При условиях-ограничениях

Приложение 4

Методические указания к решению второй контрольной работы

1. Графический метод решения задач линейного программирования

Общей задачей линейного программирования ОЗЛП называется задача, которая состоит в определении максимального (минимального) значения линейной целевой функции:

При условиях-ограничениях

где -заданные постоянные величины и .

Стандартной (или симметричной) задачей линейного программирования называется задача, которая состоит в определении максимального (минимального) значения целевой функции при выполнении условий 1 и 3, где и .

Канонической (или основной) задачей линейного программирования называется задача, которая состоит в определении максимального (минимального) значения целевой функции при выполнении условий 2 и 4, где и .

Совокупность чисел = удовлетворяющих ограничениям задачи, называется допустимым решением (или планом).

План = , при котором целевая функция задачи принимает максимальное (минимальное) значение, называется оптимальным.

В случае, когда требуется найти минимум функции можно перейти к нахождению максимума функции , так как min .

Ограничение-неравенство исходной задачи линейного программирования, имеющее вид " ", преобразуется в ограничение-равенство добавлением к левой части дополнительных неотрица­тельной переменной, а ограничение неравенство вида " " - в огра­ничение-равенство вычитанием из левой части дополнительной неотрицательной переменной.

Допустим ограничения задачи отображают наличие производственных ресурсов, тогда числовое значение дополнительной переменной в плане задачи, записанной в форме основной, равно объе­му неиспользуемого соответствующего ресурса.

План называется опорным планом основной задачи линейного программирования, если система векторов, входящих в разложение с положительными коэффициентами линейно независима.

Так как векторы являются m-мерными, то из определения опорного плана следует, что число его положительных компонент не может превышать m.

Опорный план называется невырожденным, если он содержит ровно m положительных компонент, в противном случае - план вырожденный.