№ |
Б |
Сб |
В |
c1=1 |
c2=1 |
c3=1 |
c4=0 |
c5=0 |
A1 |
A2 |
A3 |
A4 |
A5 |
||||
1 |
A1 |
с1= 1 |
b1=1 |
1 |
0 |
0 |
-1 |
-1 |
2 |
A2 |
с2= 1 |
b2=1 |
0 |
1 |
0 |
-2 |
-2 |
3 |
A3 |
с3= 1 |
b3=2 |
0 |
0 |
1 |
-3 |
-3 |
4 |
|
Z=4 |
0 |
0 |
0 |
-6 |
-6 |
2) Находим базисные столбцы матрицы системы ограничений А1 = , А2 = , А3 = .
3) В столбце Б симплексной таблицы запишем базисные столбцы А1, А2 и А3 так, что в столбце Аi единица стоит на i-ом месте.
4) В столбце Сб симплексной таблицы запишем коэффициенты целевой функции Z(X), номера которых совпадают с номерами базисных столбцов этой строки.
5) В столбце В запишем свободные члены b1 = 1, b2 = 1, b3 = 2.
6) Сверху над столбцами А1, А2, А3, А4 и А5 запишем коэффициенты целевой функции с1 = 1, с2 = 1, с3 = 1, с4 = 0 и с5 = 0.
7) В столбцах А1, А2, А3, А4 и А5 запишем столбцы матрицы А.
8) В строке 4 запишем текущие значения Z целевой функции, а также оценки ∆1, ∆2, ∆3, ∆4 и ∆5 столбцов А1, А2, А3, А4 и А5.
9) Находим Z по формуле:
Z =СбВ =(с1=1, с2=1, с3=1)∙(b1=1, b2=1, b3=2)= (1)∙(1)+(1)∙(1)+(1)∙(2) = 4.
10) Находим оценки небазисных столбцов ∆4 и ∆5 по формуле: ∆i= CбАi– ci ,
∆4 = CбА4 – c4 = (с1=1, с2=1, с3=1)∙(а14=-1, а24=-2, а34=-3) – 0 = (+1)∙(-1)+(1)∙(-2)+(1)∙(-3) = –1 –2 –3 = –6 < 0 .
∆5 = CбА5 – c5 = (с1=1, с2=1, с3=1)∙( а15=-1, а25=-2, а35=-3) – 0 = (1)∙(-1)+(1)∙(-2)+(1)∙(-3) = –1 –2 –3 = –6 < 0 .
Для базисных столбцов А1, А2, А3 оценки равны ∆j = 0; j=1, 2, 3.
11) Значения базисных переменных в таблице равны x1= b1=1, x2= b2=1, x3= b3= 2.
12) Значения небазисных переменных берутся равными нулю, т. е. х4= 0, х5= 0.
13) Текущий план по таблице Х0 = (х1 = 1, х2 = 1, х3 = 2, х4 = 0, х5 = 0).
14)Так как ∆i ≤0 при j = 1,2,3,4,5 ,значит текущий план оптимален: Х*=Х0=(х1=1,х2=1,х3=2,х4=0,х5=0),а минимальное значение функции Z(X) равно min Z(X) = 4.
15) Проверка: 1 + 0 + 0 – 0 – 0 = 1 ,0 + 1 + 0 – 0 – 0 = 1 ,0 + 0 + 2 – 0 – 0 = 2 ,
x1 = 1 > 0 , x2 = 1 > 0 , x3 = 2 > 0 , х4 = 0 , х5 = 0 ,Z(X0) = Z (1, 1, 2, 0, 0) = 1 + 1 + 2 = 4.
°2) В задаче на максимум, если ∆ j ³ 0 при всех j = m+1, m+2, …, n , то текущий план Х0 оптимален: Х0 = Х*, и тогда max Z(X) = Z. Если же хотя бы одна оценка ∆ j < 0 , то текущий план Х0 не оптимален. Его можно улучшить, то есть перейти к другому текущему плану Х1 , для которого значение Z(X) окажется большим.
Пример 3. Z(X) = 0x1 + 1x2 + 1x3 – 2x4 → max,
x1 + 0x2 + 0x3 + 3x4 = 4,
0x1 + 0x2 + x3 + 4x4 = 13 ,
0x1 + x2 + 0x3 - 2x4 = 2 ,
xi ≥ 0, i = 1, 2, 3, 4.
Решение. 1) Составим симплексную таблицу.
№ |
Б |
Сб |
В |
c1=0 |
c2=1 |
c3=1 |
c4=-2 |
A1 |
A2 |
A3 |
A4 |
||||
1 |
A1 |
с1= 0 |
b1=4 |
1 |
0 |
0 |
3 |
2 |
A3 |
с3= 1 |
b2=13 |
0 |
0 |
1 |
4 |
3 |
A2 |
с2= 1 |
b 3=2 |
0 |
1 |
0 |
-2 |
4 |
|
Z=15 |
∆1=0 |
∆2=0 |
∆3=0 |
∆4=4 |
2) Находим базисные столбцы матрицы ограничений.А1 = , А3 = , А3 = .
3) В столбце Б симплексной таблицы запишем базисные столбцы А1, А2 и А3 так, что в столбце Аi единица стоит на i-ом месте.
Уважаемый посетитель!
Чтобы распечатать файл, скачайте его (в формате Word).
Ссылка на скачивание - внизу страницы.