Для виготовлення виробів №1 і №2 є 100 кг металу. На виготовлення виробу №1 витрачається 2 кг металу, а на виріб №2 – 4 кг.
Скласти план виробництва, що забезпечує одержання найбільшого прибутку від продажу виробів, якщо відпускна вартість одного виробу №1 становить 3 грн. од., а виробу №2 – 2 грн. од., причому виробів №1 потрібно виготовити не більше 40 штук, а виробів №2 – 20 шт.
Сировина
Вироби
Кількість сировини
В1
В2
Метал
2
4
100
Вартість, грн. кг
3
2
Розв’язок
Складаємо математичну модель задачі. Позначимо через х
1 кількість виробу №1, що виготовляє підприємство за деяким планом, а через х2
кількість виробу №2. Тоді прибуток, отриманий підприємством від реалізації цих виробів, складає
∫ = 3х1+2х2.
Витрати сировини на виготовлення такої кількості виробів складають відповідно:
CI =2х1+4х2,
Оскільки запаси сировини обмежені, то повинні виконуватись нерівності:
2х1+4х2≤100
Окрім того, виробів №1 потрібно виготовити не більше 40 штук, а виробів №2 – 20 шт., тобто повинні виконуватись ще нерівності: х1≤40, х2≤20.
Таким чином, приходимо до математичної моделі:
Знайти х1, х2такі, що функція ∫ = 3х1+2х2досягає максимуму при системі обмежень:
Розв'язуємо задачу лінійного програмування симплексним методом.
Для побудови першого опорного плану систему нерівностей приведемо до системи рівнянь шляхом введення додаткових змінних.
2x1 + 4x2 + 1x3 + 0x4 + 0x5 = 100
1x1 + 0x2 + 0x3 + 1x4 + 0x5 = 40
0x1 + 1x2 + 0x3 + 0x4 + 1x5 = 20
Матриця коефіцієнтів A = a(ij) цієї системи рівнянь має вигляд:
Базисні змінні це змінні, які входять лише в одне рівняння системи обмежень і притому з одиничним коефіцієнтом.
Вирішимо систему рівнянь відносно базисних змінних:
x3, x4, x5
Вважаючи, що вільні змінні рівні 0, отримаємо перший опорний план:
X1 = (0,0,100,40,20)
Оскільки завдання вирішується на максимум, то ведучий стовпець вибираємо по максимальному негативному кількістю та індексного рядку. Всі перетворення проводимо до тих пір, поки не вийдуть в індексному рядку позитивні елементи.
Складаємо симплекс-таблицю:
План
Базис
В
x1
x2
x3
x4
x5
min
1
x3
100
2
4
1
0
0
50
x4
40
1
0
0
1
0
40
x5
20
0
1
0
0
1
0
Індексний рядок
F(X1)
0
-3
-2
0
0
0
0
Оскільки, в індексному рядку знаходяться негативні коефіцієнти, поточний опорний план неоптимальний, тому будуємо новий план. У якості ведучого виберемо елемент у стовбці х1, оскільки значення коефіцієнта за модулем найбільше.
План
Базис
В
x1
x2
x3
x4
x5
min
2
x3
20
0
4
1
-2
0
5
x1
40
1
0
0
1
0
0
x5
20
0
1
0
0
1
20
Індексний рядок
F(X2)
120
0
-2
0
3
0
0
Даний план, також не оптимальний, тому будуємо знову нову симплексну таблицю. У якості ведучого виберемо елемент у стовбці х2.
План
Базис
В
x1
x2
x3
x4
x5
min
3
x2
5
0
1
0,25
-0,5
0
5
x1
40
1
0
0
1
0
0
x5
15
0
0
-0,25
0,5
1
20
Індексний рядок
F(X3)
130
0
0
0,5
2
0
0
Оскільки всі оцінки >0,
то знайдено оптимальний план, що забезпечує максимальний прибуток: х1=40, х2=5. Прибуток, при випуску продукції за цим планом, становить 130 грн.
Завдання 2
Записати двоїсту задачу до поставленої задачі лінійного програмування. Розв’язати одну із задач симплексним методом і визначити оптимальний план іншої задачі.
Розв’язок
Розв’яжемо задачу лінійного програмування симплексним методом.
Визначимо мінімальне значення цільової функції F(X) = x1+3x2при наступних умовах-обмежень.
9x1+10x2≥45
5x1-x2≤42
-x1+13x2≤4
Для побудови першого опорного плану систему нерівностей приведемо до системи рівнянь шляхом введення додаткових змінних.
9x1 + 10x2-1x3 + 0x4 + 0x5 = 45
5x1-1x2 + 0x3 + 1x4 + 0x5 = 42
-1x1 + 13x2 + 0x3 + 0x4 + 1x5 = 4
Введемо штучні змінні x.
9x1 + 10x2-1x3 + 0x4 + 0x5 + 1x6 = 45
5x1-1x2 + 0x3 + 1x4 + 0x5 + 0x6 = 42
-1x1 + 13x2 + 0x3 + 0x4 + 1x5 + 0x6 = 4
Для постановки задачі на мінімум цільову функцію запишемо так:
F(X) = x1+3x2+Mx6 =>min
Вважаючи, що вільні змінні рівні 0, отримаємо перший опорний план:
X1 = (0,0,0,42,4,45).
План
Базис
В
x1
x2
x3
x4
x5
х6
0
х6
45
9
10
-1
0
0
1
x4
42
5
-1
0
1
0
0
х5
4
-1
13
0
0
1
0
Індексний рядок
F(X0)
0
0
0
0
0
0
0
Переходимо до основного алгоритму симплекс-методу.
План
Базис
В
x1
x2
x3
x4
x5
x6
min
1
х6
45
9
10
-1
0
0
1
5,5
x4
42
5
-1
0
1
0
0
0
х5
4
-1
13
0
0
1
0
0,3077
Індексний рядок
F(X1)
0
0
0
0
0
0
0
0
Оскільки, в індексному рядку знаходяться позитивні коефіцієнти, поточний опорний план неоптимальний, тому будуємо новий план. У якості ведучого виберемо елемент у стовбці х2, оскільки значення коефіцієнта за модулем найбільше.
План
Базис
В
x1
x2
x3
x4
x5
x6
min
2
х6
41,92
9,77
0
-1
0
-0,7692
1
4,29
x4
42,31
4,92
0
0
1
0,0769
0
8,59
х2
0,3077
-0,0769
1
0
0
0,0769
0
0
Індексний рядок
F(X2)
0
0
0
0
0
0
0
0
Даний план, також не оптимальний, тому будуємо знову нову симплексну таблицю. У якості ведучого виберемо елемент у стовбці х1.
План
Базис
В
x1
x2
x3
x4
x5
x6
min
3
х1
4,29
1
0
-0,1024
0
-0,0787
0,1024
0
x4
21,18
0
0
0,5039
1
0,4646
-0,5039
45,59
х2
0,6378
0
1
-0,0079
0
0,0709
0,0079
9
Індексний рядок
F(X3)
0
0
0
0
0
0
0
0
Даний план, також не оптимальний, тому будуємо знову нову симплексну таблицю. У якості ведучого виберемо елемент у стовбці х5.
План
Базис
В
x1
x2
x3
x4
x5
x6
4
х1
5
1
1,11
-0,1111
0
0
0,1111
x4
17
0
-6,56
0,5556
1
0
-0,5556
х5
9
0
14,11
-0,1111
0
1
0,1111
Індексний рядок
F(X4)
0
0
0
0
0
0
0
Оптимальний план можна записати так:
x1 = 5
x4 = 17
x5 = 9
F(X) = 1*5 = 5
Складемо двоїсту задачу до поставленої задачі лінійного програмування.
9y1+5y2-y3≤1
10y1-y2+13y3≤3
45y1+42y2+4y3 => max
y1 ≥ 0
y2 ≤ 0
y3 ≤ 0
Рішення двоїстої задачі дає оптимальну систему оцінок ресурсів. Використовуючи останню інтеграцію прямої задачі знайдемо, оптимальний план двоїстої задачі. Із теореми двоїстості слідує, що Y = C*A-1.
Сформуємо матрицю A із компонентів векторів, які входять в оптимальний базис.
Визначивши обернену матрицю А-1 через алгебраїчне доповнення, отримаємо:
Як видно із останнього плану симплексної таблиці, обернена матриця A-1 розміщена у стовбцях додаткових змінних.
Тоді Y = C*A-1 =
Запишемо оптимальний план двоїстої задачі:
y1 = 0.11
y2 = 0
y3 = 0
Z(Y) = 45*0.11+42*0+4*0 = 5
Завдання 3
Розв’язати транспортну задачу.
1
4
7
9
1
250
2
3
1
2
4
300
2
1
3
1
4
150
110
80
100
90
70
Розв’язок
Побудова математичної моделі
. Нехай xij
— кількість продукції, що перевозиться з і
-го пункту виробництва до j
-го споживача
. Оскільки
, то задачу треба закрити, тобто збалансувати (зрівняти) поставки й потреби:
У нашому випадку робиться це введенням фіктивного постачальника, оскільки
. З уведенням фіктивного споживача транспортній таблиці додатково заявляється n робочих клітинок.
Ціни, додатковим клітинкам, щоб фіктивний стовбець був нейтральним щодо оптимального вибору планових перевезень, призначаються усі рівні нулю.
Занесемо вихідні дані у таблицю.
В1
В2
В3
В4
В5
В6
Запаси
А1
1
4
7
9
1
0
250
А2
2
3
1
2
4
0
300
А3
2
1
3
1
4
0
150
Потреби
110
80
100
90
70
250
Забезпечивши закритість розв'язуваної задачі, розпочинаємо будувати математичну модель даної задачі:
Економічний зміст записаних обмежень полягає в тому, що весь вантаж потрібно перевезти по пунктах повністю.
Аналогічні обмеження можна записати відносно замовників: вантаж, що може надходити до споживача від чотирьох баз, має повністю задовольняти його попит. Математично це записується так:
Загальні витрати, пов’язані з транспортуванням продукції, визначаються як сума добутків обсягів перевезеної продукції на вартості транспортування од. продукції до відповідного замовника і за умовою задачі мають бути мінімальними. Тому формально це можна записати так:
Запишемо умови задачі у вигляді транспортної таблиці та складемо її перший опорний план у цій таблиці методом «північно-західного кута».
Ai
Bj
ui
b
1 = 110
b
2 = 80
b
3 = 100
b
4=90
b
5=70
b
6=250
а
1 = 250
1
110
4
80
7
[-]60
9
1
[+]
0
u
1 = 0
а
2 = 300
2
3
1
[+]40
2
90
4
[-]70
0
100
u
2 = -6
а
3 = 150
2
1
3
1
4
0
150
u
3 = -6
vj
v
1 =1
v
2 =4
v
3 =7
v
4 =8
v
5 =10
v
6 =6
В результаті отримано перший опорний план, який є допустимим, оскільки всі вантажі з баз вивезені, потреба магазинів задоволена, а план відповідає системі обмежень транспортної задачі.
Підрахуємо число зайнятих клітин таблиці, їх 8, а має бути m+n-1=8. Отже, опорний план є не виродженим.
Перевіримо оптимальність опорного плану. Знайдемо потенціали ui, vi. по зайнятих клітинам таблиці, в яких ui + vi = cij, вважаючи, що u1 = 0:
u
1=0, u
2=-6, u
3=-6, v
1=1, v
2=4, v
3=7 v
4=8, v
5=10, v
6=6. Ці значення потенціалів першого опорного плану записуємо у транспортну таблицю.
Потім згідно з алгоритмом методу потенціалів перевіряємо виконання другої умови оптимальності ui
+ vj
≤ cij
(для порожніх клітинок таблиці).
Опорний план не є оптимальним, тому що існують оцінки вільних клітин для яких ui + vi>cij
(1;5): 0 + 10 > 1
(1;6): 0 + 6 > 0
(3;4): -6 + 8 > 1
Тому від нього необхідно перейти до другого плану, змінивши співвідношення заповнених і порожніх клітинок таблиці. Вибираємо максимальну оцінку вільної клітини (А
1B
5): 1. Для цього в перспективну клітку (1;5) поставимо знак «+», а в інших вершинах багатокутника чергуються знаки «-», «+», «-». Цикл наведено в таблиці.
Тепер необхідно перемістити продукцію в межах побудованого циклу. З вантажів хij що стоять в мінусових клітинах, вибираємо найменше, тобто у = min (1;3) = 60. Додаємо 60 до обсягів вантажів, що стоять в плюсових клітинах і віднімаємо 60 з хij, що стоять в мінусових клітинах. В результаті отримаємо новий опорний план.
Для цього у порожню клітинку А
1B
5 переносимо менше з чисел хij
, які розміщені в клітинках зі знаком «–». Одночасно це саме число хij
додаємо до відповідних чисел, що розміщені в клітинках зі знаком «+», та віднімаємо від чисел, що розміщені в клітинках, позначених знаком «–».
Усі інші заповнені клітинки першої таблиці, які не входили до циклу, переписуємо у другу таблицю без змін. Кількість заповнених клітинок у новій таблиці також має відповідати умові невиродженості плану, тобто дорівнювати (n
+ m
– 1).
Отже, другий опорний план транспортної задачі матиме такий вигляд:
Ai
Bj
ui
b
1 = 110
b
2 = 80
b
3 = 100
b
4=90
b
5=70
b
6=250
а
1 = 250
1
110
4
[-]80
7
9
1
[+]60
0
u
1 = 0
а
2 = 300
2
3
1
100
2
90
4
[-]10
0
[+]100
u
2 = 3
а
3 = 150
2
1
[+]
3
1
4
0
[-]150
u
3 = 3
vj
v
1 =1
v
2 =4
v
3 =-2
v
4 =-1
v
5 =1
v
6 =-3
Перевіримо оптимальність опорного плану. Знайдемо потенціали ui, vi. по зайнятих клітинам таблиці, в яких ui + vi = cij, вважаючи, що u1 = 0.
Опорний план не є оптимальним, тому що існують оцінки вільних клітин для яких ui + vi>cij
(2;1): 3 + 1 > 2
(2;2): 3 + 4 > 3
(3;1): 3 + 1 > 2
(3;2): 3 + 4 > 1
(3;4): 3 + -1 > 1
Вибираємо максимальну оцінку вільної клітини (А
3B
2): 1
Для цього в перспективну клітку (А
3B
2) поставимо знак «+», а в інших вершинах багатокутника чергуються знаки «-», «+», «-». Цикл наведено в таблиці.
З вантажів хij що стоять в мінусових клітинах, вибираємо найменше, тобто у = min (А
2B
5) = 10. Додаємо 10 до обсягів вантажів, що стоять в плюсових клітинах і віднімаємо 10 з Хij, що стоять в мінусових клітинах. В результаті отримаємо новий опорний план.
Ai
Bj
ui
b
1 = 110
b
2 = 80
b
3 = 100
b
4=90
b
5=70
b
6=250
а
1 = 250
1
110
4
[-]70
7
9
1
70
0
[+]
u
1 = 0
а
2 = 300
2
3
1
100
2
90
4
0
110
u
2 = -3
а
3 = 150
2
1
[+]10
3
1
4
0
[-]140
u
3 = -3
vj
v
1 =1
v
2 =4
v
3 =4
v
4 =5
v
5 =1
v
6 =3
Перевіримо оптимальність опорного плану. Знайдемо потенціали ui, vi. по зайнятих клітинам таблиці, в яких ui + vi = cij, вважаючи, що u1 = 0.
Опорний план не є оптимальним, тому що існують оцінки вільних клітин для яких ui + vi>cij
(1;6): 0 + 3 > 0
(3;4): -3 + 5 > 1
Вибираємо максимальну оцінку вільної клітини (А
1B
6): 0
Для цього в перспективну клітку (А
1B
6) поставимо знак «+», а в інших вершинах багатокутника чергуються знаки «-», «+», «-». Цикл наведено в таблиці.
З вантажів хij що стоять в мінусових клітинах, вибираємо найменше, тобто у = min (А
1B
2)=70. Додаємо 70 до обсягів вантажів, що стоять в плюсових клітинах і віднімаємо 70 з Хij, що стоять в мінусових клітинах.
В результаті отримаємо новий опорний план.
Ai
Bj
ui
b
1 = 110
b
2 = 80
b
3 = 100
b
4=90
b
5=70
b
6=250
а
1 = 250
1
110
4
7
9
1
70
0
70
u
1 = 0
а
2 = 300
2
3
1
100
2
[-]90
4
0
[+]110
u
2 = 0
а
3 = 150
2
1
80
3
1
[+]
4
0
[-]70
u
3 = 0
vj
v
1 =1
v
2 =1
v
3 =1
v
4 =2
v
5 =1
v
6 =0
Перевіримо оптимальність опорного плану. Знайдемо потенціали ui, vi. по зайнятих клітинам таблиці, в яких ui + vi = cij, вважаючи, що u1 = 0.
Опорний план не є оптимальним, тому що існують оцінки вільних клітин для яких ui + vi>cij
(3;4): 0 + 2 > 1
Вибираємо максимальну оцінку вільної клітини (А
3B
4): 1
Для цього в перспективну клітку (А
3B
4) поставимо знак «+», а в інших вершинах багатокутника чергуються знаки «-», «+», «-». Цикл наведено в таблиці.
З вантажів хij що стоять в мінусових клітинах, вибираємо найменше, тобто у = min (А
3B
6) =70. Додаємо 70 до обсягів вантажів, що стоять в плюсових клітинах і віднімаємо 70 з Хij, що стоять в мінусових клітинах.
В результаті отримаємо новий опорний план.
Ai
Bj
ui
b
1 = 110
b
2 = 80
b
3 = 100
b
4=90
b
5=70
b
6=250
а
1 = 250
1
110
4
7
9
1
70
0
70
u
1 = 0
а
2 = 300
2
3
1
100
2
20
4
0
180
u
2 = 0
а
3 = 150
2
1
80
3
1
70
4
0
u
3 = -1
vj
v
1 =1
v
2 =2
v
3 =1
v
4 =2
v
5 =1
v
6 =0
Перевіримо оптимальність опорного плану, тобто повторюємо описані раніше дії.
Знайдемо потенціали ui, vi. по зайнятих клітинам таблиці, в яких ui + vi = cij, вважаючи, що u1 = 0.
математичний модель симплекс екстремум
Перевірка останнього плану на оптимальність за допомогою методу потенціалів показує, що він оптимальний.
Розрахуємо значення цільової функції відповідно до другого опорного плану задачі:
За оптимальним планом перевезень загальна вартість перевезень всієї продукції є найменшою і становить 470 грн.
Завдання 4
Знайти графічним методом екстремуми функцій в області, визначеній нерівностями.
.
Розв’язок
Необхідно знайти мінімальне значення цільової функції F = 2X1+4X2 =>min, при системі обмежень:
x1+2x2≥2 (1)
2x1+2x2≤10 (2)
x1+x2=6 (3)
Побудуємо область допустимих рішень, тобто вирішимо графічно систему нерівностей. Для цього побудуємо кожну пряму і визначимо півплощини, задані нерівностями (півплощини позначені штрихом).
Межі області
Цільова функція F(x) =>min
Розглянемо цільову функцію завдання F = 2X1+4X2 =>min.
Побудуємо пряму, що відповідає значенню функції F = 0: F = 2X1+4X2 = 0. Будемо рухати цю пряму паралельним чином. Оскільки нас цікавить мінімальне рішення, тому рухався прямо до першого торкання позначеної області. На графіку ця пряма позначена пунктирною лінією.