Пример решения задачи ЛП симплекс-методом

Задача. Для реализации трёх групп товаров коммерческое предприятие располагает тремя видами ограниченных материально-денежных ресурсов в количестве единиц. При этом для продажи 1 группы товаров на 1 тыс. руб. товарооборота расходуется ресурса первого вида в количестве a ₁₁=4 единиц, ресурса второго вида в количестве a ₂₁=3 единиц, ресурса третьего вида в количестве a ₃₁=12 единиц. Для продажи 2 и 3 групп товаров на 1 тыс. руб. товарооборота расходуется соответственно ресурса первого вида в количестве a ₁₂=8, a ₁₃=2 единиц, ресурсов второго вида в количестве a ₂₂=8, a ₂₃=4 единиц, ресурсов третьего вида в количестве a ₃₂=4, a ₃₃=6 единиц. Прибыль от продажи трёх групп товаров на 1 тыс. руб. товарооборота составляет соответственно c₁=8, c₂=6, c₃=6(тыс. руб.). Определить плановый объём и структуру товарооборота так, чтобы прибыль торгового предприятия была максимальной. Сведём условие задачи в таблицу.

Табл.9

Запишем математическую модель задачи:

При ограничениях

найти такой план , что

Для получения первого опорного плана преобразуем систему ограничений к системе уравнений:

Целевая функция для примет вид:

При этом условии построим первый опорный план, расположив его в первой симплексной таблице. Учитывая шаги 1-5, улучшаем план, получаем вторую и третью симплексные таблицы.

Табл.10

План	БП	Ресурсы плана	Коэффициенты при переменных
x1	x2	x3	x4	x5	x6
I	x4
x5
x6
Индексная строка			-8	-6	-6				-

Табл.11

План	БП	Ресурсы плана	Коэффициенты при переменных
x1	x2	x3	x4	x5	x6
II	x1				0.5	0.25
x5				2.5	-0.75			61.2
x6			-20		-3
Индексная строка					-2				-

Табл.12

План	БП	Ресурсы плана	Коэффициенты при переменных
x1	x2	x3	x4	x5	x6
III	x3					0.5
x5		-5	-8		-2
x6			-20		-3
Индексная строка

тыс.руб.

На 3 итерации получился план III, который можно считать оптимальным, и.к. все коэффициенты индексной строки неотрицательны. Следовательно, необходимо продавать товаров III группы 58 единиц, при этом коммерческое предприятие получает максимальную прибыль 348 тыс. руб. Товары I и II групп не реализуются, т.к. x ₁=0, x ₂=0.

В оптимальном плане среди базисных переменных находятся дополнительные переменные x ₅ и x ₆. Это указывает на то, что ресурсы второго и третьего вида, недоиспользованы соответственно на 8 и 84 единицы, а ресурс I вида использован полностью, т. е. x₄ =0.

В индексной строке III плана в столбцах переменных x ₁, x ₂, x ₄, не вошедших в состав базисных, получены ненулевые элементы, поэтому оптимальный план задачи ЛП является единственным.

3.3 Частные случаи решения задачи ЛП симплекс – методом.

Возможны следующие случаи:

1. При решении задачи ЛП на максимум признаком оптимальности плана является положительность всех коэффициентов индексной строки симплексной таблицы.

2. Если в разрешающем столбце все коэффициенты то функция цели неограниченна на множестве допустимых планов, т.е. и задачу решить нельзя.

3. Если в дополнительном столбце Q_i симплексной таблицы содержатся два или несколько одинаковых наименьших значений, то новый опорный план будет вырожденным (одна или несколько базисных переменных станут равными нулю). Вырожденные планы могут привести к зацикливанию, т.е. многократному повторению процесса вычислений, не позволяющему завершить задачу. Чтобы избежать этого, делим элементы строк, имеющие одинаковое наименьшее значение Q_i, на предполагаемые разрешающие элементы, а результаты заносим в дополнительные строки. За ведущую выбирается та строка, в которой раньше встречается меньшее число при чтении таблицы слева направо по столбцам.

4. Если в оптимальный план вошла дополнительная переменная x_n+i, то при реализации такого плана имеются недоиспользованные ресурсы i-го вида в количестве, полученном в столбце свободных членов симплексной таблицы.

5. Если в индексной строке симплексной таблицы оптимального плана находится нуль, принадлежащий свободной переменной, не вошедшей в базис, а в столбце, содержащем этот нуль, имеется хотя бы один положительный элемент, то задача имеет множество оптимальных планов. Свободную переменную, соответствующую указанному столбцу, можно внести в базис, выполнив соответствующие этапы алгоритма. В результате будет получен второй оптимальный план с другим набором базисных переменных.