Методы операционного исследования

 (1.5)

при обмеженнях

 (1.6)

 (1.7)

Обмеження (1.6) означає, що план всіх робіт має бути виконаний повністю, а обмеження (1.7) — що ресурси мають бути витрачені цілком.

2.  Математична модель задачі лінійного програмування (ЗЛП).

Задачу лінійного програмування можна сформулювати так

знайти

 (2.1)

при умовах

 (2.2)

та

 (2.3)

Обмеження (2.3) називають умовами позитивності. В даному випадку всі умови мають вигляд нерівностей. Інколи вони можуть бути змішаними, тобто нерівності і рівності.

 Визначення 3. Допустимим  безліччю рішень задачі (2.1) —(2.3) називається безліч R(х) всіх векторів  Х, що задовольняють умовам (2.2) і (2.3).

Очевидна безліч R(х) є опуклою багатогранною безліччю або опуклим многогранником.

Відзначимо, що оскільки min f(х) еквівалентний max[-f(х)], то завдання ЛП завжди можна звести до еквівалентного завдання максимізації.

Стандартна форма завдання лінійного програмування.

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

 

Допустимі базисні рішення.

 Хай обмеження завдання  ЛП задані у формі рівнянь, тобто завдання записане в  стандартній формі і містить m рівнянь і n змінних. Тоді всі допустимі  крайні точки безлічі допустимих  рішень визначаються, як всі однозначні ненегативні вирішення системи m рівнянь, в яких n-m змінних дорівнюють нулю. Однозначні вирішення такої системи рівнянь, що отримуються шляхом прирівнювання до нуля (n-m) змінних, називаються базисними рішеннями. Якщо базисне рішення задовольняє вимозі позитивності, воно називається допустимим базисним рішенням. Змінні, що мають нульове значення називаються небазисними або вільними змінними, а останні базисними.

 

Основні теореми лінійного програмування.

В основі методів вирішення завдань лінійного програмування лежать наступні теореми. Основна теорема лінійного програмування, що встановлює місце знаходження оптимальних рішень.

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

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

Теорема 2.2. Кожне допустиме базисне рішення відповідає крайній точці R.

Справедлива також наступна теорема, зворотна до теореми 2.2.

Теорема 2.3. Якщо  — крайня точка допустимої безлічі вирішень R, то відповідне вирішення x0 — є допустимим базисним вирішенням системи обмежень завдання лінійного програмування.

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

Симплекс-метод.

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

Аналіз рішення на чутливість.

З оптимальної симплекс-таблиці або безпосередньо, або за допомогою простих перетворень можна отримати інформацію.

1.  Оптимального рішення: значення базисних змінних записані  в стовпці В оптимальної симплекс-таблиці. Оптимальне значення цільової  функції знаходиться на перетині z-рядка і стовпця В в оптимальній симплекс таблиці. Для розглянутого прикладу: x1=10/3, x2=4/3, s1=s2=0, s3=3, s4=2/3, Zmax=12 2/3.

2.  Статусу ресурсів: ресурс  називається дефіцитним, якщо в  оптимальному рішенні він використаний  повністю. Залишкова змінна, відповідна  дефіцитному ресурсу в оптимальному  рішенні дорівнює нулю. Для розглянутого  прикладу дефіцитними будуть  ресурси 1 і 2, оскільки s1=s2=0.

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

4.  Чутливості оптимального  рішення до змін запасів ресурсів, варіацій коефіцієнтів цільової  функції і інтенсивності вжитку  ресурсів.

 

 

Подвійність в лінійному програмуванні.

Будь-яке завдання максимізації з економічної точки зору можна розглядати як завдання про розподіл обмежених ресурсів b1, b2., bn між різними споживачами, наприклад, між деякими технологічними процесами, які представляються стовпцями A1, А2 ..., Аm матриці обмежень завдання. Будь-яке допустиме рішення задачі лінійного програмування х1, х2 ..., хm дає конкретний розподіл, що вказуює ту долю кожного з ресурсів, яка має бути використана при здійсненні відповідного технологічного процесу.

Методи рішення цілочисельних ЗЛП.

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

Методи вирішення завдань цілочисельного програмування можна класифікувати як методи відсікань (1) і комбінаторні методи (2).

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

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

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

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

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

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

Базисні змінні	x1	…	xi	…	xm	w1	…	wj	…	wn	Рішення
Z	0	…	0	…	0	C1	…	Cj	…	Cn	b0
x1	1	…	0	…	0	a11	…	aj1	…	an1	b1
…	…	…	…	…	…	…	…	…	…	…	…
xi	0	…	1	…	0	a1i	…	aji	…	ani	bi
...	…	…	…	…	…	…	…	…	…	…	…
xm	0	…	0	…	1	a1m	…	ajm	…	anm	bm

Таблиця 4. Симплекс-таблиця з ослабленими обмеженнями.

Розглянемо i-ий рядок, якому відповідає неціле значення базисної змінної Хi, і виразимо Хi через небазисні змінні:

, bI – неціле.

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

bI=[bI]+fi, aji=[aji]+fij, 0<fi<1, 0£fij<1.

Як додаткове обмеження вводимо таке

,

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

Задача лінійного програмування транспортного типу.

Постановка завдання. Нехай в m пунктах виробляють деякий однорідний продукт, причому обсяг виробництва в пункті І складає Ai одиниць. Допустимо, що даний продукт споживається в n пунктах вжитку, а об'єм вжитку в пункті j складає одиниць Bj. Передбачимо, що з кожного пункту виробництва І можливе транспортування продукту в будь-який пункт вжитку j з витратами cij. Завдання полягає у визначенні такого плану перевезень, при якому запити всіх споживачів повністю задоволені, весь продукт вивезений з пунктів виробництва і сумарні транспортні витрати мінімальні.

Математична модель. Нехай Хij – кількість продукту, що перевозиться з пункту І в пункт j. Знайти безліч тих змінних , що задовольняють умовам

,

.

Та таких, що цільова функція

досягає мінімуму.

Метод рішення транспортної задачі [6, 7, 10].

Сітьові моделі.

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

Завдання мінімізації сітки.

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