Графічний метод лінійного програмування.
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.