- •Математичне програмування
- •0305 “Економіка та підприємництво” та 0306 „Менеджмент і адміністрування” Видання друге, доповнене, допрацьоване
- •Розділ 1. Загальні методичні вказівки з вивчення дисципліни
- •Та питання для самостійної перевірки знань Модуль 1. Лінійне програмування
- •Модуль 2. Двоїсті задачі, нелінійне та інші види математичного програмування
- •Розділ 3. Завдання для контрольної роботи
- •Завдання 2. Симплексний метод розв'язання задач лінійного програмування
- •Завдання 3. Двоїсті задачі лінійного програмування
- •Примітка. Розрахунки виконати для всіх небазисних змінни кінцевої симплексної таблиці прямої задачі.
- •Скласти план вантажних перевезень з мінімальним вантажообігом.
- •Площі попередників озимої пшениці, га
- •Площа сортів озимої пшениці, га
- •Середня урожайність озимої пшениці за попередниками, ц з 1 га
- •Завдання 5. Задачі нелінійного програмування
- •Визначимо головні мінори, починаючи з 2-го порядку
- •Отже, головні мінори визначаються множником
- •Тестові завдання Модуль 1. Лінійне програмування
- •1.12. В частинному розв’язку системи рівнянь при
- •1.13. В частинному розв’язку системи рівнянь при
- •1.14. Базисні невідомі, які складають допустимий розв’язок задачі лінійного програмування, можуть бути:
- •1.16. Небазисні невідомі задачі лінійного програмування:
- •1.17. Канонічна форма задачі лінійного програмування представляє собою систему:
- •1.18. Приведення загальної задачі лінійного програмування до канонічної форми виконується шляхом введення в кожне обмеження-нерівність по одній невідомій, яка називається:
- •Модуль 2. Двоїсті задачі, нелінійне та інші види математичного програмування
- •Відомість виконання тестових завдань
- •Приклад використання Excel для розв’язання симплексних задач лінійного програмування (лп)
- •Приклад використання Excel для розв’язання транспортних задач лінійного програмування (тлп)
- •Список рекомендованої літератури Підручники та навчальні посібники
- •Електронні ресурси
- •Володимир Петрович марченко Надія Іванівна гринчак Математичне програмування
- •0305 “Економіка та підприємництво” та 0306 „Менеджмент і адміністрування”
Завдання 2. Симплексний метод розв'язання задач лінійного програмування
Приклад 2.1. В господарстві для вирощування кукурудзи на зерно та ячменю виділено 400 га ріллі, 18000 людино-годин та 1800 ц мінеральних добрив. Вихід концентрованих кормів та затрати виробничих ресурсів (в розрахунку на 1 га) наведені нижче:
Показники |
Кукурудза на зерно |
Ячмінь |
Затрати праці, людино-годин |
50 |
30 |
Внесення мінеральних добрив, ц |
6 |
3 |
Вихід кормів, ц к. од |
90 |
50 |
Знайти посівні площі зернофуражних культур для отримання максимальної кількості концентрованих кормів.
Розв'язання. Для формулювання економіко-математичної моделі задачі введемо такі позначення:
х1 - площа кукурудзи на зерно, га
х2 - площа ячменю, га
Zmax – обсяг виробництва кормів, ц к. од.
Тоді умови задачі в математичній формі можна записати так:
1. Обмеження щодо використання ріллі:
х1 + х2 < 400
2. Обмеження щодо використання трудових ресурсів:
50х1 + 30х2 < 18000
3. Обмеження щодо використання мінеральних добрив:
6х1 + 3х2 < 1800
4. Обмеження на знак змінних:
х1 0, х2 0
Критерій оптимальності – виробництво максимальної кількості концентрованих кормів -
Zmax = 90х1 + 50х2
Запишемо задачу в канонічній формі, тобто перетворимо нерівності в системі обмежень в рівняння. Для цього в ліву частину кожної нерівності введемо по одній невід'ємній додатковій змінній, які в умовах даної задачі мають такий економічний зміст:
S1 - кількість невикористаної площі ріллі, га;
S2 - кількість невикористаних трудових ресурсів,
людино - годин;
S3 - кількість невикористаних мінеральних добрив, ц.
В цільову функцію Zmax додаткові змінні вводяться з нульовою оцінкою. Тоді,
Zmax = 0 - ( - 90 х1 - 50 х2)
х1 + х2 + S1 = 400
50 х1 + 30 х2+ S2 = 18000
6 х1 + 3 х2 + S3 = 1800
х1 > 0, х2 > 0; S1 > 0; S2 > 0; S3 > 0;
Якщо змінні х1 та х2 прирівняти до нуля, то отримуємо допустимий базисний розв'язок задачі: х1 = 0, х2 = 0, S1 = 400,
S2 = 18000, S3 = 1800 та max = 0. В даному випадку х1 та х2, називаються небазисними змінними, а S1, S2, та S3 - базисними змінними.
Розв'язання задачі продовжимо в симплексних таблицях, записавши в симплексну таблицю 1 отриманий допустимий базисний розв'язок задачі .
Симплексна таблиця 1
Базисні змінні |
Значення базисних змінних |
х1 |
х2 |
S1 |
S2 |
S3 |
L |
S1 |
400 |
1 |
1 |
1 |
0 |
0 |
400 |
S2 |
18000 |
50 |
30 |
0 |
1 |
0 |
360 |
S3 |
1800 |
6 |
3 |
0 |
0 |
1 |
300 |
max |
0 |
-90 |
-50 |
0 |
0 |
0 |
|
Умови оптимальності розв'язку задач симплексним методом:
1. При знаходженні максимального значення цільової функції розв'язок задачі буде оптимальним, якщо всі небазисні змінні в max - рядку мають невід'ємні коефіцієнти або дорівнюють нулю (t > 0).
2. При знаходженні мінімального значення цільової функції розв'язок задачі буде оптимальним, якщо всі небазисні змінні в min - рядку мають від'ємні значення або дорівнюють нулю ( t < 0).
В симплексній таблиці 1 небазисні змінні х1 та х2 в Z - рядку мають від'ємні коефіцієнти ( відповідно -90 та -50 ), тому розв'язок задачі не оптимальний.
Цільова функція буде наближатись до екстремального значення тоді, коли в базисний розв'язок задачі буде введена небазисна змінна, яка в Z-рядку має від'ємний коефіцієнт, причому тим скоріше, чим більший за абсолютним значенням (модулем) цей від'ємний коефіцієнт. В даному випадку цією небазисною змінною є змінна х1 (-90). Стовпчик симплексної таблиці, в якій знаходиться така змінна, називається розв'язуючим. Для того, щоб в розв'язок задачі ввести цю змінну (х1), потрібно з розв'язку вивести одну з базисних змінних ( S1, S2 або S3). Для цього визначимо відношення значень базисних змінних до додатних елементів розв'язуючого стовпчика:
min {400 / 1= 400; 18000 / 50 = 360 ; 1800 / 6 = 300 } = 300
Змінною, яка виводиться з базисного розв'язку, буде та, для якої розраховане відношення буде мінімальним. В симплексній таблиці 1 мінімальне відношення (300) належить 3-му рядку, якому відповідає змінна S3. Такий рядок називається розв'язуючим.
Елемент симплексної таблиці на перетині розв'язуючого стовпчика та розв'язуючого рядка називається розв'язуючим (6).
Пошук нового базисного розв'язку здійснюється за допомогою методу повних виключень Жордана - Гаусса за такими обчислювальними процедурами:
1. Формування розв'язуючого рівняння (рядка):
попередній розв'язуючий рядок
новий розв'язуючий рядок =
розв'язуючий елемент
Новий 3-й рядок = (1800630 01) / 6 = (30010.5000.167)
2. Формування всіх інших рівнянь (рядків), включаючи і Z-рівняння:
Новий рядок = попередній рядок - (новий розв'язуючий рядок) (коефіцієнт розв'язуючої колонки попереднього рядка)
1-й рядок |
|
|
|||||||||||
Попередній 1-й рядок - |
(400 |
1 |
1 |
1 |
0 |
0)- |
|||||||
новий розв'язуючий рядок |
-(300 |
1 |
0.5 |
0 |
0 |
0.167)(1) |
|||||||
(1) = новий 1-й рядок |
=(100 |
0 |
0.5 |
1 |
0 |
-0.167) |
|||||||
2-й рядок |
|||||||||||||
Попередній 2-й рядок - |
(18000 |
50 |
30 |
0 |
1 |
0) - |
|||||||
новий розв'язуючий рядок |
-(300 |
1 |
0.5 |
0 |
0 |
0.167) (50) |
|||||||
(50) = новий 2-й рядок |
=(3000 |
0 |
5 |
0 |
1 |
- 8.333) |
|||||||
Z рядок |
|||||||||||||
Попередній Z рядок - |
(0 |
-90 |
-50 |
0 |
0 |
0) - |
|||||||
новий розв'язуючий рядок |
-(300 |
1 |
0.5 |
0 |
0 |
0.167) х (-90) |
|||||||
(-90) = новий Z - рядок |
=(27000 |
0 |
-5 |
0 |
0 |
15) |
Нова симплексна таблиця має такий вигляд (табл. 2). Зазначимо, що в базисний розв'язок замість змінної S3 введена змінна Х1.
Симплексна таблиця 2
Базисні змінні |
Значення базисних змінних |
Х1 |
Х2 |
S1 |
S2 |
S3 |
L |
S1 |
100 |
0 |
0.5 |
1 |
0 |
-0.167 |
200 |
S2 |
3000 |
0 |
5 |
0 |
1 |
-8.333 |
600 |
Х1 |
300 |
1 |
0.5 |
0 |
0 |
0.167 |
600 |
Zmax |
27000 |
0 |
-5 |
0 |
0 |
15 |
|
В симплексній таблиці 2 одержано новий базисний розв'язок: Zmax = 27000,
Х1 = 300, Х2 = 0, S1 = 100, S2 = 3000, S3 = 0.
Значення цільової функції збільшилось з 0 до 27000. Це пояснюється тим, що в новому розв'язку площа кукурудзи на зерно становить 300 га (Х1 = 300), кожний з яких дає 90 ц к. од. Тому значення цільової функції дорівнює
Z = 90 300 = 27000.
В зв'язку з тим, що небазисна змінна х2 в Z-рядку має від'ємний коефіцієнт (-5), базисний розв'язок у симплексній таблиці 2 не оптимальний.
Продовжимо розв'язання задачі. В симплексній таблиці 2 стовпчик "Х2" є розв'язуючим. Визначимо відношення значень базисних змінних до додатних елементів розв'язуючого стовпчика:
min {100 / 0.5 = 200; 3000 / 5 = 600; 300 / 0,5 = 600} = 200 ,
тому до нового базисного розв'язку замість S1 вводимо Х2. Розв'язуючим елементом симплексної таблиці 2 буде 0.5. Пошук нового базисного розв'язку здійснюємо знову за допомогою обчислювальних операцій методу Жордана-Гаусса:
Новий 1 -й рядок
(10000.51 0- 0.167) / 0,5 = (2000120- 0.333)
Новий 2-й рядок |
||||||
Попередній 2-й рядок - |
(3000 |
0 |
5 |
0 |
1 |
- 8.333) - |
-новий розв'язуючий рядок |
-(200 |
0 |
1 |
2 |
0 - 0.333) (5) |
|
(5) = новий 2-й рядок |
=(2000 |
0 |
0 |
-10 |
1 |
- 6.667) |
Новий 3-й рядок |
||||||
Попередній 3-й рядок - |
(300 |
1 |
0.5 |
0 |
0 |
0.167) - |
-новий розв'язуючий рядок |
-(200 |
0 |
1 |
2 |
0 |
- 0.333 (0.5) |
(0.5) = новий 3-й рядок |
=(200 |
1 |
0 |
-1 |
0 |
0.333) |
Новий Z рядок |
||||||
Попередній Z рядок - |
(27000 |
0 |
-5 |
0 |
0 |
15) - |
-новий розв'язуючий рядок |
-(200 |
0 |
1 |
2 |
0 |
- 0.333) (-5) |
(-5) = новий Z - рядок |
=(28000 |
0 |
0 |
10 |
0 |
13.333) |
Запишемо симплексну таблицю 3.
Симплексна таблиця 3
Базисні змінні |
Значення базисних змінних |
Х1 |
Х2 |
S1 |
S2 |
S3 |
Х2 |
200 |
0 |
1 |
2 |
0 |
-0.333 |
S2 |
2000 |
0 |
0 |
-10 |
1 |
-6.667 |
Х1 |
200 |
1 |
0 |
-1 |
0 |
0.333 |
Zmax |
28000 |
0 |
0 |
10 |
0 |
13.333 |
В симплексній таблиці 3 маємо новий базисний розв'язок: Z = 28000,
х1 = 200, х2 = 200, S1 = 0, S2 = 2000, S3 = 0. В Zmax-рядку відсутні від'ємні елементи, тому отриманий базисний розв'язок є оптимальним. Розв'язання задачі закінчено.
Висновки. Для виробництва максимальної кількості концентрованих кормів в господарстві потрібно вирощувати кукурудзу на зерно 200 га (х1=200) та ячменю 200 га (х2=200). Площа ріллі та мінеральні добрива використовуються повністю (S1=0, S3=0), а невикористані трудові ресурси становлять 2000 людино-годин (S2=2000). Кількість кормів дорівнює 28000 ц к.од. (Zmax=28000).
Зауваження 1. Якщо розв'язуючий стовпчик має тільки від'ємні коефіцієнти і не можна знайти розв'язуючий рядок, то цільова функція не обмежена зверху (при знаходженні максимуму цільової функції) або знизу (при знаходженні мінімуму цільової функції) на множині допустимих розв'язків. Треба змінити умови задачі.
Зауваження 2. Якщо при визначенні розв'язуючого стовпчика в Z - рядку є однакові коефіцієнти, то вибирається будь-який з них.
Зауваження 3. Якщо при визначенні розв'язуючого рядка є однакові симплексні відношення, то вибирається будь-яке з них.
З
Х1
Задача 2. Для вирощування озимої пшениці, кукурудзи на зерно та ячменю виділено 400 га ріллі, 24000 людино-годин трудових ресурсів та 1600 ц мінеральних добрив. Урожайність, затрати праці та мінеральних добрив наведені в таблиці 2.1.
Таблиця 2.1
С.-г. культури |
Варіанти *) |
Затрати праці на 1 га, людино-годин |
Внесення мінеральних добрив на 1 га, ц |
Урожайність, ц з 1 га |
Озима пшениця |
Для всіх варіантів |
40 |
5 |
50 |
Кукурудза на зерно |
0 |
40 |
4 |
40 |
1 |
50 |
5 |
50 |
|
2 |
60 |
8 |
64 |
|
3 |
75 |
10 |
80 |
|
4 |
80 |
4 |
60 |
|
5 |
40 |
5 |
45 |
|
6 |
50 |
8 |
59 |
|
7 |
60 |
10 |
70 |
|
8 |
75 |
4 |
55 |
|
9 |
80 |
5 |
65 |
|
Ячмінь |
0 |
20 |
2 |
28 |
1 |
24 |
2.5 |
31 |
|
2 |
25 |
4 |
36 |
|
3 |
30 |
2 |
33 |
|
4 |
32 |
2.5 |
35 |
|
5 |
20 |
4 |
33 |
|
6 |
24 |
2 |
30 |
|
7 |
25 |
2.5 |
32 |
|
8 |
30 |
4 |
38 |
|
9 |
32 |
2 |
34 |
*) Варіант технології вирощування кукурудзи на зерно вибирається за передостанньою цифрою шифру (номера залікової книжки), Р, а варіант технології вирощування ячменю - за кінцевою цифрою шифру, К..
Визначити посівні площі сільськогосподарських культур з метою максимального виробництва зерна.