МАРК РЕГНЕРУС ДОСЛІДЖЕННЯ: Наскільки відрізняються діти, які виросли в одностатевих союзах
РЕЗОЛЮЦІЯ: Громадського обговорення навчальної програми статевого виховання ЧОМУ ФОНД ОЛЕНИ ПІНЧУК І МОЗ УКРАЇНИ ПРОПАГУЮТЬ "СЕКСУАЛЬНІ УРОКИ" ЕКЗИСТЕНЦІЙНО-ПСИХОЛОГІЧНІ ОСНОВИ ПОРУШЕННЯ СТАТЕВОЇ ІДЕНТИЧНОСТІ ПІДЛІТКІВ Батьківський, громадянський рух в Україні закликає МОН зупинити тотальну сексуалізацію дітей і підлітків Відкрите звернення Міністру освіти й науки України - Гриневич Лілії Михайлівні Представництво українського жіноцтва в ООН: низький рівень культури спілкування в соціальних мережах Гендерна антидискримінаційна експертиза може зробити нас моральними рабами ЛІВИЙ МАРКСИЗМ У НОВИХ ПІДРУЧНИКАХ ДЛЯ ШКОЛЯРІВ ВІДКРИТА ЗАЯВА на підтримку позиції Ганни Турчинової та права кожної людини на свободу думки, світогляду та вираження поглядів
Контакти
Тлумачний словник Авто Автоматизація Архітектура Астрономія Аудит Біологія Будівництво Бухгалтерія Винахідництво Виробництво Військова справа Генетика Географія Геологія Господарство Держава Дім Екологія Економетрика Економіка Електроніка Журналістика та ЗМІ Зв'язок Іноземні мови Інформатика Історія Комп'ютери Креслення Кулінарія Культура Лексикологія Література Логіка Маркетинг Математика Машинобудування Медицина Менеджмент Метали і Зварювання Механіка Мистецтво Музика Населення Освіта Охорона безпеки життя Охорона Праці Педагогіка Політика Право Програмування Промисловість Психологія Радіо Регилия Соціологія Спорт Стандартизація Технології Торгівля Туризм Фізика Фізіологія Філософія Фінанси Хімія Юриспунденкция |
|
|||||||||||||||||||||||||||
Тема 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(метод Гоморі, метод «віток і меж», метод потенціалів, метод північно-західного кута, метод мінімальної вартості, метод апроксимації Фогеля, метод подвійної переваги).
Читайте також:
|
||||||||||||||||||||||||||||
|