| Содержание |
Завдання 1.
1)Побудувати математичну модель задачі лінійного програмування
2) Звести дану задачу до канонічного виду
Два вироби В1 та В2 обробляються послідовно на трьох верстатах. Кожен виріб типу В1 потребує 1год. для обробки на I-му верстаті, 2год.- на II-му, год- на III-му. Кожен виріб типу В2 потребує для обробки 2год, год. і 3год відповідно на I-му, II-му і III-му верстатах. Час роботи на I-му верстаті не повинен перевищувати 70год, на II-му – 105год і на III-му – 50год. Скласти план виробництва при максимальному прибутку, якщо відомо, що продаж одного виробу типу В1 приносить прибуток 5грн, а типу В2 – 3грн.
Розв'язання.
1) х1 – кількість виробів типу В1
х2 – кількість виробів типу В2
Z=5х1+3х2 ->max
2) max(Z)=-min(-z)
z1=0-(5х1+3х2) ->min
Завдання 2
Розв’язати задачу лінійного програмування графічним методом
Z=6х1+4х2->max
Розв'язання.
Всі лінії рівня цільової функції паралельні одна одній і перпендикулярні градієнту. Такі лінії можуть бути побудовані для будь-яких значень цільової функції й усі разом покривають координатну площину. Градієнт показує напрямок росту цільової функції. Пунктиром зображена лінія, що належить області допустимих значень і проходить через крайню точку цієї області. Отже, ця точка- є оптимальною для нашої задачі
(3,0)-т.max
zmax=18
Завдання 3
Розв’язати методом повного виключення змінних(методом Гаусса) з використанням розрахункових таблиць
Розв'язання.
х1 х2 х3 в
1 2 3 5
2 -1 -1 1
1 -3 4 6
х1 х2 х3 в
1 2 3 5
0 -5 -7 -9
0 -5 1 1
х1 х2 х3 в
1 2 3 5
0 -5 1 1
0 -5 -7 -9
х1 х3 х2 в
1 3 2 5
0 1 -5 1
0 -7 -5 -9
х1 х3 х2 в
1 3 2 5
0 1 -5 1
0 0 -40 -2
х2=1/20
х3-5х2=1
х3=1+1/4=5/4
х1+3х3+2х2=5
х1=5-15/4-1/10=23/20
Завдання 4
1) Розв’язати симплекс-методом задачу лінійного програмування
Z=6х1+4х2->max
Розв'язання.
Z1=0-(6х1+4х2) -> min
х1 х2
х3 15 3 5
х4 12 4 3
Z1 0 6 4
Вибрали генеральний стовпчик, оскільки 6>4.
15/3>12/4, тому генеральна строка береться по х4
Перерахуємо таблицю
х4 х2
х3 6 -3/4 11/4
х1 3 ¼ ¾
Z1 -18 -3/2 -1/2
Оскільки коефіцієнти при цільовій функції <0, то знайдене рішення оптимальне, тобто z1=-18
Z=18
x3=6
x4=0
x1=3
x2=0
2)Побудувати двоїсту задачу до даної задачі лінійного програмування
Розв'язання.
f=15y1+12y2->min
3) Знайти розв’язок двоїстої задачі та дати економічну інтерпретацію отриманого розв’язку
Розв'язання.
Вільні змінні прямої задачі, по яким строяться обмеження, будуть відповідати базисним змінним двоїстої задачі, тобто
х1 х2 х3 х4
у3 у4 у1 у2
у3=0
у4=1/2
у1=0
у2=3/2
f=0+12*3/2=18
Інтерпретуємо нашу задачу як задачу про суміші:
Маємо 2 вироби, що містять по 2 живильні речовини. Організму потрібно на добу не менше, ніж 6 од. речовини 1-го типу і 4 од. речовини 2-го типу. В виробі 1-го типу 3од. речовини 1-го типу і 4 од. речовини 2-го типу. В виробі 2-го типу 5од. речовини 1-го типу і 3 од. речовини 2-го типу. Один виріб 1-го типу коштує 15, а 2-го типу – 12. Необхідно вибрати такий раціон харчування, щоб вартість була мінімальна.
Припустимо, що ціна 2-го виробу збільшиться. Це відповідає повороту градієнта по годинній стрілці, разом з ним повертається і перпендикулярна йому лінія рівня. При невеликому повороті оптимальний план залишається в первісній точці K. При досить великому повороті оптимальний план перейде в точку М. Критична величина ціни, при якій відбувається перехід оптимального плану з однієї точки в іншу, відповідає положенню, коли лінія рівня цільової функції паралельна прямій у1=2-4у2/3(а градієнт, відповідно, перпендикулярний цій прямій). Умовою паралельності двох прямих є пропорційність коефіцієнтів при змінних в двох рівняннях. Складемо пропорцію з невідомою ціною с1 2-го виробу:
Таким чином, при збільшенні ціни 2-го виробу з 12 до 20(і при збереженні ціни 1-го виробу) оптимальний план залишається незмінним. Якщо ж ціна підніметься вище, то оптимальним планом стане точка М(2,0). При ціні, у точності рівної 20, оптимальним є як первісний план K, так і новий план М, а також і всі точки, що лежать на відрізку KМ. У цьому випадку задача має нескінченно багато оптимальних планів. Усі ці різні плани забезпечують у точності ту саму вартість.
Так, план K відповідає вартості:15*0+20*3/2=30
План М відповідає вартості:15*2+20*0=30
Верхня критична границя ціни 2-го виробу дорівнює 20. Звідси випливає, що припустиме збільшення первісної ціни дорівнює 8.
Аналогічним образом розраховується нижня границя ціни 2-го виробу. При зменшенні ціни градієнт разом з лініями рівня буде повертатися проти годинникової стрілки. При досить сильному повороті оптимальний план залишиться в точці К.
Отже, нижня критичня границя ціни 2-го виробу, рівна 12. Припустиме зменшення первісної ціни складає 0.
Таким чином, при довільних змінах ціни 2-го виробу між нижньою і верхньою критичними границями, тобто між 12 і 20, оптимальний план залишається колишнім: організму необхідно 0 од. 1-го виробу і 3/2 од. 2-го виробу. При виході ціни за верхню чи нижню критичні границі оптимальний план зміниться, разом з ним зміниться і статус ресурсів.
Аналогічним образом обчислюються нижня і верхня границі по 1-му виробу.
Відзначимо, що зміна ціни по різних виробах по-різному впливає на напрямок повороту градієнта. При збільшенні ціни 1-го виробу градієнт повертається проти годинникової стрілки, а при зменшенні – по годинній стрілці.
Верхня критична границя ціни 1-го виробу дорівнює 15, так що припустиме збільшення первісної ціни дорівнює 0.
Нижня критична границя ціни 1-го виробу дорівнює 9, припустиме зменшення первісної ціни складає 6. При переході через цю границю оптимальний план переходить із точки К в точку М.
Якщо поступово збільшувати добову потребу речовини 1-го типу, то оптимальний план залишиться в точці К. При подальшому збільшенні відбудеться зміна статусу деяких обмежень
Тобто 6 і є верхньою критичною границею по речовині 1-го типу. Таким чином, добову потребу в речовині 1-го типу не можна збільшити без зміни статусу обмежень і без зміни тіньової ціни речовини. Величина 0- є припустимим збільшенням речовини 1-го типу.
Нижня критична границя і, відповідно, припустиме зменшення обчислюють аналогічно. При зменшенні добової потреби речовини 1-го типу, оптимальний план буде зміщатися до точки М(4/5,0). При подальшому зменшенні відбудеться зміна статусу деяких обмежень. Підставимо ці значення в ліву частину нерівності, що визначає обмеження по речовині 1-го типу:
3*4/5+4*0=12/5
Величина 12/5 – нижня критична границя речовини 1-го типу. Припустиме зменшення даної речовини дорівнює 18/5.
Таким чином, при зміні кількості речовини 1-го типу тіньові ціни і статус ресурсів зберігаються, якщо кількість речовини залишається між обчисленими критичними границями. При переході через одну з границь, відбувається зміна статусу і тіньових цін ресурсів.
Аналогічно обчислимо критичні границі речовини 2-го типу.
Верхня критична границя в точці М(2,0):
5*2+3*0=10
Припустиме збільшення даної речовини дорівнює 6.
Нижня критична границя в точці (0,4/3):
5*0+3*4/3=4
Припустиме зменшення даної речовини дорівнює 0.
Завдання 5.Розв’язати транспортну задачу методом потенціалів
В1 В2 В3 В4 a
А1 3 2 5 1 10
А2 4 1 3 2 7
А3 1 2 4 3 9
b 6 4 8 8
Розв'язання.
Знайдемо опорний план методом найменшої вартості
В1 В2 В3 В4 a
А1 3(8) 2 (5) 5 (12) 1 (1) 10
А2 4 (9) 1 (4) 3 (10) 2 (2) 7
А3 1 (7) 2 (6) 4 (11) 3 (3) 9
b 6 4 8 8
Цифри в дужках вказують порядок заповнення елементів в матриці Х0
Х0
0 0 2 8 8 2 0
0 4 3 0 4 3 0
6 0 3 0 6 3 0
6 4 3 8
0 0 3 0
2
0
Заповнено 6 клітинок(3+4-1), отже план невироджений
Відповідне значення цільової функції дорівнює
L=2*5+8*1+4*1+3*3+6*1+3*4=49
Знайдемо потенціали:
Нехай u1=0
u1+v4=1=>v4=1
u1+v3=5=>v3=5
u2+v3=3=>u2=-2
u3+v3=4=>u3=-1
u2+v2=1=>v2=3
u3+v1=1=>v1=2
Перевіримо на оптимальність знайдене рішення
В1 В2 В3 В4 a ui
А1 2 3 3 2
5 2 5
1 8 1 10 0
А2 0 4 63 1 4 1
3 3 3
-1 2 7 -2
А3 1 6 1 2 2 4 3 4 0 3 9 -1
b 6 4 8 8
vj 2 3 5 1
Умова оптимальності(Сij≥ ui+ vj) не виконується в одній клітинці, яка виділена, тому план не оптимальний
Перерахуємо план і потенціали і перевіримо план на оптимальність
2-5+3-1=-1
∆L=-1*2=-2 L=49-2=47
В1 В2 В3 В4 a ui
А1 1 3 2 2 2 4 5 1 8 1 10 0
А2 0 4 63 1 2 1 3 5 3 0 2 7 -1
А3 1 6 1 2 2 4 3 4 1 3 9 0
b 6 4 8 8
vj 1 2 4 1
Умова оптимальності(Сij≥ ui+ vj) виконується для всіх клітинок, тому план оптимальний
L=47
|
