вівалентним (які мають той же безліч рішень) замінами змінних і заміною рівностей на пару нерівностей
Легко помітити, що завдання знаходження максимуму можна замінити завданням знаходження мінімуму, взявши коефіцієнти з протилежним знаком.
3. Постановка завдання
Компанія володіє трьома заводами: «А», «В», «С», з відповідними вартостями виробництва на одиницю об'єму «а1», «а2», «а3», обсяг виробництва «А1», «В2», « С3 »одиниць. Компанія зобов'язалася поставляти відповідно «w1», «x2», «y3», «z4» одиниць в міста W, X, Y, Z. Вартість одиниць перевезень від заводів до міст AW; AX; AY; AZ;
BW; BX; BY; BZ; CW; CX; CY; CZ. При заданих вартостях перевезень скласти оптимальний план виробництва і розподілу в магазини.
Приклад:
WXYZAA1BB2CC3 W1X2 Y3 Z4
4. Аналітичне рішення задачі
Алгоритм методу потенціалів
План транспортної задачі є оптимальним, якщо для всіх вільних клітин таблиці перевезень значення критерію оптимальності dij <= 0. Якщо для всіх вільних клітин таблиці перевезень критерій оптимальності dij <0, то цей план перевезень є єдиним. Якщо для деяких вільних клітин таблиці перевезень критерій оптимальності dij=0, то цей оптимальний план перевезень не є єдиним. Нарешті, якщо є вільні клітини, для яких критерій оптимальності dij> 0, то отриманий план перевезень не є оптимальним. Алгоритм методу потенціалів полягає в наступному: кожному постачальнику Ai ставиться у відповідність деяке число u, яке називається потенціалом Ai-того постачальника; кожному споживачеві Bj ставиться у відповідність деяке число v, яке називається потенціалом Bj-того споживача. Для кожної заповненої клітини, тобто для кожної базисної змінної будується співвідношення:
+ vj=cij
Отримуємо систему з числом рівнянь, рівним кількості базисних змінних. З цієї системи визначаємо невідомі потенціали ui і vj, вважаючи ui=0. Для кожної незаповненою клітини, тобто для кожної небазисной змінної, розраховуються непрямі тарифи cij * за формулою:
*=ui + vj.
Потім отриманий план перевіряють на оптимальність за критерієм оптимальності dij. Якщо для кожної незаповненою клітини виконується умова: dij <= cij * <= 0, то вихідний план є оптимальним. Якщо деякі dij> 0, то необхідно перейти до нового плану шляхом переміщення перевезення в клітку, що відповідає умові max (dij). Якщо таких клітин кілька, то вибирають будь-яку з них.
Для правильного переміщення перевезень, щоб не порушити обмеження завдання, будують так званий цикл, тобто замкнутий багатокутник, що з'єднує обрану клітку з неї ж самої і проходить через заповнені клітини.
Цикл будується наступним чином: викреслюються (подумки) всі рядки і стовпці, що містять рівно одну заповнену клітку, при цьому вважається, що обрана клітина без поставки є заповненою; всі залишилися після викреслювання клітини складають цикл і лежать в його кутах, вони з'єднуються ламаною лінією. У кожну клітину циклу, починаючи з незаповненою, по черзі вписують знаки + і -. У клітинах з негативними знаками вибирається мінімальна величина поставки, що позначається як D. У ті вершини, які мають знак + додається поставка D, а у вершинах зі знаком - пост...
