Графічний метод та симплекс метод розв’язування задач лінійного програмування
1. Огляд теми
Для вирощування двох сільськогосподарських культур господарство може виділити 60га ріллі, 1890 людино-годин та 240ц діючої речовини добрив. Планується цю площу відвести під ячмінь та соняшник.
Відомі затрати праці, затрати добрив та прибуток в розрахунку на 1 га.
|
Культура |
Затрати праці на 1га, людино-годин |
Затрати добрив на 1 га, ц. 
|
Прибуток з 1 га, грн. |
|
Ячмінь |
26 |
2,5 |
200 |
|
Соняшник |
31,5 |
4,8 |
250 |
Визначити, які площі слід відвести під кожну культуру, щоб отримати максимальний прибуток.
Рішення.
Розробимо економіко-математичну модель задачі:
X1 – площа ячменю;
X2 – площа соняшнику.
Цільова функція (максимальний прибуток) має вигляд:
F = 200Х1 + 250Х2 max
Обмеження задачі:
1-ше обмеження характеризує використання площі ріллі
Х1 + Х2 <= 60
2-ге обмеження стосується використання затрат праці
26Х1 + 31,5Х2 <= 1890
3-тє обмеження описує використання добрив
2,5Х1 + 4,8Х2 <= 240
В задачі слід врахувати умову невід’ємності змінних: Х1 та Х2 >= 0
Обмеження задачі запишемо у вигляді системи рівнянь:
На системі координат намалюємо відповідні прямі:
I. Х1=0, Х2=60; Х2=0, Х1=60
II. Х1=0, Х2=1890/31,5=60; Х2=0, Х1=1890/26=72,7
III. Х1=0, Х2=240/4,8=50; Х2=0, Х1=240/2,5=96
Рис. 1.
Кожна пряма розділила площину на дві напівплощини. Координати точок однієї з напівплощин задовольняє умову відповідної нерівності (всі точки цієї напівплощини, підставлені в нерівність не заперечують знаку), другої – ні. Щоб визначити напівплощину рішень, необхідно взяти будь-яку точку, яка належить до однієї з напівплощ, та перевірити, чи задовольняють її координати даній нерівності. Якщо координати взятої точки задовольняють умову відповідної нерівності, то напівплощина, якій належить точка, є напівплощиною рішень; інакше – друга напівплощина.
Знайдемо, наприклад, напівплощину рішень, яка визначається нерівністю
Х1+Х2 £60. Для цього, побудувавши пряму Х1 Х2 =60 (на рис.1 вона І), візьмемо будь-яку точку, яка належить одній з напівплощ, наприклад точку О(0;0). Координати цієї точки задовольняють нерівності 0+0£60; Значить, напівплощина, якій належить точка О(0;0), визначається нерівністю Х1+Х2£60, Що показано стрілками на рис.1.
Перехрещення всіх отриманих напівплощ рішень визначає багатокутник рішень задачі (область можливих значень). Точки цієї області задовольняють всім обмеженням задачі.
0АВС – багатокутник рішень.
Необхідно знайти точку, яка належить чотирикутнику 0АВС, в якій цільова функція F Приймає максимальне значення. Для цього будується вектор
(200;250), координатами якого є коефіцієнти в цільовій функції при відповідних змінних, та до нього проводиться перпендикуляр.
Переміщуємо перпендикуляр за напрямом, який вказує вектор:
– в першій точці дотику перпендикуляра з багатокутником рішень буде точка Min;
– в останній точці дотику з багатокутником рішень буде точка max.
Отже в точці В цільова функція має максимальне значення.
Щоб визначити точні координати точки В, необхідно розв’язати систему з двох рівнянь, лінії яких утворили цю точку. Точка В лежить на перетині першої та третьої ліній, тому беруться саме перше та третє рівняння.
З першого рівняння вираз Х2=60-Х1 та підставимо в друге рівняння:
2,5Х1+4,8(60-Х1)=240
2,5Х1+288-4,8Х1=240
2,3Х1=48
Х1=20,87
Х2=60-20,87=39,13
Таким чином точка В(20.87;39.13) – точка max, в якій значення цільової функції дорівнює:
Щоб господарству отримати максимальний прибуток в розмірі 13956,5 грн., необхідно посіяти 20,87 га ячменю та 39,13 га соняшнику.
2. Фермер може вирощувати 4 культури на площі 80га. Він вже вклав угоди на продаж певної продукції (обсяг продаж) і може придбати 250ц мінеральних добрив.
Площа просапних культур (соняшник, цукровий буряк, картопля, кукурудза) повинна бути 20 га.
Витрати праці та добрив, прибуток з 1 га наведено в таблиці.
|
Культури |
Урожайність, Ц/га |
Обсяг продаж, Ц |
Витрати добрив на 1га, ц |
Прибуток, Грн./га |
|
Пшениця |
30 |
– |
3,5 |
160 |
|
Ячмінь |
25 |
– |
3 |
120 |
|
Просо |
20 |
200 |
3 |
100 |
|
Картопля |
330 |
– |
5 |
260 |
Визначити, які площі слід відвести під кожну культуру, щоб отримати максимальний прибуток. Розробити економіко-математичну модель та розв’язати задачу.
Рішення
Розробимо економіко-математичну модель задачі.
Змінні:
Х1 – площа пшениці;
Х2 – площа ячменю;
Х3 – площа проса;
Х4 – площа картоплі.
Цільова функція (максимальний прибуток) буде мати вигляд:
F=160X1+120X2+100X3+260X4 à max
На змінні задачі накладені обмеження:
1-ше обмеження характеризує використання площі ріллі
Х1 + Х2 + Х3 + Х4 <= 80
2-ге обмеження стосується угоди на продаж проса ( 200 ц):
20 Х 3 >= 200
3-тє обмеження описує використання добрив
3,5Х1 + 3Х2 + 3Х3 + 5Х4 <= 250
4-те обмеження описує умову, що площа картоплі повинна бути 20 га:
Х4 = 20
Запишемо задачу в канонічному вигляді (в кожну нерівність системи обмежень вводяться додаткові змінні, в цільову функцію додаткові змінні вводяться з коефіцієнтом 0).
Цільова функція має вигляд:
F=160×X1+120×X2+100×X3+260×X4+0×S5+0×S6+0×S7à max
Обмеження задачі запишемо у векторному вигляді:
; 
; 
; 
; 
; 
; 
; 
Серед всіх векторів лише два одиничних (А5 та А7). В друге та четверте обмеження необхідно ввести штучні змінні. Запишемо обмеження задачі та цільову функцію з штучними змінними:
F=160×X1+120×X2+100×X3+260×X4+0×S5+0×S6+0×S7-M×Y1-M×Y2 à max
X – основні змінні, S – додаткові змінні, Y – штучні змінні
Рішення задач симплексним методом здійснюється в таблицях, заповнимо першу таблицю.
Ітерація 1
|
Базис |
C(j) |
X1 |
X2 |
X3 |
X4 |
S1 |
S2 |
Y1 |
S3 |
Y2 |
B(i) |
|
|
160 |
120 |
100 |
260 |
0 |
0 |
-M |
0 |
-M |
||||
|
S1 |
0 |
1 |
1 |
1 |
1 |
1 |
0 |
0 |
0 |
0 |
80 |
80 |
|
Y1 |
-M |
0 |
0 |
20 |
0 |
0 |
-1 |
1 |
0 |
0 |
200 |
10 |
|
S3 |
0 |
3,5 |
3 |
3 |
5 |
0 |
0 |
0 |
1 |
0 |
250 |
83,33 |
|
Y2 |
-M |
0 |
0 |
0 |
1 |
0 |
0 |
0 |
0 |
1 |
20 |
Inf |
|
*Big M |
-160 0 |
-120 0 |
-100 -20 |
-260 -1 |
0 0 |
0 1 |
0 0 |
0 0 |
0 0 |
0 -220 |
Поточне значення цільової функції (Max) = 0+(-220 Big M)
(в базис вводимо змінну Х3; виводимо змінну Y1),
Inf – дія не виконується, тому що ділити на 0 неможливо
Система обмежень задачі записується в табличному виді (Ітерація 1): в “Базис” записуються змінні, які утворили систему одиничничних векторів (для першої таблиці), в стовпчик С(J) – коефіцієнти в цільовій функції при змінних, які ввійшли в Базис, в стовпчики Х1, Х2, Х3, Х4, S1, S2, Y1, Y2 – відповідні коефіцієнти при цих змінних в кожному обмеженні; стовпчик B(i) – праві частини рівнянь.
Індексний рядок 
розраховується за правилом – кожне значення стовпчика С(j) множиться на відповідний елемент розрахункового стовпчика, що отримано в результаті множення додається і з цієї суми віднімається коефіцієнт при змінній в цільовій функції, що отримано: число без М записується в рядок 
, число з М записується в рядок *Big M.
Наприклад:
Розрахуємо індексний рядок для стовпця Х1:
Розрахуємо індексний рядок для стовпця Х3:
Задача має оптимальне рішення, коли в індексному рядку не існує від’ємних елементів при рішенні задач на max.
Якщо умова оптимальності не виконується, необхідно визначити генеральний (направляючий) елемент, який лежить на перетині генерального стовпця та генерального рядка, та перейти до нової таблиці. Визначається направляючий стовпець, на який вказує найбільше по абсолютній величині від’ємне значення в індексному рядку. Потім визначається направляючий рядок: необхідно поділити кожне значення стовпця B(I) на відповідне значення генерального стовпця і найменше значення, яке буде отримано, вказуватиме на направляючий рядок. При визначенні генерального рядка неможливо ділити на нуль та від’ємний елемент.
Отже: Х3 – генеральний стовпець;
Рядок 2 – генеральний рядок;
20 – генеральний елемент.
Правила переходу до нової таблиці:
1. Замість генерального елемента записується 1, замість всіх інших елементів генерального стовпця 0;
2. Всі елементи генерального рядка діляться на генеральний елемент;
3. Всі інші елементи таблиці розраховуються за правилом прямокутника:
Якщо з базису виходить деяка штучна змінна, то з цього моменту відповідний стовпець не розраховується.
Розрахуємо другу таблицю (ітерація 2)
Розглянемо як за правилом прямокутника визначається декілька значень:
1) 
2) 
3) 
4) 
Ітерація 2
|
Базис |
C(j) |
X1 |
X2 |
X3 |
X4 |
S1 |
S2 |
Y1 |
S3 |
Y2 |
B(i) |
|
|
160 |
120 |
100 |
260 |
0 |
0 |
-M |
0 |
-M |
||||
|
S1 |
0 |
1 |
1 |
0 |
1 |
1 |
0,05 |
0 |
0 |
70 |
70 |
|
|
X3 |
100 |
0 |
0 |
1 |
0 |
0 |
-0,05 |
0 |
0 |
10 |
Inf |
|
|
S3 |
0 |
3,5 |
3 |
0 |
5 |
0 |
0,15 |
1 |
0 |
220 |
44 |
|
|
Y2 |
-M |
0 |
0 |
0 |
1 |
0 |
0 |
0 |
1 |
20 |
20 |
|
|
*Big M |
-160 0 |
-120 0 |
0 0 |
-260 -1 |
0 0 |
5 0 |
0 0 |
0 0 |
1000 -20 |
Поточне значення цільової функції (Max) =1000+(-20 Big M)
(в базис вводимо змінну Х4; виводимо змінну Y2)
Задача ще не має оптимального рішення, слід перейти до нової таблиці (ітерація 3).
Ітерація 3
|
Базис |
C(j) |
X1 |
X2 |
X3 |
X4 |
S1 |
S2 |
Y2 |
S3 |
Y4 |
B(i) |
|
|
160 |
120 |
100 |
260 |
0 |
0 |
-M |
0 |
-M |
||||
|
S1 |
0 |
1 |
1 |
0 |
0 |
1 |
0,05 |
0 |
50 |
50 |
||
|
X3 |
100 |
0 |
0 |
1 |
0 |
0 |
-0,05 |
0 |
10 |
Inf |
||
|
S3 |
0 |
3,5 |
3 |
0 |
0 |
0 |
0,15 |
1 |
120 |
34,29 |
||
|
X4 |
260 |
0 |
0 |
0 |
1 |
0 |
0 |
0 |
20 |
Inf |
||
|
|
-160 |
-120 |
0 |
0 |
0 |
-5 |
0 |
6200 |
Поточне значення цільової функції (Max) =6200
(в базис вводимо змінну Х1; виводимо змінну S3)
Ітерація 4
|
Базис |
C(j) |
X1 |
X2 |
X3 |
X4 |
S1 |
S2 |
Y2 |
S3 |
Y4 |
B(i) |
|
|
160 |
120 |
100 |
260 |
0 |
0 |
-M |
0 |
-M |
||||
|
S1 |
0 |
0 |
0,143 |
0 |
0 |
1 |
0,007 |
-0,286 |
15,71 |
0 |
||
|
X3 |
100 |
0 |
0 |
1 |
0 |
0 |
-0,05 |
0 |
10 |
0 |
||
|
X1 |
160 |
1 |
0,857 |
0 |
0 |
0 |
0,043 |
0,286 |
34,29 |
0 |
||
|
X4 |
260 |
0 |
0 |
0 |
1 |
0 |
0 |
0 |
20 |
0 |
||
|
|
0 |
17,1 |
0 |
0 |
0 |
1,86 |
45,7 |
11685,7 |
(Max) Оптимальна величина ЦФ=11685,7
Задача має оптимальне рішення, так як в індексному рядку не існує від’ємних елементів (виконується умова оптимальності).
Щоб фермеру отримати максимальний прибуток в розмірі 11685,7 грн., необхідно посіяти 34,29 га пшениці (Х1), 10 га проса (Х3), 20 га картоплі (Х4).
При такому плані виробництва залишається незасіяна рілля в кількості 15,71га (S1); добрива та трудові ресурси будуть використані повністю (в стовпчику „Базис” нема змінних S2 та S3).
3. Рекомендована література
Курносов А. П., Сысоев И. А. Вычислительная техника т экономико-математические методы в сельском хозяйстве. – М., 1989. Кузнецов Ю. Н., Кузобов В. И., Ермольев Ю. М. Математическое программирование. – М.: Высш. шк., 1976. Математическое программирование в примерах и задачах. М.: Высшая школа, 1986. Исследование операций в экономике: Учебн. пособие для вузов/ Н. Ш.Кремер, Б. А.Путко, И. М.Тришин. М. Н.Фридман; Под ред. проф. Н. Ш. Кремера. – М.: Банки и биржи, ЮНИТИ, 1997. Акулич И. Л. Математическое программирование в примерах и задачах. – М.: Высш. Шк.», 1986, – 319 с . Ляшенко И. Н. Линейное и нелинейное программирование. – і К.: Вищашк., 1975,-371 с.
· Додаткова
1. Математическое моделирование экономических процессов в сельском хозяйстве/ Гатаулин А. М. и др.; Под ред. А. М.Гатаулина. – М.: Агропромиздат, 1990. – 432с.:ил.
2. Эддоус М., Стэнфилд Р. Методы принятия решений/ Пер. с англ. под ред. член-корр. РАН И. И.Елисеевой. – М.: Аудит, ЮНИТИ, 1997. – 590с.
Крушевский А. В., Шевцов К. И. Математическое программирование и моделирование в экономике.: Учеб. пособие для вузов. – Киев: Высшая школа. Головное изд-во, 1979. – 456с. Курицкий Б. Я. Поиск оптимальных решений средствами Excel 7.0. – СПб.: ВНV – Санкт-Петербург, 1997. – 384с., ил. Ляшенко И. Н. Лінійне та нелінійне програмування. – К.: Вища шк., 1975. Степанюк В. В. Методи математичного програмування. – К.: Вища шк., 1984. Кузнецов Ю. Н., Кудрявцев В. И. Математическое программирование. – М., 1980. Франс Дж. и др. Математические модели в сельском хозяйстве. М.: Агропромиздат, 1987 Кравченко Р. Г. Математическое моделирование в сельском хозяйстве. М.:Колос, 1978. Кузнецов Ю. Н. Математические модели в с/х. М.: Высшая школа, 1981 Карпенко А. ф. Практикум по математическому моделированию экономических агропромышленных процессов в сельском хозяйстве. М.: Финансы и статистика, 1985.
Ви прочитали: "Графічний метод та симплекс метод розв’язування задач…"Читати далі