Тут (1) називається системою обмежень, її матриця має ранг r? n, (2) - функцією цілі (цільовою функцією). Невід'ємне рішення (х10, x20, ..., xn0) системи (1) називається допустимим рішенням (планом) ЗЛП. Допустиме рішення називається оптимальним, якщо воно звертає цільову функцію (2) в min або max (оптимум).
2. Симплексних форма ЗЛП. Для вирішення ЗЛП симплекс - методом необхідно її привести до певної (симплексного) формі:
(2 `) f + cr 1 xr 1 + ... + Csxs + ... + Cnxn = b0? min
Тут вважаємо r
У системі (1 `) невідомі х1, х2, ... , Хr називаються базисними (кожне з них входить в один і тільки одне рівняння з коефіцієнтом 1), решта хr 1, ... , Xn - вільними. Допустиме рішення (1 `) називається базисним (опорним планом), якщо всі вільні невідомі рівні 0, а відповідне йому значення цільової функції f (x10, ..., xr0, 0, ..., 0) називається базисним.
У силу важливості особливостей симплексного форми висловимо їх і словами:
а) система (1 `) задовольняє умовам:
1) всі обмеження - у вигляді рівнянь;
2) всі вільні члени невід'ємні, тобто bi? 0;
3) має базисні невідомі;
б) цільова функція (2 `) задовольняє умовам:
1) містить тільки вільні невідомі;
2) всі члени перенесені вліво, крім вільного члена b0;
3) обов'язкове мінімізація (випадок max зводиться до min за формулою max f = - min (-f)).
3) Матрична форма симплекс-методу. Симплексного формі ЗЛП відповідає симплекс - матриця:
1 0 ... 0 ... 0 a1, r +1 ... a1s ... a1n b1
0 +1 ... 0 ... 0 a2, r +1 ... a2s ... a2n b2
.................................................. ...............< br />
0 0 ... 1 ... 0 ai, r +1 ... ais ... ain bi
.................................................. ...............< br />
0 0 ... 0 ... 1 ar, r +1 ... ars ... arn br
0 0 ... 0 ... 0 cr 1 ... cs ... cn b0
Зауважимо, що кожному базису (системі базисних невідомих) відповідає своя симплекс - матриця, базисна рішення х = (b1, b2, ..., br, 0, ..., 0) і базисна значення цільової функції f (b1, b2, ..., br, 0, ..., 0) = b0 (див. Останній стовпець!).
Критерій оптимальності плану. Якщо в останній (цільової) рядку симплекс-матриці всі елементи непозитивно, без врахування останнього b0, то відповідний цій матриці план оптимальний,
тобто сj? 0 (j = r +1, n) => min f (b1, ..., b2, 0, ..., 0) = b0.
Критерій відсутності оптимальності. Якщо в симплекс-матриці є стовпець (S-й), в якому останній елемент СS> 0, a всі інші елементи непозитивно, то ЗЛП не має оптимального плану, тобто СS> 0, ais? 0 (i = 1, r) => min f = -?.
Якщо в симплекс-матриці не виконуються обидва критерії, то в пошуках оптимуму треба переходити до наступної матриці за допомогою деякого елемента ais> 0 і наступних перетворень (симплексних):
1) всі елементи i-го рядка ділимо на елемент a + is;
2) всі елементи S-го стовпця, крім ais = 1, замінюємо нулями;
3) всі інші елементи матриці перетворимо за правилом прямокутника, що схематично зображено на фрагменті матриці і дано у формулах:
akl `= akbais - ailaks = akl - ailaks;
ais ais
bk `= bkais - biaks; cl` = clais - csail
ais ais
Визначення. Елемент ais + називається що дозволяє, якщо перетворення матриці з його допомогою забезпечує зменшення (невозрастаніе) значення, цільової функції; рядок і стовпчик, на перетині яких знаходиться дозволяє елемент, також називаються вирішуючими.
Критерій вибору дозволяє елементу. Якщо елемент ais + задовольняє умові
bi = min bk
ais0 aks0 +
де s0 - номер обраного дозволяє стовпця, то він є що дозволяє.
4. Алгоритм симплекс-методу (по мінімізації).
1) систему обмежень і цільову функцію ЗЛП приводимо до симплексного формі;
2) складемо симплекс-матрицю з коефіцієнтів системи та цільової функції в симплексного формі;
3) перевірка матриці на виконання критерію оптимальності; якщо він виконується, то рішення закінчено;
4) при невиконанні критерію оптимальності перевіряємо виконання критерію відсутність оптимальності; у разі виконання останнього рішення закінчено - немає оптимального плану;
5) у разі невиконання обох критеріїв знаходимо дозволяє елемент для переходу до наступної матриці, для чого:
а) вибираємо дозволяє стовпець за найбільшим з поклади тільних елементів цільової рядка;
б) вибираємо роздільну рядок за критерієм вибору дозволяє елемента; на їх перетині знаходиться дозволяє елемент;
6) c допомогою дозволяє елемента і симплекс-перетворень переходимо до наступної матриці;
7) знову отриману симплекс-матрицю перевіряємо описаним вище способом (див. п. 3)
Через кінцеве число кроків, як правило одержуємо оптимальний план ЗЛП або його відсутність
Зауваження.
1) Якщо у роздільній рядку (стовпці) є нуль, то у відповідному йому стовпці (рядку) елементи залишаються без зміни при симплекс-перетворення.
2) перетворення - обчислення зручно починати з цільовою рядка; якщо при цьому виявиться, що виконується критерій оптимальності, то можна обмежитися обчисленням елементів останнього стовпця.
3) при переході від однієї матриці до іншої вільні члени рівнянь залишаються невід'ємними; поява негативного
ного члена сигналізує про допущену помилку в попередніх розрахунках.
4) правильність отриманого відповіді - оптимального плану - перевіряється шляхом підстановки значень базисних невідомих у цільову функцію; відповіді повинні співпасти.
5. Геометрична інтерпретація ЗЛП і графічний метод рішення (при двох невідомих)
Система обмежень ЗЛП геометрично представляє собою багатокутник або багатокутну область як перетин півплощини - геометричних образів нерівностей системи. Цільова функція f = c1x1 + c2x2 геометрично зображує сімейство паралельних прямих, перпендикулярних вектору n (с1, с2).
Теорема. При переміщенні прямої цільової функції напрямку вектора n значення цільової функції зростають, у протилежному напрямку - зменшуються.
На цих твердженнях заснований графічний метод розв'язання ЗЛП.
6. Алгоритм графічного методу розв'язання ЗЛП.
1) У системі координат побудувати прямі по рівнянь, що відповідає кожному нерівності системи обмежень;
2) знайти півплощини рішення кожного нерівності системи (позначити стрілками);
3) знайти багатокутник (багатокутну область) рішень системи обмежень як перетин півплощини;
4) побудувати вектор n (с1, с2) за коефіцієнтами цільової функції f = c1x1 + c2x2;
5) в сімействі паралельних прямих цільової функції виділити одну, наприклад, через початок координат;
6) переміщати пряму цільової функції паралельно самій собі по області рішення, досягаючи max f при русі вектора n і min f під час руху в протилежному напрямку.
7) знайти координати точок max та min за кресленням і обчислити значення функції в цих точках (відповіді).
7. Постановка транспортної задачі.
Наведемо економічну формулювання транспортної задачі за критерієм вартості:
Однорідний вантаж, який є в m пунктах відправлення (виробництва) А1, А2, ..., Аm відповідно в кількостях а1, а2, ..., аm одиниць, потрібно доставити в кожний з n пунктів призначення (споживання) В1, В2,. .., Вn відповідно в кількостях b1, b2, ..., bn одиниць. Вартість перевезення (тариф) одиниці продукту з Ai в Bj відома для всіх маршрутів AiBj і дорівнює Cij (i = 1, m; j = 1, n). Потрібно скласти такий план перевезень, при якому весь вантаж з пунктів відправлення вивозитися і запити всіх пунктів споживання задовольняються (закрита модель), а сумарні транспортні витрати мінімальні.
Умови завдання зручно розташовувати в таблицю, вписуючи в клітини кількість вантажу, що перевозиться з Ai в Bj вантажу Xij> 0, а в маленькі клітини - відповідні тарифи Cij:
8. Математична модель транспортної задачі.
З попередньої таблиці легко вбачається і складається математична модель транспортної задачі для закритої моделі
Число r = m + n - 1, яке дорівнює рангу системи (1), називається рангом транспортної задачі. Якщо число заповнених клітин (Xij? 0) в таблиці дорівнює r, то план називається невироджених, а якщо це число менше r, то план виродження - в цьому випадку в деякі клітини вписується стільки нулів (умовно заповнені клітини), щоб загальна кількість заповнених клітин дорівнювало r.
Випадок відкритої моделі? АI??? Bj легко зводиться до закритої моделі шляхом введення фіктивного споживача Bn +1 c потребою bn 1 =? Ai-? Bj, або - фіктивного постачальника Аm 1 c запасом am +1 =? Bj-? ai; при цьому тарифи фіктивних учасників приймаються рівними 0.
9. Способи складання 1-таблиці (опорного плану).
I. Спосіб північно-західного кута (діагональний). Сутність способу полягає в тому, що на кожному кроці заповнюється ліва верхня клітка (північно-західна), що залишилася, таблиці, причому максимально можливим числом: або повністю вивозитися вантаж з АI, або повністю задовольняється потреба Bj. Процедура триває до тих пір, поки на якомусь кроці не вичерпаються запаси ai і не задовольняються потреби bj. На закінчення перевіряють, що знайдені компоненти плану Xij задовольняють горизонтальним і вертикальним рівнянь і що виконується умова невироджених плану.
II. Спосіб найменшого тарифу. Суть способу в тому, що на кожному кроці заповнюється та клітина, що залишилася, таблиці, яка має найменший тариф; у випадку наявності декількох таких рівних тарифів заповнюється кожна з них. В іншому діють аналогічно попередньому способу.
10. Метод потенціалів розв'язання транспортної задачі.
Визначення: потенціалами рішення називаються числа? I? Ai,? J? Bj, що задовольняють умові? I +? J = Cij (*) для всіх заповнених клітин (i, j).
Співвідношення (*) визначають систему з m + n-1 лінійних рівнянь з m + n невідомими, що має незліченну безліч рішень; для її визначеності одному невідомому надають будь-яке число (зазвичай? 1 = 0), тоді всі інші невідомі визначаються однозначно.
Критерій оптимальності. Якщо відомі потенціали рішення X0 транспортної завдання і для всіх незаповнених клітин виконуються умови?? I +? J?? Ci j, то X0 є оптимальним планом транспортної задачі.
Якщо план не оптимальний, то необхідно перейти до наступного плану (таблиці) так, щоб транспортні витрати не збільшилися.
Визначення: циклом перерахунку таблиці називається послідовність клітин, що задовольняє умовам:
1) одна клітка порожня, всі інші зайняті;
2) будь-які дві сусідні клітини знаходяться в одному рядку або в одному стовпці;
3) ніякі 3 сусідні клітини не можуть бути в одному рядку або в одному стовпці.
Порожній клітці присвоюють знак «+», іншим - по черзі знаки «-» і «+».
Для перерозподілу плану перевезень за допомогою циклу перерахунку спочатку знаходять незаповнену клітку (r, s), в якій? R +? S? Crs, і будують відповідний цикл; потім в мінусових клітинах знаходять число X = min (Xij). Далі складають нову таблицю за наступним правилом:
1) у плюсові клітини додаємо X;
2) з мінусових клітин віднімаємо Х;
3) всі інші клітини поза циклу залишаються без зміни.
Отримаємо нову таблицю, що дає нове рішення X, таке, що f (X1)?? F (X0); воно знову перевіряється на оптимальність через кінцеве число кроків обов'язково знайдемо оптимальний план транспортної задачі, бо він завжди існує.
11. Алгоритм методу потенціалів.
1) перевіряємо тип моделі транспортної задачі і у випадку відкритої моделі зводимо її до закритої;
2) знаходимо опорний план перевезень шляхом складання 1-й таблиці одним із способів - північно-західного кута або найменшого тарифу;
3) перевіряємо план (таблицю) на задоволення системі рівнянь і на невиражденность; у випадку виродження плану додаємо умовно заповнені клітини за допомогою «0»;
4) перевіряємо опорний план на оптимальність, для чого:
а) складаємо систему рівнянь потенціалів по заповненим клітинам;
б) знаходимо одне з її рішень при? 1 = 0;
в) знаходимо суми?? i +? j = C? ij ( «непрямі тарифи») для всіх порожніх клітин;
г) порівнюємо непрямі тарифи з істинними: якщо непрямі тарифи не перевершують відповідних істинних (C? ij?? Cij) у всіх пустих клітинах, то план оптимальний (критерій оптимальності). Рішення закінчено: відповідь дається у вигляді плану перевезень останньої таблиці і значення min f.
Якщо критерій оптимальності не виконується, то переходимо до наступного кроку.
5) Для переходу до наступної таблиці (плану):
а) вибираємо одну з порожніх клітин, де непрямий тариф більше дійсного (C? ij =?? i +? j> Cij);
б) складаємо цикл перерахунку для цієї клітини і розставляємо знаки «+», «-» в вершинах циклу шляхом їх чергування, приписуючи порожній клітці «+»;
в) знаходимо число перерахунку по циклу: число X = min (Xij), де Xij - числа в заповнених клітинах зі знаком «-»;
г) складаємо нову таблицю, додаючи X в плюсові клітини і відбираючи X з мінусових клітин циклу
6) Див п. 3 і т.д.
Через кінцеве число кроків (циклів) обов'язково приходимо до відповіді, бо транспортна задача завжди має рішення.
