мування двоїста, тобто, якщо пряма задача має рішення, (вектор x = (x 1 , x 2 , ..., x k )), то існує і має рішення зворотна завдання заснована на транспонировании матриці прямої задачі. Рішенням зворотної задачі є вектор y = (y 1 , y 2 ..., y m ) компоненти якого можна розглядати як об'єктивно обумовлені оцінки ресурсів, тобто оцінки, що показують цінність ресурсу і наскільки повно він використовується. [Контровіч]
На основі об'єктивно обумовлених оцінок американським математиком Дж. Данцигом - був розроблений симплекс-метод вирішення завдань оптимального програмування. Цей метод досить широко застосовується. Алгоритм його дуже детально опрацьований, і навіть складені прикладні пакети програм, які застосовуються в багатьох галузях планування.
Його ідея полягає в наступному: спочатку досягається опорне рішення поставленої задачі, тобто допустимий варіант, задовольняє всім обмеженням. Потім, проробляючи ряд послідовних кроків, що зводяться до виконання елементарних алгебраїчних перетворень, отримують нове рішення. Воно краще або, принаймні, не гірше попереднього. Після кінцевого числа кроків (ітерацій) або встановлюють нерозв'язність завдання, або опорний план є оптимальним.
Необхідно відзначити, що симплекс метод працює тільки для системи лінійних рівнянь в канонічному вигляді, в якої повинна бути попередньо записана вихідна задача.
Рішення завдання включає пошук опорного і знаходження оптимального рішення. Ознаки опорного рішення - це наявність позитивних вільних членів. У разі його відсутності чинимо наступним чином:
1 - вибираємо будь негативний вільний член;
2 - знаходимо будь негативний коефіцієнт у рядку негативного вільного члена;
3 - проводячи розподіл коефіцієнтів шпальти вільних членів на відповідні коефіцієнти стовпця з обраним негативним елементом, знаходимо найменше позитивне значення, яке вкаже на дозволяючий коефіцієнт.
Після вибору дозволяє елемента симплексному перетворення виконується за такими правилами:
1. Новий коефіцієнт замість разрешающегося дорівнює 1, поділеній на дозволяючий коефіцієнт. При цьому новими називатимуться коефіцієнти наступної симплексної таблиці по відношенню до попередньої;
2. Нові коефіцієнти рядка разрешающегося елемента дорівнюють попереднім, діленим на дозволяючий;
3. Нові коефіцієнти стовпця разрешающегося елемента дорівнюють попереднім, діленим на дозволяє елемент, взятий з протилежним знаком;
4. Нові коефіцієнти, не варті в рядку або стовпці разрешающегося елемента, рівні приватному від ділення різниці добутку коефіцієнтів головної та побічної діагоналей на дозволяючий елемент.
Всі результати розрахунків елементів заносяться в симплекс-таблицю. [Колеснев]
Незважаючи на широту застосування методу лінійного програмування, він враховує лише три особливості економічних за...
