Практична робота №3

Тема: Задачі лінійної оптимізації в економіці.

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

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

Так, кожний раз, коли ми заходимо до магазину, перед нами постає одна й та сама проблема: як максимально задовольнити потреби, враховуючи можливості гаманця.

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

Багато з цих задач зводяться до основної задачі лінійного програмування.

Лінійне програмування – це розділ математики, в якому вивчаються методи знаходження максимуму та мінімуму лінійної функції скінченого числа змінних за умови, що ці змінні задовольняють скінченому числу додаткових обмежень у вигляді лінійних рівнянь або лінійних нерівностей. Лінійну функцію називають функцією мети.

Основна задача лінійного програмування (ОЗЛП) полягає у відшуканні таких значень дійсних змінних , , …, , для яких функція мети

(9.1)

досягає мінімального або максимального значення на множині точок, координати яких задовольняють нерівностям:

(9.2)

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

, (9.3)

Тут – координати відомого напрямного вектора-градієнта, – елементи відомої матриці , – елементи відомого вектора-стовпчика вільних членів .

Задача 1

Оптимальне планування штатного розкладу

Авіакомпанії потрібно визначити, скільки стюардес можна прийняти на роботу протягом 6 місяців при умові, що всі вони повинні пройти попередню підготовку. При цьому беруться до уваги такі показники і умови:

1. Потреби у кількості льотного часу для стюардес (вимірюються у людино-годинах):

у січні – 8 000;

у лютому – 9 000;

у березні – 8 000;

у квітні – 10 000;

у травні – 9 000;

у червні – 12 000.

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

3. Крім того, стюардеса повинна на протязі місяця, відведеного їй на підготовку, пройти 100-годинну практику безпосередньо під час польотів. Таким чином, за рахунок кожної стюардеси, що навчається на протязі місяця звільняється 100 людино-годин льотного часу, відведеного для стюардес вже підготовлених для польотів.

4. Кожна штатна стюардеса на протязі місяця може мати наліт до 150 годин.

5. Авіакомпанія на початку січня вже має 60 стюардес з досвідом. При цьому ні одну з них не збирається звільняти з роботи.

6. Встановлено також, що біля 10 % стюардес, що навчаються, по закінченні навчання звільняються з якихось причин.

7. Стюардеса з досвідом обходиться компанії у $ 800, а та, що навчається – $ 400 на місяць.

Необхідно спланувати штат авіакомпанії таким чином, щоб мінімізувати витрати за звітні 6 місяців.

Побудова математичної моделі оптимального планування штатного розкладу

Нехай х_1, х_2, х_3, х_4, х_5, х₆ – кількість нових стюардес, яких авіакомпанія набирає відповідно у січні, лютому, березні, квітні, травні і червні місяцях.

Тоді число постійно працюючих (штатних) стюардес у авіакомпанії буде:

у січні 60;

у лютому 60+0.9 х₁;

у березні 60+0.9 (х₁+ х₂);

у квітні 60+0.9 (х₁+ х₂+ х₃);

у травні 60+0.9 (х₁+ х₂+ х₃+ х₄);

у червні 60+0.9 (х₁+ х₂+ х₃+ х₄+ х₅).

Функція мети:

Z= 400$ (х₁+х₂+х₃+х₄+х₅+х₆) + 800$[60+60+0.9 х₁ + 60+0.9 (х₁+ х₂) + …
… + 60+0.9 (х₁+ х₂+ х₃+ х₄+ х₅) ] → min

Обмеження:

100* х₁ +60*150≥ 8000,

100* х₂ +(60+0.9 х₁)*150≥ 9000,

100* х₃ +(60+0.9 х₁ +0.9 х₂ )*150≥ 8000,

100* х₄ +(60+0.9 х₁ +0.9 х₂ +0.9 х₃)*150≥ 10000,

100* х₅ +(60+0.9 х₁ +0.9 х₂ +0.9 х₃ +0.9 х₄)*150≥ 9000,

100* х₆ +(60+0.9 х₁ +0.9 х₂ + ….+0.9 х₅)*150≥ 12000,

х_і ≥ 0, х_і – цілі числа, і =1, 6.

Розв’язування:

Задамо вихідні дані і запрограмуємо відповідні формули в робочу книгу MS Excel так, як показано на рис. 9.13.

Рис. 9.13

Початкові значення невідомих (кількість нових стюардес) покладемо рівними 0: діапазон B3: B8, функція мети обчислюється у комірці F9.

Скориставшись засобом Поиск решения так, як показано на рис. 9.14,

Рис. 9.14

ми отримаємо результат (рис. 9.15).

Рис. 9.15

Таким чином, згідно оптимального плану штатного розкладу авіакомпанії в червні треба взяти 17 стюардес, що, на перший погляд, є нелогічним. Припустимо, що авіакомпанія вирішила не брати в червні нових стюардес. Тоді треба ввести додаткове обмеження: $B$8 = 0. Скориставшись засобом Поиск решения, отримаємо такий результат (рис. 9.16):

Рис. 9.16

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

Транспортна задача лінійного програмування

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

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

- відстані;

- схем перевезень;

- видів транспорту тощо.

Транспортна задача – це задача вибору оптимального варіанта доставки товару від пунктів виробництва до пунктів споживання з урахуванням усіх реальних можливостей.

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

- оптимальний розподіл торговельної площі магазинів різних районів під групи різних товарів;

- оптимальний розподіл баз і торговельних точок у населених пунктах тощо.

Використання розрахунків транспортної задачі, як правило, знижує транспортні видатки на 10-30 %.

Транспортні задачі за своєю постановкою поділяються на кілька груп:

· задачі на мінімізацію вартості перевезень товару від пунктів виробництва до пунктів споживання;

· задачі на мінімізацію довжини маршруту при перевезенні вантажу від одного постачальника до кількох споживачів;

· задачі на мінімізацію строків перевезення товару від пунктів виробництва до пунктів споживання тощо.

Приклад 2 (приклад транспортної задачі).

Деяка фірма будує дорогу. Їй необхідні постачання: піску, гравію, бетону, асфальту та ін. По мірі будівництва фірма віддаляється від старих постачальників (кар’єрів, бетонних заводів, залізниці та ін.), транспортні витрати зростають. Фірма шукає нових постачальників, менеджери перераховують транспортну задачу, оцінюють витрати на перевезення матеріалів, намагаються їх мінімізувати.

У загальному випадку транспортна задача полягає в тому, що необхідно доставити певну кількість ресурсів від розподілених у просторі постачальників до розподілених у просторі споживачів (рис. 9.17):

Постачальник 1 Споживач 1 Постачальник 2 Споживач 2 Постачальник 3 Споживач 3

Рис. 9.17

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

Необхідно забезпечити мінімум витрат на перевезення, якщо відомі потреби споживачів, а потужності (можливості) постачальників обмежені.

Мета розв’язування транспортної задачі: cкласти найкращий оптимальний план перевезень від постачальників до споживачів з урахуванням обмежених ресурсів постачальників і відомими потребами споживачів. Мінімізувати витрати на перевезення.

Побудова математичної моделі транспортної задачі

Нехай відомі:

- перелік споживачів j=1, m та об’єми їх потреб – , j=1, m;

- перелік постачальників і =1, п та їх потужності – , і =1, п;

- витрати на поставку одиниці вантажу від кожного постачальника до кожного споживача – c_ij; і =1, п; j =1, m.

Позначимо через x_ij, – невідомі планові кількості перевезень від i -го постачальника до j -го споживача (і =1, п; j =1, m). Тоді математична модель транспортної задачі буде такою:

(9.6)

(9.7)

, (9.8)

де – невід’ємні об’єми перевезень, z – функція мети: мінімізація загальних витрат при перевезенні товару від всіх постачальників до всіх споживачів, – план поставок товару від i- го постачальника до всіх споживачів, – план поставок j -му споживачеві від всіх постачальників.

Приклад 3.

Нехай відомі вартості перевезення одиниці вантажу від кожного з 3-х постачальників до кожного з 5-ти споживачів, а також потужності постачальників і потреби споживачів (рис. 9.18).

 

Рис. 9.18

Знайти оптимальний план кількості перевезень вантажу, в якому врахувати потреби споживачів, обмежені потужності постачальників і мінімізувати витрати.

Розв’язування:

Задамо вихідні дані і запрограмуємо відповідні формули в робочу книгу MS Excel так, як показано на рис. 9.19. Для невідомих x_ij, і =1, n; j =1, m ми відвели діапазон B2: F4 і задали початкові значення, що дорівнюють 0.

 

Рис. 9.19

Скориставшись засобом Поиск решения так, як показано на рис. 9.20,

 

Рис. 9.20

ми отримаємо результат (рис. 9.21).

 

Рис. 9.21

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

Частинним випадком транспортної задачі є задача про призначення на роботу.

 

Задача про призначення на роботу

 

Постановка задачі. i (i=1, n) робітників можуть виконувати j (j=1, m) видів робіт. Вартості c_ij виконання і -м робітником j -ї роботи відомі. Необхідно скласти план виконання робіт так, щоб всі роботи були виконані, кожний робітник був зайнятий тільки на 1 роботі, а сумарна вартість виконання всіх робіт була мінімальною.

Відмітимо, що коли – число робіт співпадає з числом робітників, то задача є збалансованою.

Якщо задача не збалансована, то перед початком її розв’язування необхідно її збалансувати, ввівши відповідне число фіктивних рядків або стовпчиків з достатньо великими штрафними вартостями робіт.

 

Побудова математичної моделі збалансованої задачі про призначення на роботу

Нехай змінна

Тоді математична модель цієї задачі буде такою:

Функція мети:

, (9.9)

Обмеження:

,

, (9.10)

(9.11)

Обмеження (9.10) означають, що кожна робота має бути виконаною і кожний робітник виконує лише одну роботу.

Приклад 4.

Нехай відомі вартості виконання кожним з 4-х робітників відповідної роботи (рис. 9.22).

 

	роб.№1	роб.№2	роб.№3	роб.№4
1-й робіт.
2-й робіт.
3-й робіт.
4-й робіт.

Рис. 9.22

Знайти оптимальний план виконання робіт так, щоб всі роботи були виконані, кожний робітник був зайнятий тільки на 1 роботі, а сумарна вартість виконання всіх робіт була мінімальною.

Розв’язування:

Задамо вихідні дані і запрограмуємо відповідні формули в робочу книгу MS Excel аналогічно транспортній задачі (див. рис. 9.19, рис. 9.23):

 

Рис. 9.23

Скориставшись засобом Поиск решения так, як показано на рис. 9.24,

 

Рис. 9.24

ми отримаємо результат (рис.9.25).

 

Рис. 9.25

 

 

Контрольні запитання

 

1. Яку задачу називають транспортною задачею?

2. Наведіть приклади транспортних задач?

3. В чому полягає транспортна задача в загальному випадку?

4. Яка мета транспортної задачі?

5. Які вихідні дані транспортної задачі?

6. Наведіть математичну модель транспортної задачі?

7. У чому полягає постановка задачі про призначення на роботу?

8. Наведіть математичну модель задачі про призначення на роботу?