Лабораторки / PM_Praktika_2013 / ПМ Практика 2013 / Методические указания / Лабораторная работа 2 -СимплТабл
.docЛабораторная работа 2
Симплексный метод решения задач линейного программированияс помощью симплекс- таблиц
Постановка задачи
Найти симплексным методом минимум целевой функции
F = x1+ x2®min
при ограничениях
Решение с помощью симплекс-таблиц.
Записываем постановку задачи в канонической форме:
Знак “-” перед новой переменной учитывается, если исходное неравенство ≥. Знак “+” перед новой переменной, если исходное неравенство ≤.
На листе Excel следует записать условие задачи своего варианта в общем виде и в канонической форме. Составляем симплекс-таблицу 1:
Полагая переменные х1 = 0 и х2 = 0, находим базисное решение:
Х1 = (0; 0; 4; 0; -4).
Базисное решение не допустимое (x5< 0).
Выбираем ведущей строкой х5, так как x5< 0.
В качестве ведущего столбца выбираем х1 .
Найдем оценочные отношения.
Из оценочных отношений следует выбирать положительную и минимальную. В данном случае положительные оценочные отношения одинаковы (равны 4), можно выбрать любую. Например, в строке х3 . Строка х3 становится ведущей.
Ведущий элемент равен 1.
Строим симплекс-таблицу 2.
В базисе меняем х3 на х1 .
Столбец х1 заполняем нулями и 1 на месте ведущего элемента.
Ведущую строку делим на ведущий элемент (на 1).
В ведущей строке содержатся нули. Соответствующие столбцы можно переписать.
Остальные элементы рассчитываем по правилу прямоугольника в соответствии с методом Гаусса.
Полагая переменные х2 = 0 и х3 = 0, находим базисное решение:
Х2 = (4; 0; 0; 12; 0;).
Замечание: в базисном решении х4 = (-12) / (-1) = 12.
Базисное решение допустимое .
В качестве ведущего столбца выбираем х3 .
Найдем оценочные отношения.
Из оценочных отношений следует выбирать положительное и минимальное.
В данном случае положительные оценочные отношения одинаковы (равны 4), можно выбрать любую. Например, в строке х4 . Строка х4 становится ведущей.
Ведущий элемент равен - 3.
Симплекс-таблицу 3 строим по тому же алгоритму.
Полагая переменные х2 = 0 и х4 = 0, находим базисное решение:
Х3 = (0; 0; 4; 0; -4).
Базисное решение не допустимое (x5< 0).
Замечание: в базисном решении х5 = 4 / (-1) = - 4.
В качестве ведущей строки выберем х5 , а в качестве ведущего столбца х2, так как только при таком выборе получим минимальное положительное оценочное отношение.
Симплекс-таблицу 4 строим по тому же алгоритму.
Полагая переменные х4 = 0 и х5 = 0, находим базисное решение:
Х4 = (1; 3; 15; 0; 0).
Базисное решение допустимое.
Все коэффициенты последней строки неположительны. с5= -1 и остальные равны нулю. Следовательно, критерий оптимальности выполнен.
Ответ: Fmin = 4 при х1 = 1 и х2 = 3.
Базисное решение Х* = (1; 3; 15; 0; 0) следует запомнить для решения двойственной задачи.
Замечание: ответ можно было получить уже в 3-ей симплекс-таблице, если в симплекс-таблице 1 выбрать в качестве ведущей строки х5 вместо х3 .