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

Серед задач лінійного програмування часто зустрічаються такі, де одна або кілька змінних можуть приймати лише цілі значення. Якщо цілих значень набувають не всі змінні, а тільки деякі, задача є частково цілочисловою. Існують також задачі цілочислового програмування, де змінні можуть дорівнювати лише 0 або 1 (бульові, або бінарні).

Задачі цілочислового програмування легко розв’язуються за допомогою Excel. Для цього потрібно в пошуку рішення створити додаткове обмеження, виділити потрібні чарунки або масив і обрати знак «целое», а у разі наявності бульових змінних – використати знак «двоич».

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

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

Приклад 5.1

Підприємство має три філії А1, А2, А3, які можуть виготовляти відповідно 30, 20 та 15 тис. одиниць продукції на місяць. Укладено договори з чотирма замовниками B1, B2, B3,B4 на поставку продукції в кількості відповідно 10, 20, 25 та 20 тис. штук. Витрати на виробництво та транспортування тисячі одиниць продукції замовникам із кожної філії наведено в таблиці:

Таблиця 5.1

Витрати на виробництво та транспортування

Філія	В₁	В₂	В₃	В₄
А₁
А₂
А₃

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

Розв’язання

Задача є незбалансованою, оскільки сумарний попит становить 75 тис. шт., а загальна пропозиція – 65 тис. шт. Тому потрібне введення додаткового фіктивного виробника (A4)з пропозицією 10 тис. одиниць продукції (75-65). Вважаємо, що вартість виробництва і транспортування від нього до кожного замовника дорівнює 0.

Виконуємо в Excelтаблицю з умови задачі, додаємо підприємство A4. У рядочок знизу вводимо значення попиту кожного замовника, у стовпчик справа – пропозиції філій.

Оскільки маємо 4 виробника та 4 замовника, виділяємо нижче масив 4х4 (B11:E14), який буде містити оптимальний план задачі.

У чарунку B15 вставляємо формулу =СУММ(B11:B14)і протягуємо її до E15. У F11 вводимо = СУММ(B11:E11)і продовжуємо до F14.

Чарунка F15 буде містити цільову функцію, вводимо в неї формулу =СУММПРОИЗВ(B4:E7;B11:E14).

Обираємо в меню «Данные→Поиск решения». Встановлюємо цільову чарунку $F$15, що прямує до мінімуму. Вводимо обмеження $B$11:$E$14>=0; $B$15:$E$15$=B$8:$E$8; $F$11:$F$14=$F$4:$F$7.

Натискаємо «Выполнить».

Як бачимо, філія A1 має продати 10 тис. одиниць продукції замовнику B1, 5 тис. – B2 і 15 тис. – B3. Філія A2 постачатиме по 10 тис. шт. продукції підприємствам B3 та B4, а A3 – 15 тис. шт. підприємству B2. Частина попиту замовника B4 (10 тис. шт.) залишиться незадоволеною.

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

Питання для самостійного вивчення: методи розв’язування задач цілочислового програмування і транспортної задачі без Excel(метод Гоморі, метод «віток і меж», метод потенціалів, метод північно-західного кута, метод мінімальної вартості, метод апроксимації Фогеля, метод подвійної переваги).

Читайте також:

<== попередня сторінка	\|	наступна сторінка ==>
Тема 3. Задача лінійного програмування та методи її розв’язування	\|	Тема 6. Нелінійні оптимізаційні моделі економічних систем

Не знайшли потрібну інформацію? Скористайтесь пошуком google:

Генерація сторінки за: 0.103 сек.