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

Тип работы:
Дипломная
Предмет:
Программирование


Узнать стоимость новой

Детальная информация о работе

Выдержка из работы

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

Зміст

  • Вступ
  • Розділ 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

Довжина заготівки, м

Варіант розрізування прутів

1,4

4

-

-

1

1

2

2

2

-

3

-

1

2

1

-

2,5

-

-

2

1

-

-

1

Довжина відходів, м

0,4

0

1

0,1

0,6

1,2

0,7

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

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

за умов:

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

;

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

;

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

;

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

;

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

;

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

— цілі числа.

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

— цілі числа.

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

.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

=або;

=або.

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

.

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

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

за обмежень:

, ,

— цілі числа.

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

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

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

.

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

,

Звідси

,

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

, або

.

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

.

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

;

— цілі числа.

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

max

— цілі числа.

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

,

комплектів.

Задача комівояжера. Розглядається 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

Показник

Вид продукції

озима пшениця

цукрові буряки

молоко

Постійні витрати, тис. грн.

40

70

20

Змінні витрати на одиницю продукції, грн/т

400

150

500

Норма потреби в ріллі, га/т

0,2

0,02

0,25

Ціна одиниці продукції, грн/т

800

300

1000

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

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

.

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

,

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

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

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

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

;

;

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

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

за умов:

;

;

;

;

,;

— цілі числа.

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

.

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

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

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

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

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

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

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

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

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

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

; ,

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

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

,

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

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

,

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

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

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

— цілі числа.

Приклад 1. 5:

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

Рис. 1. 3

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

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

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

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

;

;

;

;

;

;

;

;

;

;

;

.

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

;

;

;

;

;

;

;

.

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

;

.

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

;

;

;

;

.

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

;

— цілі.

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

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

Приклад 1. 6:

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

Таблиця 1. 4

Робітник

Продуктивність праці на устаткуванні, грн/год

1

2

3

4

1

12

9

8

7

2

10

7

6

5

3

9

6

4

4

4

8

5

3

2

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

Якщо відома продуктивність праці і-го робітника на 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

Базис

Сбаз

План

.

.

.

.

1

0

.

0

.

0

1

.

0

.

.

.

.

.

.

.

.

.

.

.

0

0

.

1

.

Змінні - базисні, а — вільні. Оптимальний план задачі:. Якщо — цілі числа, то отриманий розв’язок є цілочисловим оптимальним планом задачі (1. 5) — (1. 8). Інакше існує хоча б одне з чисел, наприклад, — дробове. Отже, необхідно побудувати правильне обмеження, що відтинає нецілу частину значення.

Розглянемо довільний оптимальний план задачі (1. 5) — (1. 7). Виразимо в цьому плані базисну змінну через вільні змінні:

. (1. 9)

Виразимо коефіцієнти при змінних даного рівняння у вигляді суми їх цілої та дробової частин. Введемо позначення: — ціла частина числа b, — дробова частина числа b*1. Отримаємо:

1. Цілою частиною числа, а називається найбільше ціле число, що не перевищує а. Дробовою частиною є число, яке дорівнює різниці між самим числом, а та його цілою частиною, тобто =.

Наприклад, для = =2, ==;

для = =,

, (1. 10)

. (1. 11)

Отже, рівняння (1. 11) виконується для будь-якого допустимого плану задачі (1. 5) — (1. 7). Допустимо тепер, що розглянутий план є цілочисловим оптимальним планом задачі. Тоді ліва частина рівняння (1. 11) складається лише з цілих чисел і є цілочисловим виразом. Отже, права його частина також є цілим числом і справджується рівність:

, (1. 12)

де N — деяке ціле число.

Величина N не може бути від'ємною. Якщо б, то з рівняння (1. 12) приходимо до нерівності:

.

Звідки. Тобто це означало б, що дробова частина перевищує одиницю, що неможливо. У такий спосіб доведено, що число N є невід'ємним.

Якщо від лівої частини рівняння (2. 12) відняти деяке невід'ємне число, то приходимо до нерівності:

, (1. 13)

яка виконується за допущенням для будь-якого цілочислового плану задачі (1. 5) — (1. 7). У такий спосіб виявилося, що нерівність (1. 13) є шуканим правильним відтинанням.

Отже, для розв’язування цілочислових задач лінійного програмування (1. 1) — (1. 4) методом Гоморі застосовують такий алгоритм:

1. Симплексним методом розв’язується задача без вимог цілочисловості змінних — (1. 1) — (1. 3).

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

Якщо задача (1. 1) — (1. 3) не має розв’язку (цільова функція необмежена, або система обмежень несумісна), то задача (1. 1) — (1. 4) також не має розв’язку.

2. Коли в умовно-оптимальному плані є дробові значення, то вибирається змінна, яка має найбільшу дробову частину. На базі цієї змінної (елементів відповідного рядка останньої симплексної таблиці, в якому вона міститься) будується додаткове обмеження Гоморі:

.

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

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

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

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

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

Приклад 2. 1 Сільськогосподарське підприємство планує відкрити сушильний цех на виробничій площі 190 м², маючи для цього 100 тис. грн і можливість придбати устаткування двох типів: А і В. Техніко-економічну інформацію стосовно одиниці кожного виду устаткування подано в табл.1. 6:

Таблиця 1. 6

Показник

Устаткування

Ресурс

А

В

Вартість, тис. грн

25

10

100

Необхідна виробнича площа, м

40

20

190

Потужність, тис. грн/рік

350

150

-

Розв’язання. Нехай і -кількість комплектів устаткування відповідно типу, А і В.

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

,;

; ,

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

Розв’язуємо задачу, нехтуючи умовою цілочисловості. Остання симплексна таблиця набуде вигляду:

Таблиця 6. 3

План

350

150

0

0

350

1

1

0

150

0

1

1475

0

0

10

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

.

Оскільки, ,, то додаткове обмеження набуває вигляду:

.

Зведемо його до канонічної форми та введемо штучну змінну:

.

Приєднавши отримане обмеження до симплексної таблиці (табл.6. 3) з умовно-оптимальним планом, дістанемо:

Таблиця 6. 4

План

350

150

0

0

0

— М

350

1

1

0

0

0

150

0

1

0

0

0

0

-1

1

1475

0

0

10

0

0

0

0

М

0

Розв’язавши наведену задачу, знаходимо цілочисловий оптимальний план:

.

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

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

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

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

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

Тобто допустиме ціле значення має задовольняти одну з нерівностей виду:

або.

Дописавши кожну з цих умов до задачі з послабленими обмеженнями, дістанемо дві, не пов’язані між собою, задачі.

Тобто, початкову задачу цілочислового програмування (1. 1) — (1. 4) поділимо на дві задачі з урахуванням умов цілочисловості змінних, значення яких в оптимальному плані послабленої задачі є дробовими.

Це означає, що симплекс-методом розв’язуватимемо дві такі задачі:

перша задача:

(1. 14)

за умов

; (1. 15), (1. 16)

(1. 17),, (1. 18)

друга задача

(1. 19)

за умов:

,; (1. 20)

; (1. 21)

— цілі числа; (1. 22)

, (1. 23)

де -дробова компонента розв’язку задачі (1. 1) — (1. 4).

Наведені задачі (1. 14) — (1. 18) і (1. 19) — (1. 23) спочатку послаблюємо, тобто розв’язуємо з відкиданням обмежень (1. 17) і (1. 22). Якщо знайдені оптимальні плани задовольняють умови цілочисловості, то ці плани є розв’язками задачі (1. 1) — (1. 4). Інакше пошук розв’язку задачі триває. Для дальшого розгалуження вибираємо розв’язок задачі з більшим значенням цільової функції, якщо йдеться про максимізацію, і навпаки — з меншим значенням цільової функції в разі її мінімізації. Подальше розгалуження виконується доти, доки не буде встановлено неможливість поліпшення розв’язку. Здобутий останній план — оптимальний.

Показать Свернуть
Заполнить форму текущей работой