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

Решить симплексным методом задачу:

Решение:

Приводим задачу к каноническому виду.

Для этого в левую часть первого ограничения-неравенства вводим дополнительную переменную x₆ с коэффициентом +1. В целевую функцию переменная x₆ входит с коэффицентом ноль (т.е. не входит).

Получаем:

Находим начальное опорное решение. Для этого свободные (неразрешенные) переменные приравниваем к нулю х1 = х2 = х3 = 0.

Получаем опорное решение Х1 = (0,0,0,24,30,6) с единичным базисом Б1 = (А4, А5, А6).

Результаты опорного решения записываются в симплексную таблицу:

№ опорного плана	Базисные переменные	Значение баз. переменных	X1	X2	X3	X4	X5	X6	Ɠmax
I	X4
X5				-4
X6			-2
Индексная строка	F(x)		-9	-5	-4	-3	-2
II	X1
X5	-18
X6	-18
Индексная строка

Получаем первый опорный план. Его нельзя назвать оптимальным, т.к. целевая функция =0.

Переходим на улучшение опорного плана:

1). Определяем ведущий столбец по индексной строке –это max значение по модулю. В нашем случае –это -9. Следовательно x1-ведущий столбец.

2). Переходим к определению ведущей строки: для этого заполним последний столбец Ɠmax

Т.е. разделим значение базисных переменных на коэффициенты ведущего столбца –получим(24,15,6).Выберем max значение т.е. строка x4

3).определяем разрешающий элемент симплексной таблицы- это есть пересечение ведущего столбца и ведущей строки. В нашем примере-это 1.

4). Переходим к построению второго опорного плана:

для этого заполняем следующую часть таблицы:

а) во втором опорном плане переменная ведущего столбца вытесняет переменную ведущей строки, т.е. в нашем примере x1 вытеснила x4. Тогда базисными переменными во втором плане будут-x1,x5,x6

б) значения ведущей строки перейдут в новый опорный план путем деления всех её коэффициентов на разрешающий элемент, т.к. разрешающий элемент=1то ведущая строка перепишется без изменения(при делении на 1 получаются те же значения)

в) ведущий столбец перейдет в новый опорный план =0

г) все остальные коэффициенты таблицы находятся по формуле:

НЭ=СЭ-(А*В)/РЭ

СЭ В

А РЭ

Например: в первом плане стоит число=30 а в новый план перенесем это значение применяя данную формулу НЭ=30-24*2/1=-18. ЧИСЛО6 запишется как НЭ=6-24*1/1=-18. F(x)=0 запишется как НЭ=0-(-9)*24/1=216 и т.д. по этому же принципу.

Дата добавления: 2015-04-24