4.2. Метод гілок і меж

Розв'язання. Для наведеної вище задачі без врахування умови цілочисловості отримано оптимальний розв’язок: W_min = 300; Х₁ = 0; Х₂ = 3 ¾; Ѕ₁ = 0;

Ѕ₂ = 5 (симплексна таблиця 4.2), де х₂ = 3 ¾ - дробове число. Допустиме ціле значення х₂ має задовольняти одну з нерівностей х₂ ≤ 3, або х₂ ≥ 4. Приєднуємо до початкової задачі кожне з обмежень і розв’язуємо по черзі обидві утворені задачі:

Задача 1 Задача 2

W_min = 70 Х₁ + 80 Х₂ W_min = 70 Х₁ + 80 Х₂

1) 12 Х₁ + 16 Х₂ = 60 1) 12 Х₁ + 16 Х₂ = 60

2) 40 Х₁ + 60 Х₂ ≤ 230 2) 40 Х₁ + 60 Х₂ ≤ 230

3) Х₂ ≤ 3 3) Х₂ ≥ 4

Для задачі 1 оптимальним буде цілочисловий розв’язок : W_min = 310;

Х₁ = 1; Х₂ = 3; Ѕ₁ = 0; Ѕ₂ = 10.

Задача 2 не має допустимого розв’язку.

Таким чином, оптимальний розв’язок цілочислової задачі такий:

W_min = 310; Х₁ = 1; Х₂ = 3; Ѕ₁ = 0; Ѕ₂ = 10 (див. також оптимальний розв’язок за методом відтинання Гоморі, симплексна таблиця 4.4.)

Висновки. Мінімальну орендну плату в розмірі 310 грн. (W_min =310) фермер буде платити, якщо буде орендувати 1 машино-зміну агрегату марки А (х₁=1) та 3 машино-зміни агрегату марки В (х₂= 3). Залишок палива становить 10 кг (S₂ =10). Всі роботи будуть виконані повністю (Ѕ₁=0).

Задачі для самостійного розв’язання

Задача 4. Для збирання зернових на площі 1200+250хК га господарство може орендувати комбайни марок А та В, техніко-економічні показники яких за сезон жнив наведені нижче:

Показник			Комбайни марок
	А			В
1.Сезонний виробіток, га		200			250
2. Експлуатаційні затрати, тис. грн.		18			20
3.Орендна плата, тис. грн.		80+Р			90+К

Визначити кількість орендованих комбайнів марок А та В при обов’язковому виконанні запланованого обсягу робіт та мінімальній орендній платі. Експлуатаційні затрати не повинні перевищувати 300 тис. грн.

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

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

2. Формулювання економіко-математичної моделі задачі.

3. Розв’язання задачі за методом відтинання Гоморі в симплексних таблицях (додаток А), а за методом гілок і меж тільки за допомогою надбудови MS Excel ”Поиск решения” (додаток Б).

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

Модуль2. Дослідження операцій

ЗМ 5. Теоретичні засади економіко-математичногомоделювання на базі загальної задачі лінійного рограмування (ЗЗЛП)

Теоретична частина. Загальна задача лінійного програмування, на базі якої будуються лінійні оптимізаційні економіко-математичні моделі виробничих систем, формулюється так: знайти вектор невідомих х =(х₁,х₂, ..., х_j, ..., х_n), при якому цільова функція Z досягає екстремуму

_n

Z_ext = ∑ c_j x_j j(1,n)

^j=1

при обмеженнях:

_n

1) ∑ a_ij x_j = b_i i(1,m)

^j=1

2) x_j >= 0,

де

x_j - невідомі задачі, які поділяються на основні (визначаються за економічним змістом задачі), додаткові (утворюються при переході до канонічної форми задачі, і, як правило, означають невикористані виробничі ресурси при обмеженнях виду менше або дорівнює (<=) та перевиконання планових завдань при обмеження виду більше або дорівнює (>=), допоміжні (використовуються для розрахунків сумарних економічних показників, обсягів залучення додаткових виробничих ресурсів тощо);

a_ij - коефіцієнти при невідомих в обмеженнях або техніко-економічні показники - означають норми затрат виробничих ресурсів або вихід продукції на одиницю виміру невідомої;

b_i - обсяги обмежень - обмеження економіко-математичної задачі у вигляді нерівностей та рівнянь відображають умови використання виробничих ресурсів (<=) або виконання планових завдань виробництва і реалізації продукції (>=). Тому обсяги обмежень, як правило, означають обсяги виробничих ресурсів або обсяги планових завдань виробництва і реалізації продукції;

c_j - коефіцієнти при невідомих в цільовій функції або оцінки невідомих, в якості яких, як правило, приймаються економічні показники також на одиницю виміру невідомої. Цільова функція є математичним виразом критерію оптимальності і показує цільову направленість розв'язку задачі. Тому економічний зміст оцінки невідомої визначає напрям критерію оптимальності ( максимум прибутку, валової продукції, але мінімум виробничих затрат тощо).

При побудові економіко-математичних моделей потрібно враховувати їх розмірність, яка визначається такими правилами:

1) параметри економіко-математичної моделі задачі вимірюються в загально прийнятих одиницях виміру (га, т, кг, м, км, шт. тощо);

2) розмірність a_i = розмірність b_i / розмірність x_j;

3) ліві і праві частини обмежень повинні вимірюватись в одних і тих же одиницях виміру.

Побудова економіко-математичної моделі виконується поетапно в такій послідовності :

1. Постановка задачі - на основі економічного аналізу виробничої системи досліджується можливість формулювання економіко-математичної моделі і визначаються (обґрунтовуються) такі основні її параметри: перелік невідомих, система обмежень та цільова функція, які повинні бути чітко визначені (однозначні) і достовірні. В системі обмежень задачі не повинно бути протиріч.

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

3. Підготовка інформації - при моделюванні виробничих систем інформацію використовують у вигляді економічних даних, джерелами яких є нормативно-довідкові матеріали, плани, звіти, розраховані економічні показники тощо. Вимоги до інформації: достовірність, оперативність, економічність та ефективність. При моделюванні обов’язково потрібно враховувати розмірність параметрів економіко-математичної моделі.

4. Побудова економіко-математичної моделі - це математична формалізація умов задачі. При цьому використовуються такі форми запису моделей:

а) структурна - запис умов задачі в загальному аналітичному вигляді за допомогою алгебраїчних символів та індексів;

б) розгорнута - запис умов задачі в розгорнутому вигляді, як правило, у вигляді матриці.

Модель з конкретними числовими характеристиками називається числовою. При розв’язанні задачі на ПЕОМ модель записується у числовій матричній формі. Модель спочатку формулюється в аналітичному вигляді, а потім - в матричному. Для переходу до матричної форми запису аналітичну форму шляхом елементарних перетворень потрібно привести до стандартного виду, тобто в лівій частині кожного обмеження повинні бути невідомі з відповідними коефіцієнтами, а в правій – додатні числа або нуль.

Запис економіко-математичної моделі задачі (фрагмент) в аналітичному вигляді такий (приклад): знайти

Х₁ – посівна площа озимої пшениці, га;

Х₂ – посівна площа кукурудзи на зерно, га;

Х₃ посівна площа ячменю, га і т.д. … Х_n, при яких цільова функція Z

(обсяг виробництва зерна) досягає максимуму

Z_max = 40 Х₁ + 54Х₂ + 35Х₃ …

при обмеженнях:

1. Х₁ + Х₂ + Х₃ …. <= 2000 – використання ріллі, га;

2. Х₁ + Х₂ + Х₃ …. >= 1340 – площа зернових культур, га;

3. …

Запис цього фрагменту економіко-математичної моделі задачі в матричній формі буде такий:

Невідомі Обмеження	Площа, га			...	...	Вид обмежень	Обсяги обмежень
	Пшениця озима	Кукурудза на зерно	Ячмінь
	Х1	Х2	Х3	...	Хn
1.Рілля,га	1	1	1	...		<=	2000
2.Зернові культури,га	1	1	1	...		>=	1340
3. …	...	...	...	...	...	...	...
Zmax-валовий збір зерна, ц	40	54	35	...	...	...	...

5. Розв’язання задачі - економіко-математичні моделі реальних задач, як правило, розв’язуються на ПЕОМ за відповідною програмою вибраного математичного методу (симплексний метод, метод потенціалів тощо). Результати розв’язання задачі аналізуються і, при необхідності, коригуються. При розв’язанні достатньо складних і великих за розміром задач можливі помилки при побудові моделі, внаслідок чого задача не має допустимих розв’язків. Для усунення помилок потрібно перевірити правильність відображення в моделі умов задачі та введення інформації до ПЕОМ. Проте, однією із основних причин відсутності допустимих розв’язків задачі може бути наявність в ній суперечливих умов. Для їх усунення можна скоригувати обсяги обмежень (b_i) або техніко-економічні коефіцієнти (a_ij). В реальних виробничих системах перший шлях економічно недоцільний, а іноді і неможливий. В той же час, впровадження у виробництво досягнень науково-технічного прогресу дозволяє зменшити норми затрат виробничих ресурсів і збільшити вихід продукції на одиницю виміру невідомої (a_ij), що і приводить до усунення протиріч в задачі.

6. Вибір оптимального варіанта розв’язку задачі - на основі економічного аналізу результатів розв’язання задачі вибирається варіант оптимального розв’язку задачі для впровадження його у виробництво.