Загальна задача лінійного програмування (злп).

Зада́ча ліні́йного програмува́ння — задача оптимізації з лінійною цільовою функцією та допустимою множиною обмеженою лінійними рівностями або нерівностями.

Тобто, необхідно мінімізувати

(1), при обмеженнях , (2)

, (3) , (4)

де c_j (j = 1, …, n), a_ij(i = 1, …, m) — задані числа.

Задача максимізації функції (1) зводиться до задачі мінімізації шляхом заміни знаків всіх коефіцієнтів c_j на протилежні.

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

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