Задачі цілочисельного програмування та спеціальні методи знаходження їх оптимальних розв'язків

ЗАДАЧІ ЦІЛОЧИСЕЛЬНОГО ПРОГРАМУВАННЯ ТА СПЕЦІАЛЬНІ МЕТОДИ ЗНАХОДЖЕННЯ ЇХ ОПТИМАЛЬНИХ РОЗВ’ЯЗКІВ

Зміст

Вступ

Розділ 1. Цілочисельне програмування

1.1 Деякі історичні відомості

1.2 Постановка задачі

1.2 Приклади застосування цілочисельних задач лінійного програмування у плануванні та управлінні виробництвом

Розділ 2. Методи розв´язання задач цілочислового програмування

2.1 Геометрична інтерпретація розв’язків цілочислових задач лінійного програмування на площині

2.2 Методи відтинання. Метод Гоморі

2.3 Комбінаторні методи. Метод гілок та меж

Розділ 3. Розробка математичної моделі складання розкладу занять на математичному факультеті ВНУ

3.1 Формулювання завдання складання розкладу занять на математичному факультеті

3.2 Математична модель розкладу у вузі

Висновки

Література

Додаток а. бібліографія

Вступ

Дипломна робота присвячена задачам цілочисельного програмування та спеціальним методам знаходження їх оптимальних розв’язків. В ній наведено конкретні приклади застосування цілочисельних задач лінійного програмування у плануванні та управлінні виробництвом, а також розроблено математичну модель розкладу занять на математичному факультеті Волинського національного університету ім. Лесі Українки.

Робота складається із вступу, трьох розділів, висновків та списку використаної літератури, додатку в якому подано відомості про вчених, авторів основних результатів роботи

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

Другий розділ присвячений детальному розгляду методів задач цілочислового програмування, таких як графічний метод, метод Гоморі та методу гілок і меж.

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

Актуальність теми в тому, що математичне програмування зараз проникло у всі інші науки, починаючи з біології і психології і кінчаючи лінгвістикою. Навряд чи можна вказати сферу практичної і духовної діяльності людини, де б не застосовувалися методи математичного дослідження. Якщо раніше математичний апарат переважно використовувався як інструмент розрахунку, то тепер ставиться завдання вибору найбільш ефективного розв’язку проблеми, пошук оптимального варіанту.

Постановка завдання лінійного програмування вперше прозвучала в роботах російського економіста А.Н. Товстого при складанні плану перевезення вантажу між пунктами так, щоб загальний пробіг транспорту був найменшим. Математичні основи для вирішення завдань лінійного програмування були створені в 1939 році академіком Л.В. Канторовичем і його учнями. Методи лінійного програмування набули широкого поширення при розв’язані економічних задач, в плануванні виробництва, в сільському господарстві, у військовій справі. Їх значущість підкреслюється тим, що вони реалізовані в прикладних комп'ютерних програмах (MS Excel) і можуть використовуватися при необхідності кожним, хто уміє працювати на ПК.

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

Мета і завдання дослідження:

розглянути методи розв’язання задач цілочисельного програмування та визначити умови ефективності застосування кожного з них до розв’язання задачі про складання розкладу занять;

побудувати математичну модель для складання розкладу занять для студентів математичного факультету.

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

цілочисельне програмування математичний розклад

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

Практичне значення одержаних результатів. Результати роботи можна використати на практичних заняттях при вивченні дисципліни "Математичні моделі ЕЕС процесів" для студентів 5-го курсу спеціальності "прикладна математика". Їх також можна запропонувати для написання магістерської роботи з прикладної математики, ціллю якої було б автоматизоване складання розкладу занять.

Апробація результатів. Результати роботи доповідались на IV науково­ практичній конференції студентів та аспірантів "Волинь очима науковців: минуле, сучасне, майбутнє" (12-13 травня 2010р., м. Луцьк).

Розділ 1. Цілочисельне програмування

1.1 Деякі історичні відомості

В суто математичному плані деякі оптимізаційні задачі були відомі ще в стародавній Греції. Однак, сучасне математичне програмування передусім розглядає властивості та розв’язки математичних моделей економічних процесів. Тому початком його розвитку як самостійного наукового напрямку слід вважати перші спроби застосування методів математичного програмування в прикладних дослідженнях, насамперед в економіці. Початком математичного програмування вважають праці радянського вченого Л.В. Канторовича. Наприкінці 30-х років у Ленінградському університеті ним уперше були сформульовані та досліджувались основні задачі, критерії оптимальності, економічна інтерпретація, методи розв’язання та геометрична інтерпретація результатів розв’язання задач лінійного програмування (в 1939 році Л.В. Канторович оприлюднив монографію "Математичні методи організації і планування виробництва"). Сам термін "лінійне програмування" був введений дещо пізніше, в 1951 році, у працях американських вчених Дж. Данцига та Г. Кумпанса. Проте у своїй монографії Дж. Данциг зазначає, що Л.В. Канторовича слід визнати першим, хто виявив, що широке коло важливих виробничих задач може бути подане у чіткому математичному формулюванні, що дає можливість здійснити підхід до таких задач з кількісного боку та розв’язати їх чисельними методами.

В 1947 році Дж. Данциг розробив основний метод розв’язування задач лінійного програмування - симплексний метод, що стало початком формування лінійного програмування як самостійного напрямку в математичному програмуванні. Наступним кроком стали праці Дж. Неймана (1947 р.) щодо розвитку концепції двоїстості, що сприяло розширенню практичної сфери застосування методів лінійного програмування.

Періодом найінтенсивнішого розвитку математичного програмування є п’ятдесяті роки. У цей час з’являються розробки нових алгоритмів, теоретичні дослідження з різних напрямків математичного програмування зокрема в 1951 році вийшла праця Г. Куна і А. Таккера, в якій наведено необхідні та достатні умови оптимальності нелінійних задач; в 1954 році Чарнес і Лемке розглянули наближений метод розв’язання задач з сепарабельним опуклим функціоналом та лінійними обмеженнями; в 1955 році опубліковано ряд робіт, присвячених квадратичному програмуванню, крім того в п’ятдесятих роках сформувався новий напрямок математичного програмування - динамічне програмування, в розвиток якого значний вклад вніс американський математик Р. Белман.

У період найбурхливішого розвитку математичного програмування за кордоном у Радянському Союзі не спостерігалося значних досягнень через штучні ідеологічні обмеження. Відродження досліджень з математичного моделювання економіки почалося в 60-80-тих роках і стосувалося опису "системи оптимального функціонування соціалістичної економіки". Серед радянських вчених того періоду слід виокремити праці В.С. Немчинова, В.В. Новожилова, Н.П. Федоренка, С.С. Шаталіна, В.М. Глушкова, В.С. Михалевича, Ю.М. Єрмольєва та ін.

Першою задачею цілочислового типу яка була опублікована угорським математиком Б. Егерварі в 1932 році, задача про призначення персоналу. Систематичні дослідження цілочислового програмування починаються з 1955р., коли на Другому симпозіумі з лінійного програмування була розглянута задача про бомбардувальника, відома також як задача про ранець.

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

1.2 Постановка задачі

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

Задача цілочислового програмування записується так:

, (1.1)

за умов

;  (1.2)

  (1.3)

  (1.4).

Для знаходження оптимального розв'язку цілочислових задач застосовують спеціальні методи. Найпростішим методом розв'язування цілочислової задачі є знаходження її оптимального розв'язку як задачі, що має лише неперервні змінні, з подальшим округленням останніх. Такий підхід часто є виправданим.

Для знаходження оптимальних планів задач цілочислової програмування застосовують дві основні групи методів:

–       методи відтинання;

–       комбінаторні методи.

Основою методів відтинання є ідея поступового "звуження" області допустимих розв'язків розглядуваної задачі. Пошук цілочислового оптимуму починається з розв'язування задачі з так званими послабленими обмеженнями, тобто без урахування вимог цілочисловості змінних. Далі вводяться у модель спеціальні додаткові обмеження, що враховують цілочисловість змінних, многокутник допустимих розв'язків послабленої задачі поступово зменшуємо доти, доки змінні оптимального розв'язку не набудуть цілочислових значень. До цієї групи належать:

методи розв'язування повністю цілочислових задач (дробовий алгоритм Гоморі);

методи розв'язування частково цілочислових задач (другий алгоритм Гоморі, або змішаний алгоритм цілочислового програмування).

Комбінаторні методи цілочислової оптимізації базуються на повному переборі всіх допустимих цілочислових розв'язків, тобто вони реалізують процедуру цілеспрямованого перебору, під час якої розглядається лише частина розв'язків (досить невелика), а решта враховується одним зі спеціальних методів.

Найпоширенішим у цій групі методів є метод віток і меж. Починаючи з розв'язування послабленої задачі, він передбачає розбиття початкової задачі на дві підзадачі виключенням областей, що не мають цілочислових розв'язків, і дослідженням кожної окремої частини многокутника допустимих розв'язків.

Для розв'язування задач із бульовими змінними застосовують комбіновані методи, причому оскільки змінні є бульовими, то методи пошуку оптимуму значно спрощуються.

1.2 Приклади застосування цілочисельних задач лінійного програмування у плануванні та управлінні виробництвом

Задача про рюкзак. Найпростішою задачею цілочислового програмування, а саме задачею лише з одним обмеженням, є задача про рюкзак (або ранець). Така задача має багато прикладів практичного застосування. Назва "задача про рюкзак" пов’язана з інтерпретацією задачі вибору найкращого складу предметів, що задовольняють певні умови гіпотетичної проблеми туриста щодо вибору для походу оптимальної кількості речей.

Турист може вибирати потрібні речі із списку з n предметів. Відома вага кожного j-го предмета . Визначена також цінність кожного виду предметів . Максимальна вага всього вантажу в рюкзаку не може перевищувати зазначеного обсягу М. Необхідно визначити, скільки предметів кожного виду турист має покласти в рюкзак, щоб загальна цінність спорядження була максимальною за умови виконання обмеження на вагу рюкзака.

Позначимо через . - кількість предметів j-го виду в рюкзаку. Тоді математична модель задачі матиме вигляд:

, ;

, - цілі числа,

Приклад 1.1:

Фермеру для удобрення земельної ділянки необхідно придбати 107 кг добрив. Він може купити добрива в упаковках по 35 кг вартістю 14 ум. од. або по 24 кг вартістю 12 ум. од. Метою фермера є закупівля не менше, ніж 107 кг добрив з мінімальними витратами. Причому потрібно купувати або цілу упаковку, або не купувати її зовсім, бо частину упаковки придбати неможливо.

Розв’язання. Позначимо кількість упаковок вагою 35 кг та вагою 24 кг відповідно змінними та . Маємо модель цієї задачі:

,

, ,,  - цілі числа.

У результаті розв’язування задачі будь-яким з вищенаведених методів отримаємо оптимальний план: , . Отже, за оптимальним планом найменші витрати, що дорівнюють 50 ум. од., можливі у разі закупівлі однієї упаковки добрив вагою 35 кг та трьох упаковок вагою по 24 кг.

Задача оптимального розкрою матеріалів. На підприємстві здійснюється розкрій m різних партій матеріалів у обсягах одиниць однакового розміру в кожній партії. Із матеріалів усіх партій потрібно виготовити максимальну кількість комплектів Z, у кожен з яких входить p різних видів окремих частин в кількості одиниць, враховуючи, що кожну одиницю матеріалу можна розкроїти на окремі частини n різними способами, причому у разі розкрою одиниці i-ої партії j-им способом отримуємо деталей r-го виду.

Запишемо математичну модель задачі. Позначимо через  - кількість одиниць матеріалу i-ої партії, що будуть розкроєні j-им способом. Тоді з i-ої партії за j-го способу розкрою отримаємо деталей r-го виду. З усієї ж i-ої партії у разі застосування до неї всіх n способів розкрою отримаємо деталей r-го виду, а з усіх m партій їх буде отримано . У кожен комплект має входити  деталей, тому відношення  визначає кількість комплектів, які можна виготовити з деталей r-го виду. Кількість повних комплектів для всіх видів деталей визначається найменшим з цих відношень.

У разі повного комплекту має виконуватися рівність відношень:

,

звідки p - 1 відношення можна виразити через будь-яке з них, наприклад, через перше:

,або ,.

Замінивши та їх значеннями, отримаємо p - 1 обмеження стосовно комплектів:

=,

Враховуючи наявну кількість одиниць матеріалу в партіях, запишемо m обмежень щодо ресурсів:

.

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

Отже, необхідно знайти найбільше значення функції:

за обмежень:

,

 - цілі числа .

Розглянемо приклад задачі оптимального розкрою матеріалів.

Приклад 1.2: У цеху розрізують прути завдовжки 6 м на заготівки довжиною 1,4, 2 і 2,5 м. Цех обслуговує двох замовників, для кожного з яких окремо необхідно знайти:

1.       як розрізати 200 прутів, щоб отримати не менше як 40, 60 і 50 заготівок завдовжки відповідно 1,4; 2 і 2,5 м. Критерій оптимізації - мінімум відходів;

2.       як розрізати 200 прутів для формування з отриманих заготівок комплектів, що складаються з двох заготівок довжиною 1,4 м, та по одній довжиною 2 і 2,5 м. Критерій оптимізації - максимальна кількість комплектів.

Розв’язання.

1) розв’яжемо задачу за умовами першого замовника. Маємо партію прутів у кількості  штук. Відома нижня межа кількості заготівок кожного виду. Введемо такі позначення:

 - вид заготівки;

 - спосіб розрізання прута;

 - вихід у разі розрізування прута j-им способом заготівок r-го виду;

 - відходи в разі розрізування прута j-им способом;

 - кількість наявних прутів;

 - нижня межа потреби в r-ій заготівці;

 - кількість прутів, які розрізані за j-им способом.

Запишемо математичну модель для розв’язування першого пункту задачі оптимального розкрою.

Критерієм оптимальності є мінімальна кількість відходів: .

Кількість отриманих заготівок кожного виду має бути не меншою від зазначених потреб:

Сумарна кількість прутів, які розрізані різними способами не може бути більшою від кількості наявних прутів:

.

Змінні задачі  - невід’ємні і цілі числа. Отже, маємо математичну модель:

,

,

 - цілі числа.

Побудуємо числову економіко-математичну модель розрізування прутів, розглянувши можливі варіанти їх розрізування:

Таблиця 1.0

Бажано, щоб у множину ввійшли всі можливі варіанти, навіть такі, які на перший погляд здаються неефективними, наприклад, Х6.

Запишемо числову економіко-математичну модель розрізування прутів:

за умов:

а) кількість заготівок завдовжки 1,4 м:

;

б) кількість заготівок завдовжки 2 м:

;

в) кількість заготівок завдовжки 2,5 м:

;

г) кількість наявних прутів:

;

д) невід’ємність змінних:

;

є) цілочисловість змінних:

 - цілі числа .

Отже, загалом маємо математичну модель виду:

 - цілі числа .

Розв’язуючи задачу одним із методів цілочислового програмування, отримуємо набір альтернативних оптимальних планів (загальною кількістю 146). Наприклад, такий план забезпечує виготовлення всіх видів заготівок у мінімально можливій кількості за найменшого загального обсягу відходів, причому для цього використовуються лише 54 прути: , , тобто 4 прути необхідно розрізати другим способом (по три заготівки довжиною 2 м) та 50 прутів четвертим способом (по одній заготівці кожного виду). Сумарна довжина залишків дорівнює п’яти метрам. Аналогічне значення цільової функції () дає оптимальний план, за яким виготовляється більша кількість кінцевої продукції та витрачається весь наявний матеріал:

.

Отримані оптимальні плани дають набір альтернативних варіантів для прийняття управлінських рішень за конкретних виробничих умов.

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

) розв’яжемо задачу за умовами другого замовника. Оскільки в другому пункті задачі відсутні обмеження щодо кількості заготівок, проте вимагається формування комплектів, необхідно дещо змінити позначення:

 - вид заготівки;

 - спосіб розрізування прута;

 - вихід у разі розрізування прута j-им способом заготівок r-го виду;

 - кількість наявних прутів;

 - кількість прутів, які розрізані за j-им варіантом;

 - кількість r-го виду заготівок у комплекті;

 - кількість всіх заготівок r-го виду.

Математична модель у цьому разі суттєво відрізняється від моделі, що розглянута вище.

З усього матеріалу може бути отримано заготівок r-го виду. У кожен комплект має входити дві заготівки першого типу , тому відношення визначає кількість комплектів, які можна скласти з заготівок першого виду. Аналогічно можна визначити кількість комплектів для інших видів заготівок  та .

Кількість можливих повних комплектів визначається найменшим з цих відношень:  (; ; ). До того ж у разі повного комплекту має виконуватися рівність відношень: ==, звідки два з відношень можна виразити, наприклад, через перше:

=; =, звідки,. ,

Замінимо та їх значеннями:

=або ;

=або .

Враховуючи наявну кількість одиниць матеріалу, запишемо обмеження щодо використання ресурсів:

.

Всі  мають задовольняти умову невід’ємності: , та цілочисловості.

Отже, необхідно знайти найбільше значення функції:

за обмежень:

, ,

 - цілі числа .

Запишемо числову математичну модель, скориставшись попередніми даними розрахунків можливих варіантів розрізування прутів (табл.6.5).

Із умов формування комплектів маємо: , тобто заготівок першого виду має бути вдвічі більше, ніж заготівок другого та третього виду.

Звідси випливає, що за мінімальну кількість комплектів може бути прийняте одне з двох відношень:  чи . Виберемо, наприклад, . Використовуючи дані таблиці, запишемо вираз для цільової функції:

.

Обмеження щодо формування комплектів матимуть вигляд: , або

,

Звідси

,

аналогічно для :

, або

.

Обмеження щодо використання наявних прутів:

.

Обмеження стосовно невід’ємності та цілочисловості змінних:

;

 - цілі числа .

Отже, загалом маємо таку математичну модель:

 - цілі числа .

Розв’язавши задачу будь-яким з вищеописаних методів, отримаємо оптимальний план:

,

комплектів.

Задача комівояжера. Розглядається n міст , що пов’язані між собою транспортною мережею. Відома матриця відстаней від кожного міста до усіх інших:

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

Позначимо:

Отже,  може набувати лише двох значень: одиниці або нуля. Такі змінні мають назву бульових змінних. Очевидно, що вони є цілочисловими. Цільовою функцією цієї задачі є мінімізація всього маршруту комівояжера:

,

де  - відстань між містами і та j.

Обмеження щодо одноразового в’їзду в кожне місто:

 .

Обмеження щодо одноразового виїзду з кожного міста:

 .

Зазначені обмеження не повністю описують допустимі маршрути і не виключають можливості розриву маршруту. Щоб усунути цей недолік, введемо невід’ємні цілочислові змінні , які в процесі розв’язування задачі набуватимуть значень порядкових номерів міст за оптимальним маршрутом прямування комівояжера. Запишемо обмеження, які усувають можливість існування підмаршрутів:

.

Доведемо, що для довільного маршруту, який починається в пункті, можна знайти такі , що задовольняють наведену нерівність. Нехай комівояжер переїжджає з міста  до міста  на р-му кроці і допустимо також, що , тоді з міста комівояжер вирушить на наступному, (р + 1) - му кроці і . Звідси випливає, що:

.

Така нерівність виконується для будь-яких значень i та j у разі, коли , а при  нерівність виконується як строге рівняння. Отже, якщо вибрано маршрут пересування з i-го міста до j-го, то згадана нерівність фіксує два підряд порядкових номери цих міст.

Отже, маємо таку математичну модель:

Приклад 1.3:

В економічному регіоні розміщено 6 пунктів (міст). Комівояжер, який виїжджає з міста 1, має побувати в кожному місті один раз і повернутися до вихідного пункту. Знайти найкоротший маршрут, якщо відстані між містами відомі (наведені в км на рис.1.1).

Рис.1.1

Розв’язання. Маємо 6 пунктів, де має побувати комівояжер.

Позначимо:

Отже,  - бульові (цілочислові) змінні. Запишемо числову економіко-математичну модель задачі комівояжера за даних умов.

Виходячи з рис.1.0, бачимо, що всіх можливих маршрутів є 12. З першого міста можна потрапити до кожного з п’яти інших, відповідно за такими маршрутами ,Друге місто пов’язане лише з трьома іншими, а саме, з першим, четвертим та п’ятим, отже, маємо такі три змінні:  Аналогічно позначаємо змінні, що відповідають можливим маршрутам пересувань з третього, четвертого, п’ятого та шостого міст:

з третього -

з четвертого - ,

з п’ятого -    

з шостого -   

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

Критерій оптимальності - мінімізація довжини всього маршруту комівояжера:

а) обмеження щодо одноразового в’їзду в кожне місто:

б) обмеження щодо одноразового виїзду з кожного міста:

в) обмеження щодо усунення підмаршрутів:

;

;

 - цілі числа.

Такі задачі розв’язуються спеціальними методами.

У результаті отримуємо оптимальний варіант пересування таким маршрутом (рис.1.2).

Тобто з першого міста за оптимальним планом необхідно переїжджати до четвертого, з четвертого - до третього, з третього - до шостого, з шостого - до п’ятого, з п’ятого - до другого, а з другого - до першого. Довжина цього маршруту є мінімальна, дорівнює 300 км.

Зауважимо, що аналогічні задачі нерідко виникають на практиці, особливо у дрібному бізнесі. Типовим може бути, наприклад, таке завдання: "Фірма у місті має 25 кіосків, які торгують безалкогольними напоями. Щоденно з бази автомобілем розвозять до них товар. Як оптимально організувати розвезення певного обсягу товару?".

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

Відомі обсяги кожного виду ресурсів ., а також норми використання i-го . виду ресурсів на одиницю виготовлення j-го . виду продукції .

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

.

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

Зауважимо, що виготовлення будь-якої кількості продукції потребує певних фіксованих та змінних  витрат, тобто загальна сума витрат на виготовлення продукції обсягом  визначається за формулою: . Однак у разі, якщо  (продукція не випускається), то розрахунок витрат за формулою призводить до додатного значення, що неправильно. Для адекватного відображення функціональної залежності загальних витрат від обсягу виробленої продукції j-го виду можна скористатися такою нелінійною функцією:

,

де є бульовими змінними виду:

Таку умову можна записати у вигляді лінійної нерівності. Допустимо, що існує таке досить велике число М, для якого умова  виконуватиметься для всіх допустимих значень . Тоді обмеження виду:

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

за умов:

;

;

 - цілі числа .

Приклад 1.4:

Фермер планує виробляти три види продукції: озиму пшеницю, цукрові буряки та молоко. Загальні витрати складаються з двох частин: постійних та змінних.

Відповідні дані наведені в табл.1:

Таблиця 1

Необхідно визначити оптимальний план виробництва продукції кожного виду за умови, що фермер має 100 га ріллі.

Розв’язання. Нехай  - обсяг виробництва j-го виду продукції m, . Функція загальних витрат на виробництво j-го виду продукції має вигляд:

.

Цільовою функцією в цьому прикладі може бути максимізація прибутку:

,

де  - ціна одиниці j-ї продукції.

Обмеження щодо використання ріллі запишемо так:

де  - норма потреби у ріллі на виробництво одиниці j-ї продукції; А - площа ріллі.

Загалом маємо таку математичну модель:

 ;

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

Отже, М може дорівнювати 5000. Звідси маємо:

за умов:

;

;

;

;

,;

 - цілі числа.

Розв’язавши задачу, отримаємо оптимальний план:

.

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

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

Задача планування виробничої лінії. Розглядається процес функціонування виробничої лінії. Відома схема, яка зображає послідовність робіт для виготовлення k видів продукції . Відомі також:  - тривалість виконання j-ї операції ;  - термін для k-го виробу, до якого необхідно завершити операцію j;  - момент початку j-ї операції; t - тривалість виконання всіх операцій. Передбачається, що в будь-який момент на верстаті виконується тільки одна операція. Необхідно визначити оптимальні моменти початку кожної операції.

Економіко-математична модель виробничої лінії міститиме такі групи обмежень:

. Послідовність виконання j-ї операції записується для всіх пар операцій так: якщо j-та операція передує i-й операції.

. Обмеження щодо нерозгалуженості виробничого процесу для операцій і та j, які не виконуються одночасно (i ≠ j), має вигляд:

або - =, якщо операція j передує операції і;

або  -  = , якщо операція і передує операції j.

Зауважимо, що логічні обмеження виду "або-або" не можуть входити до економіко-математичної моделі задачі лінійного програмування, оскільки вони породжують неопуклу множину допустимих розв’язків. Тому необхідно ввести допоміжні змінні, які уможливлюють запис наведених вище логічних умов у вигляді лінійних обмежень. Це такі бульові змінні:

Скориставшись прийомом з попереднього прикладу (введення досить великого числа М), запишемо обмеження:

; ,

де М - досить велике число.

. Обмеження щодо термінів виготовлення кожного виробу:

,

де j - остання операція для k-го виробу.

. Усі операції мають бути виконані до моменту t:

,

Критерій оптимальності: ,

тобто ставиться завдання, щоб тривалість виготовлення всіх видів виробів була мінімальною.

Отже, маємо таку математичну модель:

 - цілі числа .

Приклад 1.5:

Потрібно оптимізувати функціонування виробничої лінії, яка охоплює 11 операцій з виготовлення двох виробів. Лінію обладнано одним багатоопераційним верстатом. Послідовність і тривалість (у хвилинах) виконання операцій відображені на рис.6.9.

Рис.1.3

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

Розв’язання. Позначивши через  момент початку j-ої операції, запишемо числову економіко-математичну модель функціонування виробничої лінії:

за наведених нижче умов.

. Обмеження стосовно послідовності виконання операцій:

;

;

;

;

;

;

;

;

;

;

;

.

. Обмеження щодо нерозгалуженості виробничого процесу:

;

;

;

;

...........

;

;

...........

;

.

. Обмеження щодо тривалостей виготовлення виробів:

;

.

. Усі операції мають бути виконані до моменту t:

;

;

;

.....

;

.....

.

. Обмеження щодо невід’ємності змінних:

;

 - цілі .

Отже, маємо частково цілочислову задачу з бульовими змінними.

Задача про призначення. Ця задача зводиться до транспортної і може бути розв’язана одним з відомих методів знаходження оптимального плану транспортної задачі. Проте, такий вид задач належить до задач цілочислового програмування, оскільки їх змінні є бульовими і оптимальний план може бути знайденим також методами цілочислового програмування. Не повертаючись до загальної постановки задачі та побудови її математичної моделі, наведемо ще один приклад задачі про призначення.

Приклад 1.6:

Необхідно розподілити чотирьох робітників за чотирма видами устаткування так, щоб їх загальна продуктивність праці була максимальною. Дані стосовно продуктивності праці кожного робітника на устаткуванні кожному виду наведено в табл.1.4:

Таблиця 1.4

Розв’язання. Зазначимо, що дану задачу можна розглядати як транспортну, в якій робітники ототожнюються з постачальниками вантажів, а види устаткування - зі споживачами цих вантажів. Обсяги пропозиції та попиту в кожному разі дорівнюють одиниці. Отже, змінні будуть бульовими:

Якщо відома продуктивність праці і-го робітника на j-му устаткуванні, то числова модель про призначення набуває вигляду:

за умов:

;

;

;

;

;

;

;

.

;

 - цілі числа .

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

Розділ 2. Методи розвґязання задач цілочислового програмування

2.1 Геометрична інтерпретація розв’язків цілочислових задач лінійного програмування на площині

Для знаходження оптимального розв’язку цілочислових задач застосовують спеціальні методи. Найпростішим з них є знаходження оптимального розв’язку задачі як такої, що має лише неперервні змінні, з дальшим їх округленням. Такий підхід є виправданим тоді, коли змінні в оптимальному плані набувають досить великих значень у зіставленні їх з одиницями вимірювання. Нехай, наприклад, у результаті розв’язування задачі про поєднання галузей у сільськогосподарському підприємстві отримали оптимальне поголів’я корів - 1235,6. Округливши це значення до 1236, не припустимося значної похибки. Проте за деяких умов такі спрощення призводять до істотних неточностей. Скажімо, множина допустимих розв’язків деякої нецілочислової задачі лінійного програмування має вигляд, зображений на

рис.2.1

Максимальне значення функціонала для даної задачі знаходиться в точці В. Округлення дасть таке значення оптимального плану  (точка D на рис.2.1). Очевидно, що точка D не може бути розв’язком задачі, оскільки вона навіть не належить множині допустимих розв’язків (чотирикутник ОАВС), тобто відповідні значення змінних не задовольнятимуть систему обмежень задачі.

Зауважимо, що геометрично множина допустимих планів будь-якої лінійної цілочислової задачі являє собою систему точок з цілочисловими координатами, що знаходяться всередині опуклого багатокутника допустимих розв’язків відповідної нецілочислової задачі. Отже, для розглянутого на рис.2.1 випадку множина допустимих планів складається з дев’яти точок (рис.2.2), які утворені перетинами сім’ї прямих, що паралельні осям  та  і проходять через точки з цілими координатами 0, 1,2. Для знаходження цілочислового оптимального розв’язку пряму, що відповідає цільовій функції, пересуваємо у напрямку вектора нормалі  до перетину з кутовою точкою утвореної цілочислової сітки. Координати цієї точки і є оптимальним цілочисловим розв’язком задачі. У нашому прикладі оптимальний цілочисловий розв’язок відповідає точці М ().

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

Графічний метод

Якщо модель містить тільки дві змінні, задачу можна розв’язати графічно. У випадку трьох змінних графічний розв’язок стає менш наочним, а при більшому числі змінних - взагалі неможливим. Незважаючи на це, розгляд графічного методу дасть змогу зробити висновки, що послужать основою для розробки загального методу розв’язання задач лінійного програмування.

Перший крок при використанні графічного методу полягає в поданні області допустимих розв’язків, у якій водночас задовольняються всі обмеження моделі. Нехай шукана область (простір) розв’язків задачі показана. Умови невід’ємності змінних обмежують область їх допустимих значень. Інші межі простору розв’язків потрібно зобразити прямими лініями, побудованими по рівняннях, що отримані заміною знака "≤" чи "≥" знаком "=" в обмеженнях. Області, в яких відповідні обмеження виконуються як нерівності, указуються стрілками, спрямованими вбік допустимих значень змінних. Отримуємо простір розв’язків задачі. У кожній точці, що належить внутрішній області або межам, всі обмеження виконуються, тому розв’язки, що відповідають цим точкам, є допустимими. Серед безкінечного числа таких точок можна знайти точку оптимального розв’язку, якщо з'ясувати, в якому напрямку зростає цільова функція. На графік наносять лінію рівня цільової функції , де  _- довільне значення . Будують вектор , що є нормаллю до ліній рівня цільової функції й визначає напрямок оптимізації . Лінію рівня зрушують паралельно самій собі вздовж вектора  доти, поки вона не вийде за межі області допустимих розв’язків. Остання точка цієї області й буде точкою оптимуму.

Значення  та  в розв’язуючій точці визначаються шляхом розв’язання системи рівнянь.

Зазначимо, що у випадку, коли лінії рівня  мають такий самий нахил, як пряма зв’язуючого обмеження (тобто такого, що проходить через оптимальну точку), матимемо безліч оптимумів на відрізку.

Графічний спосіб розв'язування ґрунтується на геометричній інтерпретації задачі лінійного програмування, тому він досить простий для розуміння. Недоліком є те, що графічним способом можна розв’язати задачу, в якій в обмеженнях є лише дві змінні, потрібно намагатися малювати лінії з найбільшою точністю, в протилежному випадку можна отримати велику похибку, а в результаті неправильне рішення.

2.2 Методи відтинання. Метод Гоморі

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

Переважно розв’язок не задовольнятиме умову цілочисловості. Тоді накладають додаткове обмеження, яке не виконується для отриманого плану задачі, проте задовольняє будь-який цілочисловий розв’язок.

Таке додаткове обмеження називають правильним відтинанням. Система лінійних обмежень задачі доповнюється новою умовою і далі розв’язується отримана задача лінійного програмування. Якщо її розв’язок знову не задовольняє умови цілочисловості, то будується нове лінійне обмеження, що відтинає отриманий розв’язок, не зачіпаючи цілочислових планів. Процес приєднання додаткових обмежень повторюють доти, доки не буде знайдено цілочислового оптимального плану, або доведено, що його не існує.

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

Отриманий новий багатогранник розв’язків містить всі цілі точки, які були в початковому, і розв’язок, що буде отримано на ньому, буде цілочисловим (рис.2.3).

Слід відмітити, що визначення правила для реалізації ідеї Данціга стосовно формування додаткового обмеження виявилось досить складним завданням і першим, кому вдалось успішно реалізувати цю ідею, був Гоморі.

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

Нехай маємо задачу цілочислового програмування:

 (1.5)

за умов:

 (1.6)

, (1.7)

 - цілі числа  (1.8).

Допустимо, що параметри   - цілі числа.

Не враховуючи умови цілочисловості, знаходимо розв’язок задачі (1.5) - (1.7) симплексним методом. Нехай розв’язок існує і міститься в такій симплексній таблиці:

Таблиця 1.5