Презентация на тему Графический метод и симплекс-метод задачи линейного программирования

задачи линейного программирования.
Найти минимальное решение функции

хотя бы одно решение) и ее многоугольник решений ограничен.

Линейная функция Z при фиксированных значениях является уравнением прямой .

график линейной функции

. Тогда задачу линейного программирования можно сформулировать так: найти точку многоугольника решений, в которой прямая опорная и функция Z при этом достигает минимума.

в направлении

, поэтому прямую передвигаем параллельно самой себе в направлении N

задач линейного программирования может существовать несколько допустимых решений со

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

что существует такая угловая точка (вершина) многогранника решений, в

которой целевая функция достигает своего наибольшего (наименьшего) значения.

опорный план, а каждый опорный план определяется системой m

линейно независимых векторов, содержащихся в данной системе из n векторов .

только опорные планы. Количество опорных планов, содержащихся в данной

задаче, определим через .

место один из случаев:

1. Все

для любы , то работает признак оптимальности, и исходный опорный план является оптимальным.

некоторы , но при этом все

, тогда целевая функция неограниченна на множестве ее планов.

для некоторых j, и при этом

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

таблице небазисный вектор имеет нулевую оценку, то ЗЛП будет

иметь неединственное решение. Можно перейти к другой оптимальной таблице с другим решением, но значение целевой функции будет оставаться прежним. График целевой функции параллелен той прямой, на которой лежит точка min или max.

ЛП имеет неограниченный оптимум, если у нее нет конечного

оптимального решения. А планом случая (для задачи максимизации), (для задачи минимизации).

симплекс-метода предполагаем, что все .

Если какое-то , то такой план задачи в качестве базисной переменной содержит нулевое значения, т.к. план называется вырожденным.

этапе расчета возникает неопределенность в выборе разрешающей строчки, т.е.

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