4. Особливості алгоритму м -методу
В розглянутій вище задачі всі обмеження були представлені нерівностями виду “<=” (не більше). Однак дуже часто зустрічаються задачі з обмеженнями протилежного знака “>=” (не менше), а також “=”, тобто обмеження, умови яких сформульовані у виді рівняння. Вирахувальну процедуру симплексного метода, який застосовується для розв’язання планово-економічних задач, в яких обмеження задані нерівностями типу “>=” і рівняннями типу “=” розглянемо на прикладі конкретної задачі.
Задача. Для корови живою вагою 450 кг і добовим надоєм молока 10 л необхідно скласти кормовий раціон, який би задовільняв біологічні потреби в поживних речовинах і одночасно мав мінімальну собівартість.
Корова на добу повинна одержувати не менше 9 кормових одиниць, 960 г перетравного протеїну і 400 мг каротину.
В господарстві є в наявності корми, поживність і собівартість яких наведені в таблиці 6.
Ця задача відноситься до типу планово-економічних, пов’язаних з пошуком найбільш ефективної комбінації ресурсів, необхідних для виробництва заданих обсягів продуктів. Однаковий за поживністю кормовий раціон може складатися із різного співвідношення наявних в господарстві кормів і тому є можливість складати багато варіантів раціонів, із яких можна знайти оптимальний.
Таблиця 6 – Перелік кормів, їх поживність і собівартість
Корми |
Вміст в 1 кг корму |
Собівартість 1 кг корму, коп. |
||
Кормових одиниць, кг |
Перетравного протеїну, г |
Каротину, мг |
||
Концентрати |
1,0 |
100,0 |
2 |
30,0 |
Сіно природних кормових угідь |
0,4 |
50,0 |
20 |
18,0 |
Силос кукурудзяний |
0,2 |
10 |
15 |
15,0 |
Кормові буряки |
0,2 |
15 |
2 |
10,0 |
Припустимо, що в кормовий раціон ввійде концентратів х1 кг, сіна природних кормових угідь х2 кг, силосу кукурудзяного х3 кг і кормових буряків х4 кг. Тоді умови задачі будуть виражені наступною системою нерівностей і рівнянь.
х1+ 0,4х2 + 0,2х3 + 0,2х4 >= 9
100х1 + 50х2 + 10х3 + 15х4 = 960
2х1 + 20х2 + 15х3 + 2х4 >= 400
Друге обмеження системи задано в вигляді рівняння. Це означає, що вміст в кормах перетравного протеїну повинен бути використаний точно в тій кількості, яка введена в задачі.
Мета задачі - мінімізувати наступну лінійну функцію:
Zmin = 30х1 + 18х2 + 15х3 + 10х4
Щоби розв’язати цю задачу, її необхідно звести до канонічного виду (системи рівнянь). Це робиться шляхом введення в першу і третю нерівності додаткових змінних із знаком “—“ (мінус).
х1+ 0,4х2 + 0,2х3 + 0,2х4 – х5 = 9
100х1 + 50х2 + 10х3 + 15х4 = 960
2х1 + 20х2 + 15х3 + 2х4 – х6 = 400
В цій системі рівнянь х5 означає величину, на яку вміст кормових одиниць в раціоні перевищить мінімум рівний 9, а х6 – величину, на яку більше каротину в раціоні проти мінімума (400 мг).
В друге рівняння (рівняння за вмістом перетравного протеїну) додаткова змінна із своїм коефіцієнтом не введена, поскільки в умові задачі необхідно точно задовільнити цю вимогу.
Розв’язати систему з від’ємними додатковими змінними дуже важко. Вище наведена система рівнянь з додатковими змінними має безмежну множину розв’язків, поскільки в ній число рівнянь є меншим числа невідомих і ця система задовільняється при умові: х1 = 0; х2 = 0; х3 = 0; х4 = 0, х5 = -9; х6 = -370, де х5 <= 0 і х6 <=0, а ці змінні згідно умови не можуть бути від’ємними, поскільки однією із основних вимог теорії лінійного програмування є невід’ємність змінних величин.
Щоби вийти із цього положення, в кожне рівняння, яке задане умовами задачі, або яке має додаткову змінну з від’ємним коефіцієнтом, вводяться штучні змінні з додатніми коефіцієнтами. Позначимо їх наступними символами: y1, y2, y3. При побудові симплексної таблиці штучні змінні приймаються в якості базисних. Зауважимо, що введення штучних змінних не можна змішувати з прийомом включення додаткових змінних у випадку перет-ворення в рівняння нерівностей типу “<=” (не більше).
Додаткові змінні, введені з метою перетворення нерівностей типу “<=” в рівняння, не підлягають виключенню. Вони розглядаються, як рівноправні з основними змінними, але в лінійну форму входять з нульовими коефіцієнтами.
В результаті включення штучних змінних в систему рівнянь, вона буде мати наступний вид:
х1+ 0,4х2 + 0,2х3 + 0,2х4 – х5 + y1 = 9
100х1 + 50х2 + 10х3 + 15х4 + y2 = 960
2х1 + 20х2 + 15х3 + 2х4 – х6 + y3 = 400
Умова невід’ємності змінних відноситься не тільки до основних і додаткових змінних, але й до штучних змінних. Тому для даної системи вона запишеться так:
х1 >= 0; х2 >= 0; х3 >= 0; х4 >= 0; х5 >= 0; х6 >= 0; y1 >= 0; y2 >=0; y3 >= 0.
Очевидним розв’язком вище наведеної системи рівнянь є:
y1 = 9; y2 = 960; y3 = 400; х1 = 0; х2 = 0; х3 = 0; х4 = 0; х5 = 0; х6 = 0.
Штучні змінні не можуть входити в оптимальний розв’язок і тому в процесі розв’язування задачі вони повинні бути замінені основними або додатковими змінними. Щоби ці змінні не ввійшли в розв’язок задачі, коефіцієнтам при них надають довільно великі значення, які перевищують будь-яку величину, з якою їх прийшлося б порівнювати в процесі розв’язування задачі. Це гарантує, що штучні змінні будуть виключені із програми, не ввійдуть в оптимальний розв’язок і не спотворять її економічного змісту. Вони тільки полегшують знаходження оптимальної програми. Коефіцієнти штучних змінних в лінійній функції позначаються символом “М”. При розв’язанні задачі на максимум число “М” вводиться в функціонал з від’ємним знаком, а при знаходженні мінімального результату воно вводиться з позитивним знаком.
Складаємо першу симплексну таблицю, в яку записується перший розв’язок. Він представляє собою перший опорний план, який складається із штучних змінних відповідних рівнянь з кормових одиниць, перетравного протеїну і каротину.
В першій симплексній таблиці крім індексного рядка “m+1” є ще рядок “m+2”. Щоби його заповнити, необхідно по кожному стовпцю додати цифри рядків, в яких у базисному стовпцю є штучні змінні і одержану суму записують у відповідну клітку рядка “m+2”.
Таблиця 7 – Перша симплексна таблиця
-
I
Базисні змінні
Сj
Вільні члени
30
18
15
10
0
0
Х1
Х2
Х3
Х4
Х5
Х6
1
1y1
M
9
0,4
0,2
0,2
-1
0
2
y2
M
960
100
50
10
15
0
0
3
y3
M
400
2
20
15
2
0
-1
M + 1
0
-30
-18
-15
-10
0
0
M + 2
103
70,4
25,2
17,2
-1
-1
Таблицю 7 обробляють так само, як і кожну іншу симплексну таблицю, але з тією різницею, що спочатку необхідно вивести із базису штучні змінні. Критерієм для включення в базис основної або додаткової змінної є елементи “m+2”-го рядка. В базис вводиться змінна, яка має в “m+2” найбільший додатний елемент. Якщо таких однакових найбільших додатних елементів буде два і більше, тоді перевага надається тому із них, який в рядку “m+1” має найбільше значення із знаком “—“. В тому випадку, коли в рядку “m+1” таких елементів буде не один, а декілька, то можна брати будь-який стовбець, однак бажано, щоби перевагу надати тому, який знаходиться ближче до стовбця вільних членів. Цим шляхом досягається виключення всіх штучних змінних із базису. В результаті буде одержано базисний розв’язок або опорний план. Його приймають як вихідний план для пошуку оптимального плану з допомогою звичайного симплексного методу. Напрямними елементами стають елементи “m+1”-го рядка. Причому, в задачах, які розв’язуються на мінімум, на відміну від розрахунку на максимум, в базис вводяться вектори, які мають в “m+1”-му рядку додатні елементи, починаючи з найбільшого. Розрахунок вважається закінченим, коли всі ці елементи стануть від’ємними або нулями.
Перетворимо початкову таблицю (табл.7) нашої задачі. Поскільки в ряд ку “m+2” найбільшим додатнім числом є число 103, то в базис повинна бути введена змінна х1. Ця змінна буде введена на місце штучної змінної y1, так як найменшим із відношень bi/aij є число 9. Розв’язувальним елементом є число 1. В результаті перерахунку всіх величин початкової таблиці (табл.7) одержимо наступну симплексну таблицю (табл.8).
Таблиця 8 – Друга симплексна таблиця
-
I
Базисні змінні
Сj
Вільні члени
30
18
15
10
0
0
Х1
Х2
Х3
Х4
Х5
Х6
1y1
30
9
1
0,4
0,2
0,2
-1
0
2y2
M
60
0
10
-10
-5
100
0
3
y3
M
382
0
19,2
14,6
1,6
2
-1
m + 1
270
0
-6
-9
-4
-30
0
m + 2
0
29,2
4,6
-3,4
102
-1
Таблиця 9 – Третя симплексна таблиця
-
I
Базисні змінні
Сj
Вільні члени
30
18
15
10
0
0
Х1
Х2
Х3
Х4
Х5
Х6
1
х1
30
9,6
1
0,5
0,1
0,15
0
0
2х5
0
0,6
0
0,1
-0,1
-0,05
1
0
3
y3
M
380,8
0
19,18
14,62
1,7
0
-1
M + 1
288
0
-3
-12
-5,5
0
0
M + 2
0
19,18
14,62
1,7
0
-1
Згідно показників “m+2” рядка в базис необхідно ввести змінну х5, а вивести із нього штучну змінну y2. Після перерахунку всіх елементів одержимо третю симплексну таблицю (табл.9).
В цій таблиці в базис вводиться основна змінна х2, а виводиться додаткова змінна х5. Після перетворення одержана четверта симплексна таблиця (табл.10).
Таблиця 10 – Четверта симплексна таблиця
-
I
Базисні змінні
Сj
Вільні члени
30
18
15
10
0
0
Х1
Х2
Х3
Х4
Х5
Х6
1
х1
30
6,6
1
0
0,6
0,4
0
0
2
х2
18
6
0
1
-1
-0,5
1
0
3
y3
M
265,72
0
0
33,8
11,29
0
-1
M + 1
306
0
0
-15
-7
0
0
M + 2
0
0
33,8
11,29
0
-1
Тепер із базиса виводиться штучна змінна y3, а на її місце вводиться основна змінна х3. В результаті перерахунку одержана п’ята симплексна таблиця (табл.11).
Таблиця 11 – П’ята симплексна таблиця
-
I
Базисні змінні
Сj
Вільні члени
30
18
15
10
0
0
Х1
Х2
Х3
Х4
Х5
Х6
1
Х1
30
1,893
1
0
0
0,1996
1,5888
0,0177
2
Х2
18
13,861
0
1
0
-0,1659
4,325
-0,0296
3
Х3
15
7,86
0
0
1
0,334
-5,674
-0,029
M + 1
424,19
0
0
0
-1,9896
-55,1183
-0,4437
M + 2
0
0
0
0
0
0
В базисі п'ятої симплексної таблиці уже відсутні штучні змінні, а рядок “m+2” містить тільки нулі, значить одержаний опорний і одночасно оптимальний план, поскільки в рядку “m+1” немає додатніх елементів.
В оптимальний кормовий раціон корови ввійшли корми в такій кількості (кг): концентрати (х1) 1,893; сіно природних кормових угідь (х2) 13,861 і силос кукурудзяний (х3) 7,86. Собівартість цього раціону дорівнює 424,19 коп. Кормові буряки (х4) в раціон не ввійшли.
ПОСТАНОВКА ТА РОЗВ’ЯЗУВАННЯ ТРАНСПОРТНИХ ЗАДАЧ ЛІНІЙНОГО ПРОГРАМУВАННЯ
Постановка і математична модель транспортної задачі
Метод апроксимації
Метод потенціалів
Розподільчий метод
Література:
1. Гатаулін А.М., Гаврилов Г.В., Харитонова Л.А. Економіко-математичні методи в плануванні сільськогосподарського виробництва. – К.: Вища школа, 1989.
2. Математическое моделирование экономических процессов в сельском хозяйстве. Под ред. проф. А.М.Гатаулина. – М.:Агропромиздат, 1990.
3. Курносов А.П. Вычислительная техника и программирование. –М.: Финанси ы статистика, 1991.
4. Кадюк З.С., Черняк В.Т., Іваницький І.Є., Сибаль Я.І. Використання методів лінійного програмування в економічних розрахунках. – Львів: Львів. держагроуніверситет, 2005.
5. Кадюк З.С., Черняк В.Т., СибальЯ.І., Іваницький І.Є. Економіко-математичне моделювання в АПК. - Львів: НВФ „Українські технології”, 2007.