2015-06-30
270
http://www.mathelp.spb.ru/applet/SimplexTool.htm. Программа (апплет) выдает решение задачи, нужно только ввести исходные данные.
Решение задачи линейного программирования можно найти симплексным методом. Прежде чем применять указанный метод, следует записать исходную задачу в форме основной задачи линейного программирования, если она не имеет такой формы записи.
Симплексный метод решения задачи линейного программирования основан на переходе от одного опорного плана к другому, при котором значение целевой функции возрастает (при условии, что данная задача имеет оптимальный план и каждый ее опорный план является невырожденным). Указанный переход возможен, если известен какой-нибудь исходный опорный план. Рассмотрим задачу, для которой этот план можно непосредственно записать.
Пусть требуется найти максимальное значение функции
при условиях
Здесь 
и 
– заданные постоянные числа 
Векторная форма данной задачи имеет следующий вид: найти максимум функции
(22)
при условиях
(23)
(24)
|
|
|
где
Так как
то по определению опорного плана 
является опорным планом данной задачи (последние 
компонент вектора Х равны нулю). Этот план определяется системой единичных векторов 
которые образуют базис m- мерного пространства. Поэтому каждый из векторов а также вектор 
могут быть представлены в виде линейной комбинации векторов данного базиса. Пусть
Положим 
Так как векторы 
– единичные, то 
и 
а
