Теорія двоїстості. Двоїста задачі лінійного програмування.

          Правила побудови двоїстої задачi:

·                    максимiзацiя (мiнiмiзацiя) цiльової функцiї прямої задачi замiнюється на мiнiмiзацiю(максимiзацiю) цiльової функцiї двоїстої задачi;

·                    якщо цiльова функцiя задачi максимiзується (мiнiмiзується), то всi обмеження-нерiвностi повиннi вiдповiдно мати знак"?" ("?"); коефiцiєнти цiльвої функцiї прямої задачi є вiльними членами обмежень двоїстої задачi, а правi частини обмежень прямої задачi - коефiцiєнтами цiльової функцiї двоїстої задачі;

·                    матриця коефiцiєнтiв обмежень двоїстої задачi є транспонованою по вiдношенню до матрицi коефiцiєнтiв обмежень прямої задачi;

·                    кількість змiнних однiєї задачi дорiвнює кількості обмежень другої; кожному обмеженню-нерiвностi прямої задачi вiдповiдає невiд'ємна змiнна двоїстої задачi i навпаки.  

Двоїстий симплекс-метод, так як і симплекс-метод,

використовується при знаходженні розв’язку задачі лінійного

програмування, записаної у формі основної задачі, для якої серед

векторів Рі, складених з коефіцієнтів при невідомих в системі рівнянь,

маючи m одиничних. Разом з тим двоїстий симплекс-метод можна

застосовувати при розв’язанні задачі лінійного програмування, вільні

члени системи рівнянь котрими можуть бути любі числа (при розв’язку

задачі симплексним методом ці числа припускаються невід’ємними). Таку

задачу і розглянемо тепер, попередньо припустивши, що одиничними

являються вектори P1, P2, ... , Pm.

7. Содержание

   • Теоретичні питання
   • Загальна задача лінійного програмування (злп).
   • Постановка задачі. Побудова математичної моделі. Форми представлення злп.
   • Графічний метод розв’язання задачі лінійного програмування.
   • Симплекс-метод розв’язання задачі лінійного програмування.
   • Алгоритм симплекс-метода.
   • Теорія двоїстості. Двоїста задачі лінійного програмування.
   • Співвідношення між прямою та двоїстою злп.
   • Транспортні моделі. Визначення транспортної моделі. Методи розв’язання транспортної задачі.
   • Визначення початкового рішення транспортної задачі.
   • Метод північно-західного кута.
   • Метод мінімального елементу.
   • Транспортні моделі. Визначення оптимального рішення.
   • Сітьові моделі.
   • Цілочислове програмування.