Курсовая работа: Решение и постоптимальный анализ задачи линейного программирования
ЦФ:
Zmin= 12X1 + 5X2 + 4X3
Ограничения:
40X1 + 30X2 + 10X3 < 900
3X1 + 2X2 + X3 < 35
1000X1 + 500X2 + 300X3 = 8000
X1, X2, X3 > 0
Приведем задачу к канонической форме и введём искусственные переменные:
Zmin = 12X1 + 5X2 + 4X3 + 0S1 + 0S2 – MR1
40X1 + 30X2 + 10X3 + 0S1 = 900
3X1 + 2X2 + X3 + 0S2 = 35
1000X1 + 500X2 + 300X3 + R1 = 8000
X1, X2, X3 > 0
R1 = – 1000X1 – 500X2 – 300X3 + 8000
Zmin = 12X1 + 5X2 + 4X3 + 0S1 + 0S2 – M (– 1000X1 – 500X2 – 300X3 + 8000) = (12 + 1000M) X1 + (5 + 500M) X2 + (4 + 300M) X3 – 8000M
Z + (–12 – 1000M) X1 + (–5 – 500M) X2 + (–4 – 300M) X3 = – 8000M
Составляем симплекс таблицу:
| Шаг 0 | |||||||
| БП | X 1 | X2 | X3 | S1 | S2 | R1 | решение |
| S1 | 40 | 30 | 10 | 1 | 0 | 0 | 900 |
| S2 | 3 | 2 | 1 | 0 | 1 | 0 | 35 |
| R1 | 1000 | 500 | 300 | 0 | 0 | 1 | 8000 |
| Z | -1000M+12 | -500M+5 | -300M+4 | 0 | 0 | 0 | -8000M |
| Шаг 1 | |||||||
| S1 | 0 | 10 | -2 | 1 | 0 | -1/25 | 580 |
| S2 | 0 | 1/2 | 1/10 | 0 | 1 | -3/1000 | 11 |
| X1 | 1 | 1/2 | 3/10 | 0 | 0 | 1/1000 | 8 |
| Z | 0 | -1 | 2/5 | 0 | 0 | M-3/250 | -96 |
| Шаг 2 | |||||||
| S1 | -20 | 0 | -8 | 1 | 0 | -3/50 | 420 |
| S2 | -1 | 0 | -1/5 | 0 | 1 | -1/250 | 3 |
| X2 | 2 | 1 | 3/5 | 0 | 0 | 1/500 | 16 |
| Z | 2 | 0 | 1 | 0 | 0 | M-1/100 | -80 |
В итоге: Z = 80, X1 = 0, X2 = 16, X3 = 0
5. Постоптимальный анализ решения
5.1 Определения статуса и ценности ресурсов
Zmin= 12X1 + 5X2 + 4X3
40X1 + 30X2 + 10X3 + S1 = 900
3X1 + 2X2 + X3 + S2 = 35
1000X1 + 500X2 + 300X3 = 8000
Двойственная задача имеет вид:
ω max = 900Y1 + 35Y2 + 8000Y3
40Y1 + 3Y2 + 1000Y3 < 12 (X1)
30Y1 + 2Y2 + 500Y3 < 5 (X2)
10Y1 + 1Y2 + 300Y3 < 4 (X3)
Y1 < 0 (S1)
Y2 < 0 (S2)