| Содержание |
Задача 1.Розв’язати задачу лінійного програмування графічним методом
Знайдемо точку мінімума
Задача 2.Розв’язати симплекс-методом задачу лінійного програмування
x1 x2
x3 3 -1 1
x4 10 -1 2
x5 36 4 1
Lmin 0 -2 3
Вибрали генеральний стовпчик, оскільки 3>0.
генеральну строку берем по х3, оскільки(3/1)<(10/2)<(36/1)
Перерахуємо таблицю
x1 x3
x2 3 -1 1
x4 4 1 -2
x5 33 5 -1
Lmin -9 1 -3
Вибрали генеральний стовпчик, оскільки 1>0.
генеральну строку берем по х4, оскільки(4/1)<(33/5)
Перерахуємо таблицю
x4 x3
x2 7 1 -1
x1 4 1 -2
x5 13 -5 9
Lmin -13 -1 -1
Оскільки коефіцієнти при цільовій функції <0, то знайдене рішення оптимальне, тобто Lmin=-13
x2=7 x1=4 x5=13 x4=x3=0
Задача 3. Для даної задачі лінійного програмування побудувати двоїсту, розв’язати одну з пари двоїстих задач симплекс-методом і за її розв’язком знайти розв’язок двоїстої до неї
Запишемо двоїсту задачу
Розв'яжемо пряму задачу симплекс-методом
x1 x2
x3 3 -1 1
x4 10 -1 2
x5 36 6 1
Lmin 0 1 -9
Вибрали генеральний стовпчик, оскільки 1>0.
генеральну строку берем по х5, оскільки 6>0
Перерахуємо таблицю
x5 x2
x3 9 1/6 7/6
x4 46 1/6 13/6
x1 6 1/6 1/6
Lmin -6 -1/6 -55/6
Оскільки коефіцієнти при цільовій функції <0, то знайдене рішення оптимальне, тобто Lmin=-6, а Lmax=6
x2=0 x1=6 x5=0 x4=46 x3=9
х1 х2 х3 х4 х5
у4 у5 у1 у2 у3
y1=0 y3=1/6 y2=0 y5=55/6 y4=0 F=6
Задача 4. Розв’язати методом потенціалів транспортну задачу
Q1 Q2 Q3 Q4 Q5 a
P1 8 6 7 3 4 50
P2 7 4 9 3 4 50
P3 6 1 4 5 2 55
P4 7 8 3 4 2 50
b 35 30 50 25 65
Знайдемо опорний план методом найменшої вартості
Q1 Q2 Q3 Q4 Q5 a
P1 8(19) 6 (2) 7 (17) 3 (15) 4 (10) 50
P2 7 (20) 9 (3) 9 (18) 3 (16) 4 (11) 50
P3 6 (6) 1 (1) 4 (7) 5 (8) 2 (5) 55
P4 7 (13) 8 (4) 3 (12) 4 (14) 2 (9) 50
b 35 30 50 25 65
Цифри в дужках вказують порядок заповнення елементів в матриці Х0
Х0
0 0 25 25 0 25 25 0
35 0 15 0 0 15 35 0
0 30 0 0 25 30 25 0
0 0 10 0 40 40 10 0
35 30 10 25 25
0 0 25 0 40
15 0
0
Заповнено 8 клітинок(5+4-1), отже план невироджений
Відповідне значення цільової функції дорівнює
L=25*7+25*3+35*7+15*9+30*1+25*2+10*3+40*2=1020
Знайдемо потенціали:
Нехай u1=0
u1+v3=7=>v3=7
u1+v4=3=>v4=3
u2+v3=9=>u2=2
u4+v3=3=>u4=-4
u2+v1=7=>v1=5
u4+v5=2=>v5=6
u3+v5=2=>u3=-4
u3+v2=1=>v2=-4
Перевіримо на оптимальність знайдене рішення
Q1 Q2 Q3 Q4 Q5 a ui
P1 5 8 5 6 7 25 7 3 25 3 6 4 50 0
P2 7 35 7 63 7 4 9 15 9
5 3 8 4
50 2
P3 1 6 1 30 1 3 4 -1 5 2 25 2 55 -4
P4 1 7 1 8 3 10 3
-1 4 2 40 2
50 -4
b 35 30 50 25 65
vj 5 5 7 3 6
Умова оптимальності(Сij≥ ui+ vj) не виконується в чотирьох клітинках, які виділені, тому план не оптимальний
Перерахуємо план і потенціали і перевіримо план на оптимальність
4-2+3-9=-4
∆L=-4*15=-60 L=1020-60=960
Q1 Q2 Q3 Q4 Q5 a ui
P1 9 8 5 6 7 25 7
3 25 3 6 4
50 0
P2 7 35 7 63 3 4 5 9 1 3 4 15 4 50 -2
P3 5 6 1 30 1 3 4 -1 5 2 25 2 55 -4
P4 5 7 1 8 3 25 3
-1 4 2 25 2
50 -4
b 35 30 50 25 65
vj 9 5 7 3 6
Умова оптимальності(Сij≥ ui+ vj) не виконується в двох клітинках, які виділені, тому план не оптимальний
Перерахуємо план і потенціали і перевіримо план на оптимальність
4-2+3-7=-2
∆L=-2*25=-50
L=960-50=910
Q1 Q2 Q3 Q4 Q5 a
P1 7 8 3 6 5 7 3 25 3 4 25 4 50
P2 7 35 7 63 3 4 5 9 3 3 4 15 4 50
P3 5 6 1 30 1 3 4 1 5 2 25 2 55
P4 5 7 1 8 3 50 3 1 4 2 2 50
b 35 30 50 25 65
Заповнено 7 клітинок, отже план вироджений, тому представимо план так
Q1 Q2 Q3 Q4 Q5 a ui
P1 7 8 3 6 5 7 3 25 3 4 25 4 50 0
P2 7 35 7 63 3 4 5 9 3 3 4 15 4 50 0
P3 5 6 1 30 1 3 4 1 5 2 25 2 55 -2
P4 5 7 1 8 3 50 3 1 4 2 0 2 50 -2
b 35 30 50 25 65
vj 7 3 5 3 4
Заповнено 8 клітинок(5+4-1), отже план невироджений
Умова оптимальності(Сij≥ ui+ vj) виконується для всіх клітинок, тому план оптимальний
L=910
Задача 5. Одним із методів відтинання розв'язати задачу цілочи¬слового програмування:
Розв’яжемо задачу симплекс-методом
x1 x2
x3 -3 1 -1
x4 10 -1 2
x5 -24 -5 -6
Lmin 0 1 -2
Вибрали генеральну строку, оскільки -24<0.
24/6<24/5, тому генеральний стовпчик береться по х2
Перерахуємо таблицю
x1 x5
x3 1 11/6 -1/6
x4 2 -8/3 1/3
x2 4 5/6 -1/6
Lmin 8 8/3 -1/3
Вибрали генеральний стовпчик, оскільки 8/3>0.
генеральну строку берем по х1, оскільки 1/(11/6)<4/(5/6)
Перерахуємо таблицю
x3 x5
x1 6/11 6/11 -1/11
x4 38/11 16/11 1/11
x2 39/11 -5/11 -1/11
Lmin 72/11 -16/11 -1/11
Знайдене рішення оптимальне, але розв'язки мають бути цілими числами, тому використаємо перший алгоритм Гоморі
x1=6/11-(6/11х3-1/11х5)
Побудуємо пряму відсікання
хвід= х6=
Знайдемо оптимальне рішення, використовуючи пряму відсікання
Перерахуємо таблицю
x3 x5
x1 6/11 6/11 -1/11
x4 38/11 16/11 1/11
x2 39/11 -5/11 -1/11
x6 -6/11 -6/11 -10/11
Lmin 72/11 -16/11 -1/11
Вибрали генеральну строку, оскільки -6/11<0.
генеральний стовпчик берем по х3
Перерахуємо таблицю
x3 x6
x1 3/5 3/5 -1/10
x4 17/5 7/5 1/10
x2 18/5 -2/5 -1/10
x5 3/5 3/5 -11/10
Lmin 33/5 -7/5 -1/10
Знайдене рішення оптимальне, але розв'язки мають бути цілими числами, тому використаємо другий алгоритм Гоморі
x2=18/5-(-2/5х3-1/10х6)
Побудуємо пряму відсікання
хвід= х7=
Знайдемо оптимальне рішення, використовуючи пряму відсікання
Перерахуємо таблицю
x3 x6
x1 3/5 3/5 -1/10
x4 17/5 7/5 1/10
x2 18/5 -2/5 -1/10
x5 3/5 3/5 -11/10
х7 -3/5 -3/5 -3/20
Lmin 33/5 -7/5 -1/10
Вибрали генеральну строку, оскільки -3/5<0.
генеральний стовпчик берем по х6. Перерахуємо таблицю
x3 x7
x1 1 1 -2/3
x4 3 1 2/3
x2 4 0 -2/3
x5 5 5 -22/3
х6 4 4 -20/3
Lmin 7 -1 -2/3
Оскільки коефіцієнти при цільовій функції <0 і х1 та х2 - цілі, то знайдене рішення оптимальне, тобто Lmin=7, a Lmax=-7
x4=3 x2=4 x1=1 x3=0 x5=5 x6=4 x7=0
|
