о основних елементів:
1. спосіб визначення якого-небудь первісного допустимого базисного рішення задачі;
2. правило переходу на краще (точніше, не гіршого) рішенню;
. критерій перевірки оптимальності знайденого рішення.
Симплексний метод включає в себе ряд етапів і може бути сформульований у вигляді чіткого алгоритму (чіткого припису про виконання послідовних операцій). Це дозволяє успішно програмувати і реалізовувати його на ЕОМ. Завдання з невеликим числом змінних і обмежень можуть бути вирішені симплексним методом вручну.
1.3. Двоїста задача лінійного програмування
З кожною задачею лінійного програмування можна деяким чином зіставити іншу задачу ЛП, звану двоїстої по відношенню до вихідної (прямий).
Під двоїстої завданням розуміється допоміжна завдання лінійного програмування, формулируемая за допомогою певних правил безпосередньо з умов прямої задачі. Зацікавленість у визначенні оптимального розв'язання прямої задачі шляхом вирішення двоїстої до неї завдання обумовлена ??тим, що обчислення при вирішенні ДЗ можуть виявитися менш складними. Трудомісткість обчислень при вирішенні ЗЛП більшою мірою залежить від числа обмежень, а не від кількості змінних.
Дамо визначення двоїстої задачі по відношенню до прямої задачі лінійного програмування, що складається, в знаходженні максимального значення функції
функції
f=c 1 x 1 + c 2 x 2 + ... + cnxn? max (1.4)
за умов:
a 11 x 1 + a 12 x 2 + ... + a 1n xn? b 121 x 1 + a 22 x 2 + ... + a 2n x n? b 2
... (1.5) m1 x 1 + a m2 x 2 + ... + a mn xn? b mj? 0 (j=1, 2, ... m, m? N).
Завдання, що складається в знаходженні мінімального значення функції
f *=b 1 y 1 + b 2 y 2 + ... + bmym? min (1.6)
за умов:
a 11 y 1 + a 12 y 2 + ... + a m1 ym? c 112 y 1 + a 22 y 2 + ... + a m2 y m? c 2
... (1.7) 1n y 1 + a 2n y 2 + ... + a mn ym? c mi? 0 (i=1, 2, ... k? M)
називається двоїстої по відношенню до задачі (1.4) - (1.5). Завдання (1.4) - (1.5) і (1.6) - (1.7) утворюють пару завдань, звану в лінійному програмуванні двоїстої парою. Порівнюючи дві сформульовані завдання, бачимо, що двоїста задача складається згідно з такими правилами:
Цільова функція вихідної задачі задається на максимум, а цільова функція двоїстої - на мінімум.
1. Матриця
(1.8)
2. складена з коефіцієнтів при невідомих у системі обмежень (1.5) вихідної задачі, і аналогічна матриця
(1.9)
в двоїстої задачі виходять один з одного Транспонированием (тобто заміною рядків стовпцями, а стовпців - рядками).
3. Число змінних в двоїстої задачі дорівнює числу обмежень в системі (1.5) вихідної задачі, а число обмежень в системі (1.7) двоїстої завдання - числу змінних у вихідній задачі.
4. Коефіцієнтами при невідомих у цільовій функції (1.6) двоїстої задачі є вільні члени в системі (1.5) вихідної задачі, а ...
