Зміст виконання завдання

1. Запис умов задачі за індивідуальним варіантом.

2. Побудова початкового опорного плану задачі.

3. Розв'язок задачі в транспортних таблицях та на ПЕОМ за допомогою надбудови MS Excel ”Поиск решения” (додаток В) .

4. Висновки за результатами розв'язку задачі.

Зм 4. Цілочислове програмування

Теоретична частина. Значне місце в задачах математичного програмування займають задачі, на невідомі яких в оптимальному розв’язку накладена умова цілочисловості, а звичайне округлення приводить до грубих помилок (наприклад, кількість ферм у господарстві, кількість одиниць сільськогосподарської техніки тощо). Якщо умова цілочисловості накладається лише на частину невідомих, то такі задачі називають частково цілочисловими. Задачі, в яких крім умови цілочисловості оптимального розв'язку цільова функція і обмеження лінійні, називаються цілочисловими задачами лінійного програмування. Для знаходження оптимальних розв'язків цих задач застосовують точні (відтинання Гоморі) та комбінаторні (гілок і меж) методи.

4.1. Алгоритм методу відтинання Гоморі

При застосуванні методу відтинання Гоморі використовують такий алгоритм:

1. Задача розв’язується симплексним методом без врахування вимог цілочисловості змінних.

2. Якщо в умовно-оптимальному плані є дробові значення, то вибирається змінна, яка має найбільшу дробову частину^*). На базі цієї змінної (елементів відповідного рядка кінцевої симплексної таблиці, в якому вона міститься) будується додаткове обмеження-відтинання Гоморі за формулою

_n

∑ {a_ijx_j } ≥ {b_i}

^j=m+1

де {b_i} – дробова частина базисної змінної в умовно-оптимальному плані,

яка вибрана для побудови обмеження-відтинання;

{a_ij} – дробові частини коефіцієнтів при невідомих лівої частини додатко-

вого обмеження-відтинання.

3. Формулюється рядок-відтинання U_i за формулою

U_i = - f {b_i},

який приєднується до кінцевої симплексної таблиці умовно-оптимального плану. При цьому сформульований рядок–відтинання приймається за розв’язуючий рядок, а розв’язуюча колонка вибирається за максимальним значення (модулем) серед коефіцієнтів розв’язуючого рядка. Після розв’язання розширеної задачі за алгоритмом симплексного методу її перевіряють на цілочисловість. Якщо розв’язок не цілочисловий, то розрахунки повторюють, починаючи з п.2 до отримання цілочислового розв’язку.

Примітка^*) Цілою частиною числа а називається найбільше ціле число а, що не перевищує а. Дробовою частиною є число {a}, яке дорівнює різниці між самим числом а та його цілою частиною, тобто {a} = а - а. Наприклад, для а = 3 ¾ ціле число а = 3, а дробове число {a}= 3 ¾ - 3 = ¾ ; для

а = - 3 ¾ ціле число а = - 3, а дробове число {a}= - 3 ¾ - ( - 4) = ¹/₃ .

4.2. Алгоритм методу гілок і меж

Алгоритм розв’язання цілочислових задач за методом гілок і меж такий:

1. Задачу розв’язують симплексним методом без врахування вимог цілочисловості змінних. Якщо в оптимальному розв’язку немає дробових чисел, то отриманий розв’язок є оптимальним розв’язком цілочислової задачі.

2. Коли в умовно-оптимальному плані є дробові значення, то вибирають одну з нечислових змінних x_j і визначають її цілу частину.

3. Записують два обмеження, які відтинають не цілочислові розв’язки:

x_j ≤ [x_j *] та x_j ≥ [x_j *] + 1

де [x_j *] – ціла частина дробової змінної x_j в умовно оптимальному розв’язку.

Наприклад, якщо x_j =3 ¾, то отримуємо інтервал 3;4, де, очевидно, немає цілочислових значень x_j і оптимальний розв’язок цілочислової задачі буде знаходитися або в інтервалі x_j <= 3 або в інтервалі x_j >= 4.

4. Кожну з одержаних нерівностей приєднують до обмежень початкової задачі. В результаті отримують дві задачі лінійного програмування.

5. В будь-якій послідовності розв’язуються обидві задачі. Якщо отримано оптимальний цілочисловий розв’язок однієї задачі, а друга задача немає розв’язку, то процес розв’язування цілочислової задачі закінчено. У разі, коли оптимальний цілочисловий розв’язок одержано в обох задачах, то вибирається той розв’язок, який дає краще значення цільової функції. Якщо ж в обох задачах одержано не цілочислові значення, то для дальшого гілкування вибирають ту задачу, для якої знайдено краще значення цільової функції і здійснюють перехід до кроку 2. Розрахунки повторюються до отримання оптимального цілочислового розв"язку.

Приклад 4. Для виконання весняних польових робіт на площі 60 га фермер має можливість орендувати агрегати:

Марка агрегату	Змінний виробіток, га	Затрати палива за 1 машино-зміну, кг	Орендна плата за 1 машино-зміну, грн.
А	12	40	70
В	16	60	80

Добові затрати палива не повинні перевищувати 230 кг.

Визначити кількість орендованих машино-змін при мінімумі орендної плати.