одночасно і вимогам мінімізації (максималізації) (2.6) цільової функції, -
оптимальними .
Вище описана задача лінійного програмування (ЗЛП) представлена ​​в загальній формі, але одна і та ж (ЗЛП) може бути сформульована в різних еквівалентних формах. Найбільш важливими формами завдання лінійного програмування є канонічна і стандартна .
У канонічної формі задача є задачею на максимум (мінімум) деякої лінійної функції F , її система обмежень складається тільки з рівностей (Рівнянь). При цьому змінні завдання х 1 , х 2 , ..., х n є невід'ємними:
(2.7)
(2.8)
(2.9)
До канонічної формі можна перетворити будь-яку задачу лінійного програмування. p> Правило приведення ЗЛП до канонічного виду:
1.Якщо у вихідній задачі деяке обмеження (наприклад, перше) було нерівністю, то воно перетвориться в рівність, введенням в ліву частину деякої неотрицательной змінної, при чому в нерівності «≤» вводиться додаткова не негативними мінлива зі знаком В«+В»; в випадки нерівності «≥» - зі знаком В«-В»
(2.10)
Вводимо змінну.
Тоді нерівність (2.10) запишеться у вигляді:
(2.11)
У кожне з нерівностей вводиться своя " урівнює " змінна, після чого система обмежень стає системою рівнянь.
2. Якщо в вихідній задачі деяка змінна не підпорядкована умові незаперечності, то її замінюють (в цільовій функції і у всіх обмеженнях) різницею невід'ємних змінних
, l - вільний індекс
Транспортна задача в матричної постановці та її властивості
Дане завдання зводиться до визначення такого плану перевезень деякого продукту з пунктів його виробництва в пункти споживання (| | x i , j | | mxn ), який мінімізує цільову функцію
на безлічі допустимих планів
при дотриманні умови балансу
В
Якщо привести умови транспортної задачі до канонічної формі завдання лінійного програмування, то матриця задачі матиме розмірність ( m + n ) mn . Матриці систем рівнянь в обмеженнях мають ранги, рівні відповідно m і n . Однак, якщо, з одного боку, підсумувати рівняння за m, а з іншого - рівняння за n, то отримаємо одне і те ж значення. З цього випливає, що одне з рівнянь в системі є лінійною комбінацією інших. Таким чином, ранг матриці транспортної задачі дорівнює m + n -1 , і її невироджений базисний план повинен містити m + n -1 ненульових компонент.
Процес вирішення транспортної задачі зручно оформляти у вигляді послідовності таблиць. Рядки транспортної таблиці відповідають пунктам виробництва (в останній клітці кожного рядка зазначено обсяг ...
