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

Описание метода решения задачи.

Процедура решения ЗЛП начинается с приведения ее к канонической форме, то есть к стандартной форме задания, ориентированной на разработанный именно для этой формы метод решения. Задача линейного программирования в канонической форме имеет смысл при условии n>m. В этом случае полностью описывается область допустимых решений (ОДР) ЗЛП, геометрически являющую

ся выпуклым многогранником в евклидовом пространстве Rn[1]. Выпуклая фигура, как известно, характеризуется тем свойством, что, если две точки X1 и X2 принадлежат этой фигуре, то и весь отрезок X1X2 принадлежит ей. Кроме того, доказано, что оптимальное решение ЗЛП всегда лежит на границе ОДР. Поэтому справедлив вывод о том, что, по крайней мере, одна из угловых (опорных) точек выпуклого многогранника ОДР является точкой оптимума. Для того, чтобы определить координаты опорной точки, все множество переменных X={xj}, j= необходимо разделить на два подмножества

:

подмножество базисных переменных , при этом число m базисных переменных равно числу уравнений (ограничивается) при условии, что уравнения являются линейно-независимыми; подмножество остальных n-m свободных (внебазисных) переменных {xj}, jБ[1].

Количество возможных вариантов разделения переменных на базисные и свободные (число базисов) равно .

Наиболее очевидный метод решения ЗЛП состоит в том, чтобы для каждого из базисов найти координаты соответствующих опорных точек, выделить из них точки, принадлежащие ОДР, а затем из них, в свою очередь, выбрать ту, координаты которой максимизируют целевую функцию. В отличие от этого метода, реализующего, по сути, идею полного перебора опорных точек ОДР, известен более эффективный так называемый симплекс-метод решения ЗЛП.

В основе симплекс-метода лежит подход, включающий:

выбор опорной точки, принадлежащей ОДР (выбор начального допустимого базиса);

проверку опорной точки на оптимальность;

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

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

Имеем исходную ЗЛП:

{60x1+50x2+37x3+45x4+56x5}max.

x1+4x2+2x3+x4+3x5600;

2x1+2x2+x3+4x4+2x5590;

4x1+x2+3x3+x4+2x5750;(4)

3x1+2x2+4x3+2x4+x5670;

x1+2x2+x3+4x4+4x5495;

x1, x2, x3, x4, x5 0.

Приведем ЗЛП к канонической форме. Приведение системы ограничений, заданных в форме неравенств, к канонической форме равенств осуществляется посредством соответствующего увеличения размерности вектора X=(x1, x2, x3, x4, x5) с учетом обязательной неотрицательности всех его составляющих.

Таким образом, ЗЛП в канонической форме имеет вид:

max {60x1+50x2+37x3+45x4+56x5};

(5)

Поиск допустимого базиса.

Заполнение симплекс-таблицы.

ЗЛП в канонической форме можно записать в матричном виде:

(6)

b=(600, 590, 750, 670, 495)T,

X=(x1, x2, x3, x4, x5, x6, x7, x8, x9, x10)T,

C=(60,50,37,45,56,0,0,0,0,0),

A=.

Поиск допустимого базиса начинается с анализа столбцов матрицы A=(A1, A2,…, A10), используемой в записи ограничения (6) канонической формы ЗЛП. В качестве базисных следует выбирать такие 5 переменных, которым соответствует набор столбцов, позволяющих составить единичную матрицу P=(Aj1, Aj2, Aj3, Aj4, Aj5).

Если ОДР исходной ЗЛП задана в форме неравенств типа (как в нашем случае), то начальный базис может быть сформирован из дополнительных переменных x6, x7, x8, x9, x10, вводимых в систему ограничений с целью приведения ее к канонической форме равенств. В этом случае матрица P будет единичной.

Таким образом, выберем в качестве начального базиса XБО=(x6, x7, x8, x9, x10)T, так как столбцы A6, A7, A8, A9, A10 матрицы A образуют единичную матрицу.

Теперь перейдем к заполнению симплекс-таблицы. Пусть ЗЛП сформулирована в канонической форме (5). Мы выбрали базисные переменные x6, x7, x8, x9, x10. Разрешим систему неравенств в (5) относительно базисных переменных.

Система ограничений в форме Такера примет вид:

x6=600-(x1+4x2+2x3+x4+3x5);

x7=590-(2x1+2x2+x3+4x4+2x5);

x8=750-(4x1+x2+3x3+x4+2x5);(7)

x9=670-(3x1+2x2+4x3+2x4+x5);

x10=495-(x1+2x2+x3+4x4+4x5);

Целевую функцию можно представить в виде:

f(x)=f0-(-60x1-50x2-37x3-45x4-56x5), где f0=0.

Симплекс-таблица выглядит следующим образом:

Таблица 1. Исходная симплекс таблица в общем виде

 Скачать реферат