Приклади цілочислових економічних задач
Задача 6.2. Задача лінійного розкрою. У цеху розрізують прути завдовжки 6 м на заготівки 1,4; 2 і 2,5 м. Усього в цеху мають 200 прутів. Потрібно дістати не менше як 40, 60 і 50 заготівок завдовжки відповідно 1,4; 2 і 2,5 м.
Побудувати загальну і числову модель лінійного розкрою. За критерій оптимізації є сенс узяти мінімум відходів.
Розв'язування. Нехай і 
— вид заготівки. Кожний прут можна розрізати різними 
способами. Скористаємося такими позначеннями:
— вихід заготовок i-го виду в разі розрізування прута 7-м способом;
— відходи в разі розрізування прута i-м способом;
— кількість наявних прутів;
— відповідно нижня і верхня межі потреби в i-й заготівці;
— кількість прутів, які розрізані за j-м варіантом.
Запишемо загальну економіко-математичну модель лінійного розкрою.
Критерій оптимальності:
за умов
Побудуємо числову економіко-математичну модель розрізування прутів, розглянувши можливі варіанти такого розрізування:
| Довжина заготівки, м | Варіанти розрізування прутів | ||||||
| 
| 
| 
| 
| 
| 
| |
| 1,4 | 4 | - | - | 1 | 1 | 2 | 2 |
| 2 | - | 3 | - | 1 | 2 | 1 | - |
| 2,5 | - | - | 2 | 1 | - | 1 | 1 |
| Довжина відходів, м | 0,4 | 0 | 1 | 0,1 | 0,6 | 1,2 | 0,7 |
Бажано, щоб у множину ввійшли всі можливі варіанти, навіть такі, які на перший погляд здаються неефективними, наприклад .
Запишемо числову економіко-математичну модель розрізування прутів:
за умов
а)щодо кількості заготівок завдовжки 1,4 м:
|
|
|
2 м:
2,5 м:
б) щодо кількості наявних прутів:
в) щодо невід’ємності змінних:
г) щодо цілочисловості змінних:
Пропонуємо розв'язати цю задачу одним із методів цілочислового програмування.
Задача 6.3. Задача комівояжера. В економічному регіоні розміщено 6 пунктів (міст). Комівояжер, який виїжджає з міста 1, має побувати в кожному місті один раз і повернутися до вихідного пункту. Знайти найкоротший маршрут, якщо відстані між містами відомі (рис. 6.2).
Записати загальну і числову економіко-математичну модель.
Розв'язування. Нехай маємо n пунктів, де має побувати комівояжер.
Позначимо:
Отже, 
— бульові (цілочислові) змінні. Цільовою функцією цієї задачі є мінімізація всього маршруту комівояжера:
де 
— відстань між містами і та j.
Обмеження щодо одноразового в'їзду в кожне місто:
Обмеження щодо одноразового виїзду з кожного міста:
Ці обмеження не повністю описують допустимі маршрути і не виключають можливості розриву маршруту. Щоб усунути цей недолік, введемо додаткові змінні 
, які набувають невід'ємних цілих значень. Запишемо обмеження, які виключають можливість існування підмаршрутів:
|
|
|
де 
— порядковий номер міста за маршрутом прямування комівояжера.
Запишемо числову економіко-математичну модель комівояжера за розглядуваних умов.
Критерій оптимальності:
а) обмеження щодо одноразового в’їзду в кожне місто:
б) обмеження щодо одноразового виїзду з кожного міста:
в) обмеження щодо виключення підмаршрутів:
Такі задачі розв'язуються спеціальними методами [1; 10].
Зауважимо, що аналогічні задачі нерідко постають на практиці, наприклад, у дрібному бізнесі.
Фірма у місті має 25 кіосків, які торгують безалкогольними напоями. Щоденно з бази автомобілем розвозять до них товар. Як оптимально організувати розвезення відповідної кількості товару?
ТЕМА 7.
ЗАДАЧІ ДРОБОВО-ЛІНІЙНРОГО ПРОГРАМУВАННЯ. ОСНОВНІ МЕТОДИ
РОЗВ’ЯЗУВАННЯ ТА АНАЛІЗУ.
Дата добавления: 2022-01-22; просмотров: 14; Мы поможем в написании вашей работы! |
Мы поможем в написании ваших работ!