Решения задачи планирования производства симплекс методом (стр. 7 из 10)

подмножество базисных переменных

, при этом число m базисных переменных равно числу уравнений (ограничивается) при условии, что уравнения являются линейно-независимыми; подмножество

остальных n-m свободных (внебазисных) переменных {xj}, j

Б[1].

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

Наиболее очевидный метод решения ЗЛП состоит в том, чтобы для каждого из

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

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

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

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

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

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

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

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

max.

x1+4x2+2x3+x4+3x5

600;

2x1+2x2+x3+4x4+2x5

590;

4x1+x2+3x3+x4+2x5

750;(4)

3x1+2x2+4x3+2x4+x5

670;

x1+2x2+x3+4x4+4x5

495;

x1, x2, x3, x4, x5

Приведем ЗЛП к канонической форме. Приведение системы ограничений, заданных в форме неравенств, к канонической форме равенств осуществляется посредством соответствующего увеличения размерности вектора 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=(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. Исходная симплекс таблица в общем виде

b	x1	x2	x3	x4	x5	x6	x7	x8	x9	x10
x6	b6	a61	a62	a63	a64	a65	a66	a67	a68	a69	a610
x7	b7	a71	a71	a71	a71	a71	a71	a71	a71	a71	a710
x8	b8	a81	a82	a83	a84	a85	a86	a87	a88	a89	a810
x9	b9	a91	a92	a93	a94	a95	a96	a97	a98	a99	a910
x10	b10	a101	a102	a103	a104	a105	a106	a107	a108	a109	a1010
f(x)	f0	c1	c2	c3	c4	c5	c6	c7	c8	c9	c10

В нашем случае:

Таблица 2. Исходная симплекс таблица поставленной задачи

БП	СЧ	X1	X2	X3	X4	X5	X6	X7	X8	X9	X10
X6	600	1	4	2	1	3	1	0	0	0	0
X7	590	2	2	1	4	2	0	1	0	0	0
X8	750	4	1	3	1	2	0	0	1	0	0
X9	670	3	2	4	2	1	0	0	0	1	0
X10	495	1	2	1	4	4	0	0	0	0	1
Y	0	-60	-50	-37	-45	-56	0	0	0	0	0

Составленная симплекс-таблица соответствует начальному базису и начальной опорной точке ОДР. Переход к очередной опорной точке в процессе поиска оптимального решения сопровождается составлением новой симплекс-таблицы.

Каждая симплекс-таблица анализируется по критериям допустимости и оптимальности базиса.

3.3.4 Проверка признака допустимости и оптимальности базиса

Признак допустимости базиса:

в опорной точке в соответствии с (7) xj=bi, i=6,…,10; j=6,…,10, поэтому признак допустимости базиса формулируется как условие bi

0, i=6,…,10.

Признак оптимальности базиса:

Если для

то найденное решение оптимально и единственно.

Если для

то найденное решение оптимально, но не единственно.

Если

то решение неоптимально. В этом случае поиск оптимального решения продолжается и необходимо перейти к новой опорной точке.

Перейдем к конкретному случаю. В нашем случае выполняется условие допустимости базиса, так как b=(600, 590, 750, 670, 495)T<0 и bi<0 (i=6,…,10).

Выбранный нами начальный базис XБО=(x6, x7, x8, x9, x10)T не является оптимальным, так как c1=-60<0, c2=-50<0, c3=-37<0, c4=-45<0 и c6=56<0. Таким образом, необходимо осуществить переход к новой опорной точке (новому базису).

3.3.5 Нахождение разрешающего элемента в симплекс-таблице. Формирование нового базиса

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

Выбор переменной xr. Выбор переменной xr осуществляется по результатам анализа коэффициентов cj симплекс-таблицы. Найдем cr=

В нашем случае min{c1, c2, c3, c4, c5}=c1=-60 и xr=x1.

Столбец, который соответствует переменной xr=x1 в симплекс-таблице, будем называть разрешающим.

Выбор переменной xs. Выбор переменной xs проводится по результатам анализа коэффициентов air i=1,2,3,4,5 разрешающего столбца.

Если

, это означает, что ОДР такова, что неограниченное увеличение свободной переменной xr приводит к неограниченному возрастанию целевой функции (ОДР не замкнута).

Если

, то соответствующие базисные переменные xi (i=6,7,8,9,10) получают отрицательные приращения при увеличении xr=x1. Среди этих переменных xi необходимо отыскать xs, достигающую нуля при минимальном значении приращения xr. Нужно найти

В нашем случае min{600/1, 590/2, 750/4, 670/3, 495/1}=min{600,295,187.5,223.3,495}=187.5 и xs=x8. Строка, которая соответствует переменной xs=x8 в симплекс-таблице, называется разрешающей. Элемент asr=a81=4 называется разрешающим элементом симплекс-таблицы.

Выбор разрешающего элемента завершает формирование нового базиса XБ1, отличающегося от прежнего базиса одной переменной xr=x1, то есть вместо переменной x8 в базис XБ1 будет включена переменная x1: XБ1=(x6, x7, x1, x9, x10)T.

Для нового базиса (новой опорной точки) снова заполняется симплекс-таблица, в которой новые базисные переменные выражены через новые свободные.

3.3.6 Пересчет симплекс-таблицы

Правила пересчета:

Разрешающий элемент заменяется на 1.

Элементы разрешающего столбца за исключением asr переписываются без изменений.

Элементы разрешающей строки за исключением asr изменяют знак на противоположный.

Оставшиеся элементы новой симплекс-таблицы вычисляются согласно следующему правилу: произведение соответствующего элемента прежней таблицы на разрешающий элемент asr минус произведение элементов, находящихся на другой диагонали таблицы. В соответствии с этим правилом имеем: