Графічний метод лінійного програмування.
1.На площині х1ох2 будують багатокутник розв’язків заданої задачі:
а)будують прямі р-ння, які отримують із заданих обмежень шляхом заміни символу „>=” на „=”
б)визначають півплощини, які відповідають заданим обмеженням. Для цього береть довільну точку на площині, яка не лежить на прямій 1. Н-д: беремо точку (0;0)і підставляємо її координати в першу нерівність. Якщо нерівність справджується, то перше обмеження визначає на площині півплощину, яка містить точку(0;0) і границя якої є перша пряма. Отримані півплощини відмічаємо стрілочками. Інші півплощини визначаються аналогічно.
в)знаходимо спільну частину знайдених співплощин – багатокутник розв’язку задач.
2.На площині х2ох2 будують певний вектор С – це градієнт заданої ф-ції(це напрям, у якому ф-ція найшвидше зростає).Якщо даний вектор не можна побудувати, то будують вектор пропорційний до нього.
3.Будують лінію нульового рівня заданої ф-ції, тобто множину точок на площині в яких ф-ція приймає значення 0.
4.Лінію нульового рівня переміщують в напрямку вектора паралельно самій собі, поки не буде знайдено остання спільна точка з багатокутником розв’язку(в цій точці ф-ція досягає найбільшого значення).
5.Знаходимо координати знайденої точки і значення ф-ції в ній.
Алгоритм симплекс методу.
1.Вихідну задачу лінійного програмування записують в основній формі. Це здійснюється за допомогою введення нових невідомих, які називаються вільними. Нові невідомі перетворюють частину обмежень задачі в рівності.
2.Вибирають початковий не вироджений план задачі, і знаходять значення заданої ф-ції на ньому.
3.Перевіряють план на оптимальність. Критерій оптимальності плану – останній рядок таблиці не містить від’ємних елементів. Якщо план не оптимальний то переходимо до наступного кроку.
4.Створюють нову симплекс таблицю за таким алгоритмом:
а)серед від’ємних елементів останнього рядка знаходять найменший, а стовпчик у якому він розміщений позначають стрілочкою, як спрямовуючий.
б)елементи стовпчика Ао ділять на додатні елементи спрямовуючого стовпчика, результати записують в останній стовпчик таблиці. Серед отриманих часток знаходять найменшу і даний рядок в якому він знаходиться позначають стрілочкою, як спрямовуючий.
в)знаходять головний елемент, такий який розміщений на перетині спрямовуючого стовпчика та рядка і відмічають його рамкою.
г)з базису виводимо вектор спрямовуючого рядка, а замість нього вводимо вектор спрямовуючого стовпчика.
д)елементи спрямовуючого рядка ділять на головний елемент і результат записують у відповідний рядок нової таблиці.
е)всі решти елементи спрямовуючого стовпика у новій таблиці беруть рівними 0.
є)всі решти елементи нової таблиці знаходять за правило прямокутника.
5.З нової симплекс таблиці отримують опорний план і значення ф-ції на ньому.
6.Знову перевіряємо план на оптимальність.
Алгоритм двоїстого симплекс методу.
1.Вибирається початковий псевдо план задачі і знаходиться значення ф-ції на ньому.
2.Перевіряють обраний псевдо план на оптимальність і заповнюють сиплекс таблицю. Критерій оптимальності плану – останній рядок таблиці не містить від’ємних елементів. Якщо план не оптимальний то переходимо до наступного кроку.
3.Створюють нову симплекс таблицю за таким алгоритмом:
а)серед від’ємних елементів першого стовпчика Ао знаходять найменший і рядок у якому він розміщений позначають стрілочкою, як спрямовуючий.
б)елементи останнього рядка ділять на від’ємні елементи спрямовуючого стовпчика. Серед отриманих часток знаходять найбільшу і даний стовпчик, в якому він знаходиться позначають стрілочкою, як спрямовуючий.
в)знаходять головний елемент, такий який розміщений на перетині спрямовуючого стовпчика та рядка і відмічають його рамкою.
г)з базису виводимо вектор спрямовуючого рядка, а замість нього вводимо вектор спрямовуючого стовпчика.
д)елементи спрямовуючого рядка ділять на головний елемент і результат записують у відповідний рядок нової таблиці.
е)всі решти елементи спрямовуючого стовпика у новій таблиці беруть рівними 0.
є)всі решти елементи нової таблиці знаходять за правило прямокутника.
4.З нової симплекс таблиці виписують псевдо план і значення ф-ції на ньому.
5.Знову перевіряємо план на оптимальність.
Алгоритм методу потенціалів.
1.Серед наявних опорних планів транспортної задачі вибирають той, значення ф-ції мети на якому менша ніж значення ф-ції на інших планах.
2.Вибирають потенціали, які позначають вартість одиниці продукції в і-того постачальника Ui та й-того споживача Vj.
3.Записують сис рівнянь(Ui+Cij=Vij) для знаходження невідомих потенціалів, причому кожні рівність відповідає тільки заповненій клітинці даної таблиці.
4.Знаходять значення невідомих потенціалів із записаної сис рівнянь.
Для знаходження невідомих потенціалів значення потенціалу, яке найбільше зустрічається в сис прирівнюють до О, а потім знаходять значення решти потенціалів.
5.Перевіряють умову оптимальності плану: для всіх незаповнених клітинок таблиці повинна виконуватися рівність ?Ij=(Ui-Cij)-Vj>=0.
Якщо серед отриманих різниць ?Ij є від’ємні, то вибраний план не є оптимальний, тому переходимо до наступного кроку.
6.Будують цикл перерозподілу продукції між постачальниками та виробниками:
а)серед отриманих від’ємних різниць знаходять найменшу і клітинку до якої вона досягається відзначається символом „+”.
б)враховуючи відмічену клітинку таблиці будують цикл перерозподілу продукції. Вершини циклу почергово відмічають знаками „+” та „-”.
7.Вибирають к-сть продукції для перерозподілу – вибирають найменше число, здійснюють перерозподіл продукції між споживачами та постачальниками. До числа із клітинками зі знаками „+” до чисел з
„-”, віднімають к-сть продукції для перерозподілу.
8.Виписують новий опорний план задачі і знаходять значення заданої ф-ції на ньому.
9.Повертаємося до пункту 3.
Постановка задачі лінійного програмування.
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