3. Лекция. Линейное программирование

Виды математических моделей ЛП
Математическая модель задачи ЛП может быть каноничес­кой и неканонической.


Определение . Если все ограничения системы заданы урав­нениями и переменные Xj неотрицательные, то такая модель задачи называется канонической.
Если хотя бы одно ограничение является неравенством, то модель задачи ЛП является неканонической. Чтобы перейти от неканонической модели к канонической, необходимо в каждое
неравенство ввести балансовую переменную х_n+i .
Если знак неравенства < , то балансовая переменная вводится со знаком плюс, если знак неравенства >, то — минус. В целевую функ­цию балансовые переменные не вводятся.
Чтобы составить математическую модель задачи ЛП, не­обходимо:
— ввести обозначения переменных;
— исходя из цели экономических исследований, составить целевую функцию;
— учитывая ограничения в использовании экономических показателей задачи и их количественные закономернос­ти, записать систему ограничений.
3. 2 Двойственность в задачах линейного программирования
Каждая задача линейного программирования, называемая прямой или исходной, тесно связана с другой задачей, ее называют двойственной.
Математические модели этих задач имеют следующий вид.

прямая задача:

двойственная задача:

Эти задачи экономически могут быть сформулированы следующим образом.

Прямая задача: сколько и какой продукции х_i(i-1, 2, … , n) надо произвести, чтобы при заданных стоимостях единицы продукции С_i, объемом имеющихся ресурсов b_j (j=1,2,…, m) и нормах расхода ресурсов а_ij максимизировать выпуск продукции в стоимостном виде.