Постановка задачі лінійного програмування.
1.Знайти найбільше значення функції F(X1,X2;Xn) = C1X1+C2X2+….+CnХn при обмежені а11х1+а12х2+...а1тХn<=в1, а21х1+а22х2+...а2nХn<=в2, а31х1+а32х2+...а3nХn<=в3, х1, х2...>=0, параметр Сj, аij, вij сталі величини.
Ф-ція F називаэться ф—цією мети або ф-цією цілі. Параметр Сj, аij, вij називається не керонваним параметром. Невідомі Х1,Х2,Хn називаються керованимипараметрами. Задача лінійного програмування полягає в тому, щоб знайти такі значення керованих параметрів, які б задовільняли обмеження і при яких ф-ція F приймає найбільше значення.
Вектор Х=(х1, х2, ... Xn) називається .... заадчі, якщо його координати х1, х2, ... Xn задовільняє обмеження задачі.
План Х*=(х1*, х2*, ... Xn*) при якому ф-ція досягає найбільшого значення називається оптимальним планом.
Якщо Х* - оптимальний план задачі, то для будь-якого Х має нерівність F(x)=F(x*).
Постановка двоїстої задачі
Нехай маємо задачу F(X1,X2;..Xn)= а1х1+а2х2+..+аnxn
Max
При обмежені
а11х1+а12х2+...+а1nxn<=b1
a21x1+a22x2+...+a2nxn<=b2
... ... ...
am1x1+am2x2+...+a2nxn<=bm
Двоїстість – це заперечення вихідних тверджень за певними правилами.
Двоїстою до вихідної задачі лінійного пргамуванння буде наступна задача лінійного програмування. Знайти найменше значення ф-ції: z(y1,y2,...,ym)=b1y+b2y2+...+bmYm
min
При обмеженнях
a11y1+a21y2+...+am1yn>=c1
………………………………………………………
y1, y2...ym>=0
max F = minZ
Постановка транспортної задачі.
Нехай деяка однорідна продукція знаходиться в постачальників. А1, А2, Ам відповідно в к-сті одиниць а1, а2, ам. Потреби у споживачів в В1, В2, Вn складають в1, в2, вn. Вартості перевезенння Сij.
Потрібно знайти такий план перевезення продукції, який:
а)дозволяє вивезти всю продукцію від постачальниа.
б)повністю задовільнити потреби споживачів
в)має найменшу вартість.
Записуються вихідні данні у вигляді таблиці.
Позначимо через Хij – к-сть одиниць продукції, яку планується перевозити від і-того постачальника до j-того споживача.
Планом буду матриця Х
EMBED Equation.3
Вартість перевезення становитиме.
F(x11*c11+x21*c12+…+x1nc1n+cx21*c21+x22*c22+…+x2nc2n)+..(xm1*cm1+xm2*cm2+...+xmn*cmn)
EMBED Equation.3
а)Умови виведення продукції від постачальників:
x11+x12+…+x1n=a1
x21+x22+…+x2n=a2
……
xm1+xm2+…+xmn=am
б)Умови забезпечення споживачів
x11+x21+…+xm1=b1
x12+x22+…+xm2=bn
x1n+x2n+…++xmn=bn
EMBED Equation.3 i=1,m EMBED Equation.3 ; і=1,m
Алгоритм методу потенціалів.
1.Серед наявних опорних планів транспортної задачі вибирають той, значення ф-ції мети на якому менша ніж значення ф-ції на інших планах.
2.Вибирають потенціали, які позначають вартість одиниці продукції в і-того постачальника Ui та й-того споживача Vj.
3.Записують сис рівнянь(Ui+Cij=Vij) для знаходження невідомих потенціалів, причому кожні рівність відповідає тільки заповненій клітинці даної таблиці.
4.Знаходять значення невідомих потенціалів із записаної сис рівнянь.
Для знаходження невідомих потенціалів значення потенціалу, яке найбільше зустрічається в сис прирівнюють до О, а потім знаходять значення решти потенціалів.
5.Перевіряють умову оптимальності плану: для всіх незаповнених клітинок таблиці повинна виконуватися рівність ?Ij=(Ui-Cij)-Vj>=0.
Якщо серед отриманих різниць ?Ij є від’ємні, то вибраний план не є оптимальний, тому переходимо до наступного кроку.
6.Будують цикл перерозподілу продукції між постачальниками та виробниками:
а)серед отриманих від’ємних різниць знаходять найменшу і клітинку до якої вона досягається відзначається символом „+”.
б)враховуючи відмічену клітинку таблиці будують цикл перерозподілу продукції. Вершини циклу почергово відмічають знаками „+” та „-”.
7.Вибирають к-сть продукції для перерозподілу – вибирають найменше число, здійснюють перерозподіл продукції між споживачами та постачальниками. До числа із клітинками зі знаками „+” до чисел з
„-”, віднімають к-сть продукції для перерозподілу.
8.Виписують новий опорний план задачі і знаходять значення заданої ф-ції на ньому.
9.Повертаємося до пункту 3.