У системі (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 bkais0 aks0 +
де s0 - номер обраного дозволяє стовпця, то він є що дозволяє.
4. Алгоритм симплекс-методу (по мінімізації).
5) систему обмежень і цільову функцію ЗЛП приводимо до симплексного формі;
6) складемо симплекс-матрицю з коефіцієнтів системи та цільової функції в симплексного формі;
7) перевірка матриці на виконання критерію оптимальності; якщо він виконується, то рішення закінчено;
8) при невиконанні критерію оптимальності перевіряємо виконання критерію відсутність оптимальності; у разі виконання останнього рішення закінчено - немає оптимального плану;
9) у разі невиконання обох критеріїв знаходимо дозволяє елемент для переходу до наступної матриці, для чого: а) вибираємо дозволяє стовпець за найбільшим з поклади тільних елементів цільової рядка; б) вибираємо роздільну рядок за критерієм вибору дозволяє елемента; на їх перетині знаходиться дозволяє елемент;
6) c допомогою дозволяє елемента і симплекс-перетворень переходимо до наступної матриці;
7) знову отриману симплекс-матрицю перевіряємо описаним вище способом (див. п. 3)
Через кінцеве число кроків, як правило одержуємо оптимальний план ЗЛП або його відсутність
Зауваження.
1) Якщо у роздільній рядку (стовпці) є нуль, то у відповідному йому стовпці (рядку) елементи залишаються без зміни при симплекс-перетворення.
2) перетворення - обчислення зручно починати з цільовою рядка; якщо при цьому виявиться, що виконується критерій оптимальності, то можна обмежитися обчисленням елементів останнього стовпця.
3) при переході від однієї матриці до іншої вільні члени рівнянь залишаються невід'ємними; поява негативного ного члена сигналізує про допущену помилку в попередніх розрахунках.
4) правильність отриманого відповіді - оптимального плану - перевіряється шляхом підстановки значень базисних невідомих у цільову функцію; відповіді повинні співпасти.
5. Геометрична інтерпретація ЗЛП і графічний метод рішення (при двохневідомих)
Система обмежень ЗЛП геометрично представляє собою багатокутник абобагатокутну область як перетин півплощини - геометричнихобразів нерівностей системи. Цільова функція f = c1x1 + c2x2 геометричнозображує сімейство паралельних прямих, перпендикулярних вектору n
(с1, с2).
Теорема. При переміщенні прямої цільової функції напрямку вектора nзначення цільової функції зростають, у протилежному напрямку --зменшуються.
На цих твердженнях заснований графічний метод розв'язання ЗЛП.
6. Алгоритм графічного методу розв'язання ЗЛП.
7) У системі координат побудувати прямі по рівнянь, що відповідає кожному нерівності системи обмежень;
8) знайти півплощини рішення кожного нерівності системи (позначити стрілками);
9) знайти багатокутник (багатокутну область) рішень системи обмежень як перетин півплощини;
10) побудувати вектор n (с1, с2) за коефіцієнтами цільової функції f = c1x1 + c2x2;
11) в сімействі паралельних прямих цільової функції виділити одну, наприклад, через початок координат;
12) переміщати пряму цільової функції паралельно самій собі по області рішення, досягаючи max f при русі вектора n і min f під час руху в протилежному напрямку.
13) знайти координати точок max та min за кресленням і обчислити значення функції в цих точках (відповіді).
Постановка транспортної задачі.
Наведемо економічну формулювання транспортної задачі за критеріємвартості:
Однорідний вантаж, який є в 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:
Математична модель транспортної задачі.
З попередньої таблиці легко вбачається і складається математичнамодель транспортної задачі для закритої моделі
Число 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.
Способи складання 1-таблиці (опорного плану).
Спосіб північно-західного кута (діагональний). Сутність способу полягає вте, що на кожному кроці заповнюється ліва верхня клітка (північно-західна), що залишилася, таблиці, причому максимально можливим числом: абоповністю вивозитися вантаж з АI, або повністю задовольняється потреба
Bj. Процедура триває до тих пір, поки на якомусь кроці не вичерпаютьсязапаси ai і не задовольняються потреби bj. На закінчення перевіряють, щознайдені компоненти плану Xij задовольняють горизонтальним і вертикальнимрівнянь і що виконується умова невироджених плану.
Спосіб найменшого тарифу. Суть способу в тому, що на кожному кроцізаповнюється та клітина, що залишилася, таблиці, яка має найменшийтариф; у випадку наявності декількох таких рівних тарифів заповнюється будь-яказ них. В іншому діють аналогічно попередньому способу.
Метод потенціалів розв'язання транспортної задачі.
Визначення: потенціалами рішення називаються числа ai ® Ai, bj ® Bj,задовольняють умові ai + bj = Cij (*) для всіх заповнених клітин (i, j).
Співвідношення (*) визначають систему з m + n-1 лінійних рівнянь з m + nневідомими, що має незліченну безліч рішень; для її визначеностіодному невідомому надають будь-яке число (зазвичай a1 = 0), тоді всі іншіневідомі визначаються однозначно.
Критерій оптимальності. Якщо відомі потенціали рішення X0 транспортноїзавдання і для всіх незаповнених клітин виконуються умови ai + bj Ј Ci j, то
X0 є оптимальним планом транспортної задачі.
Якщо план не оптимальний, то необхідно перейти до наступного плану (таблиці)так, щоб транспортні витрати не збільшилися.
Визначення: циклом перерахунку таблиці називається послідовність клітин,задовольняє умовам:одна клітка порожня, всі інші зайняті;будь-які дві сусідні клітини знаходяться в одному рядку або в одному стовпці;ніякі 3 сусідні клітини не можуть бути в одному рядку або в одному стовпці
.
Порожній клітці присвоюють знак «+», іншим - по черзі знаки «-» і
«+».
Для перерозподілу плану перевезень за допомогою циклу перерахунку спочаткузнаходять незаповнену клітку (r, s), в якій ar + bs> Crs, і будуютьвідповідний цикл; потім в мінусових клітинах знаходять число X = min (Xij).
Далі складають нову таблицю за наступним правилом:в плюсові клітини додаємо X;з мінусових клітин віднімаємо Х;всі інші клітини поза циклу залишаються без зміни.
Отримаємо нову таблицю, що дає нове рішення X, таке, що f (X1) Ј f (X0);воно знову перевіряється на оптимальність через кінцеве число кроківобов'язково знайдемо оптимальний план транспортної задачі, бо він завждиіснує.
Алгоритм методу потенціалів.перевіряємо тип моделі транспортної задачі і у випадку відкритої моделі зводимоїї до закритої;знаходимо опорний план перевезень шляхом складання 1-й таблиці одним зспособів - північно-західного кута або найменшого тарифу;перевіряємо план (таблицю) на задоволення системі рівнянь і наневиражденность; у випадку виродження плану додаємо умовно заповненіклітини за допомогою «0»;перевіряємо опорний план на оптимальність, для чого:а) складаємо систему рівнянь потенціалів по заповненим клітинам;б) знаходимо одне з її рішень при a1 = 0;в) знаходимо суми ai + bj = Cўij ( «непрямі тарифи») для всіх порожніх клітин;г) порівнюємо непрямі тарифи з істинними: якщо непрямі тарифи неперевершують відповідних істинних (Cўij Ј Cij) у всіх пустих клітинах, топлан оптимальний (критерій оптимальності). Рішення закінчено: відповідь дається ввигляді плану перевезень останньої таблиці і значення min f.
Якщо критерій оптимальності не виконується, то переходимо до наступногокроці.
Для переходу до наступної таблиці (плану):а) вибираємо одну з порожніх клітин, де непрямий тариф більше дійсного
(Cўij = ai + bj> Cij);б) складаємо цикл перерахунку для цієї клітини і розставляємо знаки «+», «-
»У вершинах циклу шляхом їх чергування, приписуючи порожній клітці« + »;в) знаходимо число перерахунку по циклу: число X = min (Xij), де Xij - числа взаповнених клітинах зі знаком «-»;г) складаємо нову таблицю, додаючи X в плюсові клітини і відбираючи X?мінусових клітин циклу
Див п. 3 і т.д.
Через кінцеве число кроків (циклів) обов'язково приходимо до відповіді, ботранспортна задача завжди має рішення.
