Вопрос № 9. Этапы решения ЗЛП графическим методом (алгоритм решения)

Если задача линейного программирования содержит только две переменные, то ее можно решить графическим методом, выполняя следующие операции:

1. Строим все полуплоскости, соответствующие ограничениям системы.

2. Находим область допустимых решений (ОДР), как множество точек, в котором пересекаются все построенные полуплоскости.

3. Строим вектор , выходящий из начала координат, где и – это коэффициенты при неизвестных в целевой функции . Этот вектор указывает направление возрастания целевой функции.

4. Перпендикулярно вектору проводим так называемую линию уровня (т.е. прямую , проходящую через начало координат).

5. Перемещаем линию уровня параллельно самой себе в направлении вектора (если задача на максимум (max)) или в противоположном направлении (если задача на минимум (min)) до тех пор, пока линия уровня имеет хотя бы одну общую точку с ОДР.

6. Находим координаты этой общей крайней точки, решая систему уравнений прямых, на пересечении которых она находится.

7. Подставляем эти координаты в целевую функцию и находим ее max (или min).

Вопрос № 10. Алгоритм симплексного метода решения ЗЛП:

1. Привести задачу к каноническому виду

2. Найти начальное опорное решение с "единичным базисом" (если опорное решение отсутствует, то задача не имеет решение ввиду несовместимости системы ограничений)

3. Вычислить оценки разложений векторов по базису опорного решения и заполнить таблицу симплексного метода

4. Если выполняется признак единственности оптимального решения, то решение задачи заканчивается

5. Если выполняется условие существования множества оптимальных решений, то путем простого перебора находят все оптимальные решения