2.12
B1 | B2 | B3 | B4 | Запасы | |
A1 | |||||
A2 | |||||
A3 | |||||
A4 | |||||
Потребности |
∑a = 280 + 175 + 125 + 130 = 710
∑b = 90 + 180 + 310 + 130 = 710
Поиск первого опорного плана.
c11=4
x11 = min(280,90) = 90
280 - 90 = 190 | ||||
x | ||||
x | ||||
x | ||||
90 - 90 = 0 |
c12=5
x12 = min(190,180) = 180
190 - 180 = 10 | ||||
x | x | |||
x | x | |||
x | x | |||
180 - 180 = 0 |
c13=3
x13 = min(10,310) = 10
x | 10 - 10 = 0 | |||
x | x | |||
x | x | |||
x | x | |||
310 - 10 = 300 |
c23=2
x23 = min(175,300) = 175
x | ||||
x | x | x | 175 - 175 = 0 | |
x | x | |||
x | x | |||
300 - 175 = 125 |
c33=9
x33 = min(125,125) = 125
x | ||||
x | x | x | ||
x | x | x | 125 - 125 = 0 | |
x | x | |||
125 - 125 = 0 |
c44=6
x44 = min(130,130) = 130
x | ||||
x | x | x | ||
x | x | x | ||
x | x | 130 - 130 = 0 | ||
130 - 130 = 0 |
c14=7, но т.к. ограничения выполнены, то x14=0.
B1 | B2 | B3 | B4 | Запасы | |
A1 | 4[90] | 5[180] | 3[10] | 7[0] | |
A2 | 2[175] | ||||
A3 | 9[125] | ||||
A4 | 6[130] | ||||
Потребности |
Подсчитаем число занятых клеток таблицы, их 7, а должно быть m + n - 1 = 7. Следовательно, опорный план является невырожденным.
Значение целевой функции для этого опорного плана равно:
F(x) = 4*90 + 5*180 + 3*10 + 2*175 + 9*125 + 6*130 = 3545
Улучшение опорного плана.
u1 + v1 = 4; 0 + v1 = 4; v1 = 4
u1 + v2 = 5; 0 + v2 = 5; v2 = 5
u1 + v3 = 3; 0 + v3 = 3; v3 = 3
u2 + v3 = 2; 3 + u2 = 2; u2 = -1
u3 + v3 = 9; 3 + u3 = 9; u3 = 6
u1 + v4 = 7; 0 + v4 = 7; v4 = 7
u4 + v4 = 6; 7 + u4 = 6; u4 = -1
v1=4 | v2=5 | v3=3 | v4=7 | |
u1=0 | 4[90] | 5[180] | 3[10] | 7[0] |
u2=-1 | 2[175] | |||
u3=6 | 9[125] | |||
u4=-1 | 6[130] |
Опорный план не является оптимальным, так как существуют оценки свободных клеток, для которых ui + vj >cij
(3;1): 6 + 4 > 1; ∆31 = 6 + 4 - 1 = 9 > 0
(3;2): 6 + 5 > 3; ∆32 = 6 + 5 - 3 = 8 > 0
(3;4): 6 + 7 > 8; ∆34 = 6 + 7 - 8 = 5 > 0
(4;1): -1 + 4 > 2; ∆41 = -1 + 4 - 2 = 1 > 0
max(9,8,5,1) = 9
Запасы | |||||
4[90][-] | 5[180] | 3[10][+] | 7[0] | ||
2[175] | |||||
1[+] | 9[125][-] | ||||
6[130] | |||||
Потребности |
B1 | B2 | B3 | B4 | Запасы | |
A1 | 5[180] | 3[100] | 7[0] | ||
A2 | 2[175] | ||||
A3 | 1[90] | 9[35] | |||
A4 | 6[130] | ||||
Потребности |
u1 + v2 = 5; 0 + v2 = 5; v2 = 5
u1 + v3 = 3; 0 + v3 = 3; v3 = 3
u2 + v3 = 2; 3 + u2 = 2; u2 = -1
u3 + v3 = 9; 3 + u3 = 9; u3 = 6
u3 + v1 = 1; 6 + v1 = 1; v1 = -5
u1 + v4 = 7; 0 + v4 = 7; v4 = 7
u4 + v4 = 6; 7 + u4 = 6; u4 = -1
v1=-5 | v2=5 | v3=3 | v4=7 | |
u1=0 | 5[180] | 3[100] | 7[0] | |
u2=-1 | 2[175] | |||
u3=6 | 1[90] | 9[35] | ||
u4=-1 | 6[130] |
Опорный план не является оптимальным, так как существуют оценки свободных клеток, для которых ui + vj >cij
(3;2): 6 + 5 > 3; ∆32 = 6 + 5 - 3 = 8 > 0
(3;4): 6 + 7 > 8; ∆34 = 6 + 7 - 8 = 5 > 0
max(8,5) = 8
Запасы | |||||
5[180][-] | 3[100][+] | 7[0] | |||
2[175] | |||||
1[90] | 3[+] | 9[35][-] | |||
6[130] | |||||
Потребности |
B1 | B2 | B3 | B4 | Запасы | |
A1 | 5[145] | 3[135] | 7[0] | ||
A2 | 2[175] | ||||
A3 | 1[90] | 3[35] | |||
A4 | 6[130] | ||||
Потребности |
u1 + v2 = 5; 0 + v2 = 5; v2 = 5
u3 + v2 = 3; 5 + u3 = 3; u3 = -2
u3 + v1 = 1; -2 + v1 = 1; v1 = 3
u1 + v3 = 3; 0 + v3 = 3; v3 = 3
u2 + v3 = 2; 3 + u2 = 2; u2 = -1
u1 + v4 = 7; 0 + v4 = 7; v4 = 7
u4 + v4 = 6; 7 + u4 = 6; u4 = -1
v1=3 | v2=5 | v3=3 | v4=7 | |
u1=0 | 5[145] | 3[135] | 7[0] | |
u2=-1 | 2[175] | |||
u3=-2 | 1[90] | 3[35] | ||
u4=-1 | 6[130] |
Опорный план является оптимальным, так все оценки свободных клеток удовлетворяют условию ui + vj ≤ cij.
Минимальные затраты составят: F(x) = 5*145 + 3*135 + 2*175 + 1*90 + 3*35 + 6*130 = 2455
Анализ оптимального плана.
Из 1-го склада необходимо груз направить в 2-й магазин (145 ед.), в 3-й магазин (135 ед.)
Из 2-го склада необходимо весь груз направить в 3-й магазин.
Из 3-го склада необходимо груз направить в 1-й магазин (90 ед.), в 2-й магазин (35 ед.)
Из 4-го склада необходимо весь груз направить в 4-й магазин.
Задача имеет множество оптимальных планов, поскольку оценка для (1;4) равна 0.
2.13
B1 | B2 | B3 | B4 | Запасы | |
A1 | |||||
A2 | |||||
A3 | |||||
Потребности |
∑a = 510 + 90 + 120 = 720
∑b = 270 + 140 + 200 + 110 = 720
B1 | B2 | B3 | B4 | Запасы | |
A1 | |||||
A2 | |||||
A3 | |||||
Потребности |
Поиск первого опорного плана.
c11=1
x11 = min(510,270) = 270
510 - 270 = 240 | ||||
x | ||||
x | ||||
270 - 270 = 0 |
c12=4
x12 = min(240,140) = 140
240 - 140 = 100 | ||||
x | x | |||
x | x | |||
140 - 140 = 0 |
c13=7
x13 = min(100,200) = 100
x | 100 - 100 = 0 | |||
x | x | |||
x | x | |||
200 - 100 = 100 |
c23=8
x23 = min(90,100) = 90
x | ||||
x | x | x | 90 - 90 = 0 | |
x | x | |||
100 - 90 = 10 |
c33=4
x33 = min(120,10) = 10.
x | ||||
x | x | x | ||
x | x | 120 - 10 = 110 | ||
10 - 10 = 0 |
c34=8
x34 = min(110,110) = 110
x | ||||
x | x | x | ||
x | x | 110 - 110 = 0 | ||
110 - 110 = 0 |
B1 | B2 | B3 | B4 | Запасы | |
A1 | 1[270] | 4[140] | 7[100] | ||
A2 | 8[90] | ||||
A3 | 4[10] | 8[110] | |||
Потребности |
Подсчитаем число занятых клеток таблицы, их 6, а должно быть m + n - 1 = 6. Следовательно, опорный план является невырожденным.
Значение целевой функции для этого опорного плана равно:
F(x) = 1*270 + 4*140 + 7*100 + 8*90 + 4*10 + 8*110 = 3170
Улучшение опорного плана.
u1 + v1 = 1; 0 + v1 = 1; v1 = 1
u1 + v2 = 4; 0 + v2 = 4; v2 = 4
u1 + v3 = 7; 0 + v3 = 7; v3 = 7
u2 + v3 = 8; 7 + u2 = 8; u2 = 1
u3 + v3 = 4; 7 + u3 = 4; u3 = -3
u3 + v4 = 8; -3 + v4 = 8; v4 = 11
v1=1 | v2=4 | v3=7 | v4=11 | |
u1=0 | 1[270] | 4[140] | 7[100] | |
u2=1 | 8[90] | |||
u3=-3 | 4[10] | 8[110] |
Опорный план не является оптимальным, так как существуют оценки свободных клеток, для которых ui + vj >cij
(1;4): 0 + 11 > 3; ∆14 = 0 + 11 - 3 = 8 > 0
(2;4): 1 + 11 > 9; ∆24 = 1 + 11 - 9 = 3 > 0
max(8,3) = 8
Запасы | |||||
1[270] | 4[140] | 7[100][-] | 3[+] | ||
8[90] | |||||
4[10][+] | 8[110][-] | ||||
Потребности |
B1 | B2 | B3 | B4 | Запасы | |
A1 | 1[270] | 4[140] | 3[100] | ||
A2 | 8[90] | ||||
A3 | 4[110] | 8[10] | |||
Потребности |
u1 + v1 = 1; 0 + v1 = 1; v1 = 1
u1 + v2 = 4; 0 + v2 = 4; v2 = 4
u1 + v4 = 3; 0 + v4 = 3; v4 = 3
u3 + v4 = 8; 3 + u3 = 8; u3 = 5
u3 + v3 = 4; 5 + v3 = 4; v3 = -1
u2 + v3 = 8; -1 + u2 = 8; u2 = 9
v1=1 | v2=4 | v3=-1 | v4=3 | |
u1=0 | 1[270] | 4[140] | 3[100] | |
u2=9 | 8[90] | |||
u3=5 | 4[110] | 8[10] |
Опорный план не является оптимальным, так как существуют оценки свободных клеток, для которых ui + vj >cij
(2;1): 9 + 1 > 5; ∆21 = 9 + 1 - 5 = 5 > 0
(2;2): 9 + 4 > 6; ∆22 = 9 + 4 - 6 = 7 > 0
(2;4): 9 + 3 > 9; ∆24 = 9 + 3 - 9 = 3 > 0
(3;2): 5 + 4 > 2; ∆32 = 5 + 4 - 2 = 7 > 0
max(5,7,3,7) = 7
Запасы | |||||
1[270] | 4[140][-] | 3[100][+] | |||
6[+] | 8[90][-] | ||||
4[110][+] | 8[10][-] | ||||
Потребности |
B1 | B2 | B3 | B4 | Запасы | |
A1 | 1[270] | 4[130] | 3[110] | ||
A2 | 6[10] | 8[80] | |||
A3 | 4[120] | ||||
Потребности |
u1 + v1 = 1; 0 + v1 = 1; v1 = 1
u1 + v2 = 4; 0 + v2 = 4; v2 = 4
u2 + v2 = 6; 4 + u2 = 6; u2 = 2
u2 + v3 = 8; 2 + v3 = 8; v3 = 6
u3 + v3 = 4; 6 + u3 = 4; u3 = -2
u1 + v4 = 3; 0 + v4 = 3; v4 = 3
v1=1 | v2=4 | v3=6 | v4=3 | |
u1=0 | 1[270] | 4[130] | 3[110] | |
u2=2 | 6[10] | 8[80] | ||
u3=-2 | 4[120] |
Опорный план является оптимальным, так все оценки свободных клеток удовлетворяют условию ui + vj ≤ cij.
Минимальные затраты составят: F(x) = 1*270 + 4*130 + 3*110 + 6*10 + 8*80 + 4*120 = 2300
Анализ оптимального плана.
Из 1-го склада необходимо груз направить в 1-й магазин (270 ед.), в 2-й магазин (130 ед.), в 4-й магазин (110 ед.)
Из 2-го склада необходимо груз направить в 2-й магазин (10 ед.), в 3-й магазин (80 ед.)
Из 3-го склада необходимо весь груз направить в 3-й магазин.
1.32
x+2y-14=0
-5x+3y-15=0
4x+6y-24=0
Ответ: 14 при (14:0)
Область допустимых значений
1.33
4x-2y-12=0
-x+3y-6=0
2x+4y-16=0
Ответ: 13 при (4,8:3,6)
Область допустимых значений
2.23
B1 | B2 | B3 | B4 | Запасы | |
A1 | |||||
A2 | |||||
A3 | |||||
Потребности |
∑a = 160 + 140 + 60 = 360
∑b = 80 + 80 + 60 + 80 = 300
B1 | B2 | B3 | B4 | B5 | Запасы | |
A1 | ||||||
A2 | ||||||
A3 | ||||||
Потребности |
Поиск первого опорного плана.
c31=1
x31 = min(60,80) = 60
x | x | x | x | 60 - 60 = 0 | |
80 - 60 = 20 |
c22=2
x22 = min(140,80) = 80
x | |||||
140 - 80 = 60 | |||||
x | x | x | x | ||
80 - 80 = 0 |
c13=3
x13 = min(160,60) = 60
x | 160 - 60 = 100 | ||||
x | |||||
x | x | x | x | ||
60 - 60 = 0 |
c21=3
x21 = min(60,20) = 20
x | x | ||||
x | 60 - 20 = 40 | ||||
x | x | x | x | ||
20 - 20 = 0 |
c14=4
x14 = min(100,80) = 80
x | x | 100 - 80 = 20 | |||
x | x | ||||
x | x | x | x | ||
80 - 80 = 0 |
c15=0
x15 = min(20,60) = 20
x | x | 20 - 20 = 0 | |||
x | x | ||||
x | x | x | x | ||
60 - 20 = 40 |
c25=0
x25 = min(40,40) = 40.
x | x | ||||
x | x | 40 - 40 = 0 | |||
x | x | x | x | ||
40 - 40 = 0 |
B1 | B2 | B3 | B4 | B5 | Запасы | |
A1 | 3[60] | 4[80] | 0[20] | |||
A2 | 3[20] | 2[80] | 0[40] | |||
A3 | 1[60] | |||||
Потребности |
Подсчитаем число занятых клеток таблицы, их 7, а должно быть m + n - 1 = 7. Следовательно, опорный план является невырожденным.
Значение целевой функции для этого опорного плана равно:
F(x) = 3*60 + 4*80 + 0*20 + 3*20 + 2*80 + 0*40 + 1*60 = 780
Улучшение опорного плана.
u1 + v3 = 3; 0 + v3 = 3; v3 = 3
u1 + v4 = 4; 0 + v4 = 4; v4 = 4
u1 + v5 = 0; 0 + v5 = 0; v5 = 0
u2 + v5 = 0; 0 + u2 = 0; u2 = 0
u2 + v1 = 3; 0 + v1 = 3; v1 = 3
u3 + v1 = 1; 3 + u3 = 1; u3 = -2
u2 + v2 = 2; 0 + v2 = 2; v2 = 2
v1=3 | v2=2 | v3=3 | v4=4 | v5=0 | |
u1=0 | 3[60] | 4[80] | 0[20] | ||
u2=0 | 3[20] | 2[80] | 0[40] | ||
u3=-2 | 1[60] |
Опорный план является оптимальным, так все оценки свободных клеток удовлетворяют условию ui + vj ≤ cij.
Минимальные затраты составят: F(x) = 3*60 + 4*80 + 0*20 + 3*20 + 2*80 + 0*40 + 1*60 = 780
Анализ оптимального плана.
Из 1-го склада необходимо груз направить в 3-й магазин (60 ед.), в 4-й магазин (80 ед.)
Из 2-го склада необходимо груз направить в 1-й магазин (20 ед.), в 2-й магазин (80 ед.)
Из 3-го склада необходимо весь груз направить в 1-й магазин.
На 1-ом складе остался невостребованным груз в количестве 20 ед.
Оптимальный план является вырожденным, так как базисная переменная x15=0.
На 2-ом складе остался невостребованным груз в количестве 40 ед.
Оптимальный план является вырожденным, так как базисная переменная x25=0.
2.24
B1 | B2 | B3 | B4 | Запасы | |
A1 | |||||
A2 | |||||
A3 | |||||
Потребности |
∑a = 80 + 100 + 70 = 250
∑b = 80 + 50 + 50 + 70 = 250
B1 | B2 | B3 | B4 | Запасы | |
A1 | |||||
A2 | |||||
A3 | |||||
Потребности |
Поиск первого опорного плана.
c14=1
x14 = min(80,70) = 70
80 - 70 = 10 | ||||
x | ||||
x | ||||
70 - 70 = 0 |
c12=2
x12 = min(10,50) = 10
x | x | 10 - 10 = 0 | ||
x | ||||
x | ||||
50 - 10 = 40 |
c32=2
x32 = min(70,40) = 40.
x | x | |||
x | x | |||
x | 70 - 40 = 30 | |||
40 - 40 = 0 |
c31=3
x31 = min(30,80) = 30
x | x | |||
x | x | |||
x | x | 30 - 30 = 0 | ||
80 - 30 = 50 |
c23=5
x23 = min(100,50) = 50
x | x | |||
x | x | 100 - 50 = 50 | ||
x | x | |||
50 - 50 = 0 |
c21=6
x21 = min(50,50) = 50.
x | x | |||
x | x | 50 - 50 = 0 | ||
x | x | |||
50 - 50 = 0 |
B1 | B2 | B3 | B4 | Запасы | |
A1 | 2[10] | 1[70] | |||
A2 | 6[50] | 5[50] | |||
A3 | 3[30] | 2[40] | |||
Потребности |
Подсчитаем число занятых клеток таблицы, их 6, а должно быть m + n - 1 = 6. Следовательно, опорный план является невырожденным.
Значение целевой функции для этого опорного плана равно:
F(x) = 2*10 + 1*70 + 6*50 + 5*50 + 3*30 + 2*40 = 810
Улучшение опорного плана.
u1 + v2 = 2; 0 + v2 = 2; v2 = 2
u3 + v2 = 2; 2 + u3 = 2; u3 = 0
u3 + v1 = 3; 0 + v1 = 3; v1 = 3
u2 + v1 = 6; 3 + u2 = 6; u2 = 3
u2 + v3 = 5; 3 + v3 = 5; v3 = 2
u1 + v4 = 1; 0 + v4 = 1; v4 = 1
v1=3 | v2=2 | v3=2 | v4=1 | |
u1=0 | 2[10] | 1[70] | ||
u2=3 | 6[50] | 5[50] | ||
u3=0 | 3[30] | 2[40] |
Опорный план не является оптимальным, так как существуют оценки свободных клеток, для которых ui + vj >cij
(2;2): 3 + 2 > 3; ∆22 = 3 + 2 - 3 = 2 > 0
Запасы | |||||
2[10] | 1[70] | ||||
6[50][-] | 3[+] | 5[50] | |||
3[30][+] | 2[40][-] | ||||
Потребности |
B1 | B2 | B3 | B4 | Запасы | |
A1 | 2[10] | 1[70] | |||
A2 | 6[10] | 3[40] | 5[50] | ||
A3 | 3[70] | ||||
Потребности |
u1 + v2 = 2; 0 + v2 = 2; v2 = 2
u2 + v2 = 3; 2 + u2 = 3; u2 = 1
u2 + v1 = 6; 1 + v1 = 6; v1 = 5
u3 + v1 = 3; 5 + u3 = 3; u3 = -2
u2 + v3 = 5; 1 + v3 = 5; v3 = 4
u1 + v4 = 1; 0 + v4 = 1; v4 = 1
v1=5 | v2=2 | v3=4 | v4=1 | |
u1=0 | 2[10] | 1[70] | ||
u2=1 | 6[10] | 3[40] | 5[50] | |
u3=-2 | 3[70] |
Опорный план не является оптимальным, так как существуют оценки свободных клеток, для которых ui + vj >cij
(1;1): 0 + 5 > 4; ∆11 = 0 + 5 - 4 = 1 > 0
(1;3): 0 + 4 > 3; ∆13 = 0 + 4 - 3 = 1 > 0
max(1,1) = 1
Запасы | |||||
4[+] | 2[10][-] | 1[70] | |||
6[10][-] | 3[40][+] | 5[50] | |||
3[70] | |||||
Потребности |
B1 | B2 | B3 | B4 | Запасы | |
A1 | 4[10] | 1[70] | |||
A2 | 6[0] | 3[50] | 5[50] | ||
A3 | 3[70] | ||||
Потребности |
u1 + v1 = 4; 0 + v1 = 4; v1 = 4
u2 + v1 = 6; 4 + u2 = 6; u2 = 2
u2 + v2 = 3; 2 + v2 = 3; v2 = 1
u2 + v3 = 5; 2 + v3 = 5; v3 = 3
u3 + v1 = 3; 4 + u3 = 3; u3 = -1
u1 + v4 = 1; 0 + v4 = 1; v4 = 1
v1=4 | v2=1 | v3=3 | v4=1 | |
u1=0 | 4[10] | 1[70] | ||
u2=2 | 6[0] | 3[50] | 5[50] | |
u3=-1 | 3[70] |
Опорный план является оптимальным, так все оценки свободных клеток удовлетворяют условию ui + vj ≤ cij.
Минимальные затраты составят: F(x) = 4*10 + 1*70 + 3*50 + 5*50 + 3*70 = 720
Анализ оптимального плана.
Из 1-го склада необходимо груз направить в 1-й магазин (10 ед.), в 4-й магазин (70 ед.)
Из 2-го склада необходимо груз направить в 2-й магазин (50 ед.), в 3-й магазин (50 ед.)
Из 3-го склада необходимо весь груз направить в 1-й магазин.
Задача имеет множество оптимальных планов, поскольку оценка для (2;1) равна 0.
РЕШИТЕ ЗАДАЧИ ГЕОМЕТРИЧЕСКИМ МЕТОДОМ