Постановка задачи линейного программирования

Задача линейного программирования (ЛП) в общем виде записывается следующим образом (1.1 – 1.4). Каждой задаче ЛП может быть поставлена в соответствие другая вполне определенная задача ЛП, такая, что при решении одной из них одновременно решается и другая. Эти задачи названы парой взаимодвойственных задач. Любой задаче ЛП (1)–(4) можно поставить в соответствие двойственную задачу вида (1.5 – 1.8):

	(1.1)		(1.5)
(1.2)	(1.6)
(1.3)	(1.7)
(1.4)	(1.8)

где – неизвестные величины; – заданные действительные числа; (1.1) – целевая функция (ЦФ); (1.2), (1.3) – основные ограничения задачи; (1.4) – не основные ограничения; y_i имеет произвольный знак для .

Для решения задач ЛП может быть использован графический метод, симплекс-метод, метод искусственного базиса, модифицированный симплекс-метод и двойственный симплекс-метод.

Правила составления двойственных задач:

1) число неизвестных одной задачи равно числу ограничений второй;

2) матрицы коэффициентов системы ограничений получаются одна из другой путем транспонирования;

3) знаки неравенств в системе ограничений заменяют на противоположные, например ≤ на ≥ и, наоборот;

4) свободные члены ограничений исходной задачи становятся коэффициентами целевой функции двойственной задачи и, наоборот, коэффициенты целевой функции исходной задачи преобразуются в свободные члены ограничений двойственной;

5) критерий оптимальности целевой функции заменяется на противоположный, например, max на min.