Студопедия
Новини освіти і науки:
МАРК РЕГНЕРУС ДОСЛІДЖЕННЯ: Наскільки відрізняються діти, які виросли в одностатевих союзах


РЕЗОЛЮЦІЯ: Громадського обговорення навчальної програми статевого виховання


ЧОМУ ФОНД ОЛЕНИ ПІНЧУК І МОЗ УКРАЇНИ ПРОПАГУЮТЬ "СЕКСУАЛЬНІ УРОКИ"


ЕКЗИСТЕНЦІЙНО-ПСИХОЛОГІЧНІ ОСНОВИ ПОРУШЕННЯ СТАТЕВОЇ ІДЕНТИЧНОСТІ ПІДЛІТКІВ


Батьківський, громадянський рух в Україні закликає МОН зупинити тотальну сексуалізацію дітей і підлітків


Відкрите звернення Міністру освіти й науки України - Гриневич Лілії Михайлівні


Представництво українського жіноцтва в ООН: низький рівень культури спілкування в соціальних мережах


Гендерна антидискримінаційна експертиза може зробити нас моральними рабами


ЛІВИЙ МАРКСИЗМ У НОВИХ ПІДРУЧНИКАХ ДЛЯ ШКОЛЯРІВ


ВІДКРИТА ЗАЯВА на підтримку позиції Ганни Турчинової та права кожної людини на свободу думки, світогляду та вираження поглядів



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

 

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

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

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

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

Приклад 5.1

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

Таблиця 5.1

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

Філія В1 В2 В3 В4
А1
А2
А3

 

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

Розв’язання

Задача є незбалансованою, оскільки сумарний попит становить 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(метод Гоморі, метод «віток і меж», метод потенціалів, метод північно-західного кута, метод мінімальної вартості, метод апроксимації Фогеля, метод подвійної переваги).

 


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

  1. Алгебраїчне та інсерційне програмування
  2. Безпосереднє програмування відеопам'яті
  3. Виконання програми - реалізація мови програмування
  4. Використання пакету Maple для розв’язування задач лінійного програмування
  5. Вступ до мови програмування
  6. Геометрична інтерпретація задачі лінійного програмування
  7. Геометрична інтерпретація задачі нелінійного програмування
  8. Геометрична інтерпретація розв’язків цілочислових задач лінійного програмування на площині
  9. Графічний метод розв’язування задач лінійного програмування
  10. Державне регулювання суспільного відтворення та його форми. Планування та програмування
  11. Динамічне програмування.
  12. Динамічного програмування




Переглядів: 687

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

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

  

© studopedia.com.ua При використанні або копіюванні матеріалів пряме посилання на сайт обов'язкове.


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