Навигация
Рішення задач цілочисленного програмування
32739
знаков
0
таблиц
2
изображения
Курсова робота:
Рішення задач цілочисленного програмування
Зміст
Введення
1. Постановка лінійної цілочисленної задачі
2. Теоретичні основи методів відсікання
3. Перший алгоритм Гомори
4. Другий алгоритм Гомори
5. Алгоритм Дальтона й Ллевелина
6. Алгоритм Данцига
7. Деякі висновки
Висновок
Список літератури
Введення
Серед практично важливих задач відшукання умовного екстремуму лінійної функції важливе місце займають задачі з вимогою цілочисленності всіх (частини) змінних. Вони одержали назву задач цілочисленного програмування.
Історично першою задачею цілочисленного типу є опублікована угорським математиком Е. Егервари в 1932 р. задача про призначення персоналу.
Існують різні методи рішення таких задач, і помітне місце серед них займають методи відсікання. Розглянемо в цій роботі деякі з методів відсікання, попередньо більш докладно розібравшись із постановкою лінійних цілочисленних задач.
1. Постановка лінійної цілочисленної задачі
Серед сукупності п неподільних предметів, кожний i-і (i=1,2,…,п) з яких володіє по i-й характеристиці показником 
і корисністю 
знайти такий набір, що дозволяє максимізувати ефективність використання ресурсів величини 
.
Математична модель цієї задачі може бути представлена в такий спосіб:
в області, певної умовами
(1)
(2)
- цілі, 
. (3)
знайти рішення 
при якому максимізується (мінімізується) значення цільової функції
(4)
Якщо 
, то (1–4) є моделлю задачі цілочисленного програмування, якщо 
- моделлю задачі частково цілочисленного програмування.
Часткою случаємо задачі цілочисленного програмування є задача з булевими змінними. Її математична модель у загальному виді записується в такий спосіб:
в області, певної умовами
(5)
(6)
знайти рішення 
, при якому максимізується (мінімізується) значення функції
(7)
До класу задач цілочисленного програмування примикають задачі, у яких умова цілочисленності всіх або частини змінних замінено вимогою дискретності. А саме, для кожної j-і змінної 
заздалегідь визначений набір значень (не обов'язково цілих), які вона може приймати: 
де 
.
Передбачається, що 
сільгоспкооперативи, тобто
. Математична модель загальної задачі дискретного програмування може бути представлена в такий спосіб:
в області, певної умовами
(8)
(9)
знайти рішення 
, при якому максимізується (мінімізується) лінійна функція
(10)
Умова (9) визначило назву цього класу; задач. Якщо , то (8–10) називається задачею дискретного програмування; якщо , те (8–10) називається задачею частково дискретного програмування.
Неважко бачити, що умова (2–3) задачі (1–4) і умова (6) задачі (5–7) є часткою случаємо умови (9) задачі (8–10). Дійсно, (2–3) відповідає тому случаю, коли 
для 
. Умова (9) відповідає випадку, коли 
.
Для задач цілочисленного типу визначене поняття припустимого й оптимального рішення.
Вектор , що задовольняє умовам (1–3) (відповідно (8–9)), називається припустимим рішенням задачі (1–4) (відповідно (8–10)). Припустиме рішення, при якому функція (4) (відповідно (10)) досягає найбільшого (найменшого) значення, називається оптимальним рішенням.
Визначивши поняття припустимого й оптимального рішення, природно порушити питання про їхнє знаходження. Здавалося б, що природний шлях рішення цілочисленної задачі складається в рішенні відповідної лінійної задачі з наступним округленням компонентів її оптимального плану до найближчих цілих чисел. Насправді такий шлях у більшості випадків не тільки веде, від оптимуму, але навіть приводить іноді до неприпустимого рішення задачі.
ПРИКЛАД. В області, певної умовами
– цілі
знайти максимум функції 
.
Вирішимо задачу геометрично (мал. 1). Область пошуку екстремума – багатокутник ODABC, але тому що лінія рівня цільової функції паралельна стороні АВ багатокутника, екстремум досягається у вершинах 
і 
, а також у будь-якій крапці відрізка АВ, і дорівнює 7.
(мал. 1)
Однак нас цікавлять лише крапки із цілочисленними координатами, отже, ні А, ні В не є припустимим рішенням задачі. Округляючи значення координат А, одержимо 
Але крапка А' не належить області пошуку. Можна показати, що цілочисленний оптимум досягається в крапках N (3; 2) і M (2; 3) і дорівнює 5. Обидві крапки усередині області пошуку.
Побудований нами приклад показав, що для рішення задач із вимогою цілочисленності необхідно розглянути особливі методи оптимізації; і, крім того, ми бачимо, що оптимальне рішення задач цілочисленного програмування не обов'язково належить границі багатогранника (багатокутника) умов, що було характерно для задач лінійного програмування.
Похожие работы
4 9 0 1 0 3 Р5 0 8 4 -2 0 0 1 4 F 0 -5 -6 0 0 0 Таблиця № 1 – Вихідна симплекс-таблиця Знаходження оптимального розвязку ЗЛП за допмогою с-м включає слідуючі етапи: 1. За вихідною с-т знаходять опорне рішення Кожній с-т відповідає своє опорне рішення. Воно може бути представлене у вигляди вектора Х Розмірніст вектора дорівнює кількості змі ...
... . Механізм переривань забезпечує ефективна взаємодія пристроїв уведення-висновку з мікропроцесором. Переривання цікавлять нас тому, що обробка переривань - це прерогатива програмування на мові асемблера. У високорівневих мовах відсутні засоби роботи з перериваннями на машинному рівні. Переривання звичайно викликаються зовнішніми пристроями. Переривання сигналізує мікропроцесору, щоб він призупинив ...
... рішень, зв’язаних із регулюванням витрат і з питань інвестиційної діяльності підприємства. Отже, управлінський облік це формування інформації для управління витратами з метою підвищення ефективності функціонування підприємства. Причому, відповідно до Закону «Про бухгалтерський облік і фінансову звітність в Україні», підприємства вправі самостійно обирати систему і форми ведення управлінського ...
... ‚ є гіпотезою про закон розподілу. Гіпотеза про те‚ що середні розміри деталей‚ які виготовляються на однотипних‚ паралельно працюючих станках‚ приблизно однакові‚ є гіпотезою про параметри розподілу. Зроблений на основі статистичних даних висновок про те‚ що між кількома генеральними сукупностями або між емпіричним і теоретичним розподілом істотних відмінностей немає‚ називають нульовою ( ...
0 комментариев