Методы оптимальных р ...

2.3 Формы записи задачи линейного программирования

Из рассмотренных выше примеров мы видим, что тип неравенств, используемых в задачах может быть самым разным (=, , ≤).

В зависимости от используемых типов ограничений существует 3 формы записи задачи линейного программирования:

• Стандартная (в системе ограничений задачи присутствуют только неравенства);

• Каноническая (в системе ограничений задачи присутствуют только равенства);

• Общая (в системе ограничений задачи присутствуют как равенства, так и неравенства).

Все формы записи эквивалентны, всегда можно от одной формы записи перейти к другой.

Запишем математически формы записи:

1. Стандартная форма записи

2. Каноническая форма записи

3. Общая форма

В задачах линейного программирования различают 2 вида решений:

• Допустимое решение (опорный план);

• Оптимальное решение (оптимальный план).

Вектор Х=(х₁, х₂,…х_n), удовлетворяющий системе ограничений задачи называется допустимым решение (опорным планом).

Опорных планов может быть бесчисленное множество. Среди множества опорных планов необходимо найти оптимальный.

Оптимальным решением (или оптимальным планом) задачи линейного программирования называется решение Х==(х₁^*, х₂^*,…х_n^*) системы ограничений, при котором критерий оптимизации принимает экстремальное (максимальное или минимальное) значение.

Оптимальный план один, в исключительных случаях их может быть несколько, это встречается тогда, когда количество переменных невелико.

Термины «решение» и «план» - синонимы. «Решение» используется чаще, когда речь идет о формальной стороне задачи (математическом решении), а «план» – о содержательной стороне (экономической интерпретации).