) лінійної функції при лінійних обмеженнях.
Загальна форма задачі має вигляд: знайти за умов
В
Де
В
Тут і далі нам зручніше вважати с і а и вектор - рядками, а x і b = (b 1 , ..., b m ) T - вектор стовпцями.
Поряд із загальною формою широко використовуються також канонічна і стандартна форми. Як в канонічній, так і в стандартній формі
В
тобто всі змінні в будь-якому допустимому вирішенні завдання повинні приймати невід'ємні значення (Такі змінні прийнято називати невід'ємні на відміну від так званих вільних змінних, на область значень яких подібне обмеження не накладається). Відмінність же між цими формами полягає в тому, що в одному випадку I 2 = 0, а в іншому - I 1 = 0. p> Задача ЛП в канонічній формі:
(2.1)
(2.2)
(2.3)
Задача ЛП у стандартній формі:
В
В обох випадках А є матриця розмірності mxn, i-й рядок якої збігається з вектором а i .
Задача ЛП в загальній формі зводиться (у певному сенсі) до задачі ЛП в канонічній (стандартною) формі. Під цим розуміється існування загального способу побудови по вихідної завданню (У загальній формі) нової задачі ЛП (в потрібній нам формі), будь-яке оптимальне рішення якою "легко" перетворюється на оптимальне рішення вихідної задачі і навпаки. (Фактично, зв'язок між цими завданнями виявляється ще більш тісної). Тим самим ми отримуємо можливість, не втрачаючи спільності, займатися вивченням завдань ЛП, представлених або в канонічній, або в стандартній формі. Зважаючи на це наші подальші розгляду завдань ЛЗ будуть присвячені, головним чином, завданням в канонічній формі.
В
2. Приведення задачі лінійного програмування до стандартної форми
Будь-яка задача лінійного програмування приводиться до стандартної (канонічної) формі основної задачі лінійного програмування, яка формулюється так: знайти невід'ємні значення змінних X1, X2, Xn, які відповідають обмеженням у вигляді рівності:
A11X1 + A12X2 + ... + A1nXn = B1;
A21X1 + A22X2 + ... + A2nXn = B2;
..........................................
Am1X1 + Am2X2 + ... + AmnXn = Bm;
Xj ≥ 0, j = 1, ..., n
і звертають в максимум лінійну функцію цих змінних:
E = C1X1 + C2X2 + ... + CnXn Гћ max
При цьому також потрібно, щоб праві частини рівностей були невід'ємні, тобто повинні дотримуватися умови:
Bj ≥ 0, j = 1, ..., n
Приведення до стандартної форми необхідно, так як більшість методів вирішення завдань лінійного програмування розроблено саме для стандартної форми. Для приведення до стандартної формі завдання лінійного програмування може знадобитися виконати такі дії:
перейти від мінімізації цільо...
