містить М рядків і N стовпців. До неї заносяться коефіцієнти системи обмежень і цільової функції з відповідними знаками. Змінні, розташовані у верхньому рядку симплекс-таблиці, є вільними, тобто незалежними змінними, а змінні в крайньому лівому стовпчику таблиці називаються базисними. Так як у нас є два рівності, то введемо дві додаткові змінні.
Таблиця 6. Вихідна симплекс-таблиця:
-x1-x2-x3-x4-x5-x6BY111001045Y200110122Y310000030Y401000060Y500100025Y600010035Y710010075Y8001100100Fmax- 0,05-0,04-0,09-0,02000
Таблиця 7. Кінцева симплекс-таблиця:
-Y1-X2-Y2-X4-X5-X6BХ11-1001045Х3001-10122Y3-1100-105Y401000015Y500-110-125Y600010030Y70-1-110-140Y80-1000-170Fmax0,050,010,0900,040,024.25
Маємо оптимальні шляхи вирішення задачі:
По дорозі Х1 (2 - 4 - 3)=45,
По дорозі Х3 (6 - 4 - 5)=22
Значення цільової функції F max=4.25 - максимальна цінність передачі інформації
. Двоїста задача
Для будь-якої задачі лінійного програмування може бути поставлена ??у відповідність деяка інша задача, яка називається двоїстої по відношенню до прямої.
У двоїстої завданню необхідно знайти значення змінних Y i * (i=1, M - 1), що задовольняють системі, де Y i *? 0 (i=L + 1, M - 1), Y i * (i=1, L) не обмежені в знаку, і забезпечують мінімальне значення цільової функції, при цьому Fmax=-Фmin. Таким чином, для даної задачі двоїста їй буде мати вигляд.
Цільова функція:
Ф min=45Y1 * + 22Y2 * + 30Y3 * + 60Y4 * + 25Y5 * + 35Y6 * + 75Y7 * + 100Y8 *? min
Обмеження:
Y1 * + Y3 * + Y7 *? 0,05; * + Y4 *? 0,04;
Y2 * + Y5 * + Y8 *? 0,09;
Y2 * + Y6 * + Y7 * + Y8 *? 0,02;
Y1? 0;
Y2? 0;
Yi *? 0, де i=1,8
Якщо вихідну симплекс-таблицю прямої задачі представити у матричному вигляді:
А - матриця коефіцієнтів обмежень.
Вихідну симплекс-таблицю двоїстої задачі можна записати у вигляді:
Звідси випливає, що рішення двоїстої задачі визначається з кінцевої симплекс-таблиці прямої задачі і навпаки. Якщо формально в якості додаткових змінних для обмежень задачі використовувати змінні, а в якості додаткових змінних для обмежень двоїстої задачі - змінні Хj *, то при вирішенні двоїстої задачі симплекс-таблицю на будь ітерації симплекс-методу можна розглядати як транспоновану симплекс-таблицю прямої задачі. При цьому коефіцієнти рядка цільової функції і стовпця вільних членів транспонуючих без зміни, а всі інші коефіцієнти таблиці одночасно з Транспонированием змінюють знаки на протилежні.
Таблиця 8. Вихідна симплекс-таблиця двоїстої задачі:
- Y1 * -Y2 * -Y3 * -Y4 * -Y5 * -Y6 * -Y7 * -Y8 * BX1 * - 10-1000-10-0,05X2 * - 100-100-10-0,04X3 * 0-100-100-1-0,09X4 * 0-1000-10-1-0,02X5 * - 100000000X6 * 0-10000000Фmin452230602535751000
Таблиця 9. Кінцева симплекс-таблиця двоїстої задачі:
- X1 * -X3 * -Y3 * -Y4 * -Y5 * -Y6 * -Y7 * -Y8 * BX2 * - 101-100000,01Y1 * - 101000100,05X4 * 0-1001-1000Y2 * 0-10010010,09X5 * - 101000100,04X6 * 0-10000000,02Фmin452251525304070-4.25
Рішення двоїстої задачі: *=0,05; Y2 *=0,09; Y3 *=0; Y4 *=0; Y5 *=0; Y6 *=0; Y7 *=0; Y8 *=0;
Значення цільової функції для двоїстої задачі: Фmin=- 4,25.
. Економічна інтерпретація подвійності
Отримані значення змінних двоїстої задачі: Y1 *=0,05 і Y2 *=0,09 показують, наскільки зміниться цільова функція прямої задачі при зміні на одиницю корисності відповідно першого і другого гілок. Значення Y3 *=0; Y4 *=0; Y5 *=0; Y6 *=0; Y7 *=0 і Y8 *=0 свідчать про те, що зміна даного виду ресурсу (пропускних спроможностей відповідних шляхів) не призводить до зміни цільової функції. Це свідчить про те, що даний ресурс використаний не повністю для отримання оптимального рішення, тобто має місце прихований запас цього виду ресурсу. Величина прихованого запасу визначається значенням додаткових змінних Y3=5; Y4=15; Y5=25; Y6=30; Y7=40; Y8=70 в оптимальному рішенні прямої задачі. Таким чином, позитивну, відмінну від нуля подвійну оцінку мають ті ресурси, які повністю використовуються при оптимальному плані передачі інформації, тому двоїсті оцінки визначають дефіцитність використовуваних ресурсів (корисність шляхів). Ліві частини обмежень двоїстої задачі визначають вартість кожного шляху....
