Лекция 12. МЕТОДЫ РЕШЕНИЯ ЗАДАЧ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ

Графический метод решения ЗЛП

Наиболее простым и наглядным методом решения ЗЛП является графический метод. Он применим для решения ЗЛП с двумя переменными. На плоскости х20Х] строится многоугольник решений ABCDEF:

Среди точек этого многоугольника надо найти такую, в которой линейная функция F = с2х2 принимает максимум (минимум).

Рассмотрим линию уровня линейной функции F, те. линию, вдоль которой функция F принимает фиксированное значение С:

cixi + C2x2 = C. (i)

Примерами линий уровня являются линии постоянной температуры (изотермы) на картах прогноза погоды, параллели (линии уровня широты) и меридианы (линии уровня долготы) на географической карте.

Пусть надо найти самую северную точку страны. Это будет точка, имеющая наибольшую широту, т.е. точка, через которую проходит параллель с самой большой широтой. Именно так надо поступать при геометрическом решении ЗЛП. На многоугольнике решений ищется точка, через которую проходит линия уровня с наибольшим значением, если ищется максимум целевой функции.

Линии уровня (1) представляют собой параллельные прямые при различных значениях С, так как их угловой коэффициент определяется только соотношением между с, и с2. Другими словами, линии уровня - это своеобразные параллели, расположенные под углом к осям координат.

При смещении линии уровня в одну сторону уровень только возрастает, а при смещении в другую - только убывает. Направление наибольшего возрастания функции показывает вектор-градиент, координаты которого равны частным производным функции:

dF dF

VF = (—) = (С12).(2) ос{ дс2

Градиент ориентирован перпендикулярно линиям уровня.

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

Таким образом, графический метод решения ЗЛП сводится к следующим этапам:

  • 1. На координатной плоскости х20Х] строится многоугольник решений.
  • 2. Находится градиент целевой функции VF = (с,;с2).
  • 3. Линия уровня CjXj + с2х2 = С, перпендикулярная градиенту, передвигается в его направлении до тех пор, пока не покинет пределы многоугольника решений. Предельная точка этого движения и является точкой максимума целевой функции.

4. Для нахождения координат точки максимума решается система двух уравнений, описывающих пересекающиеся в этой точке прямые.

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

При графическом решении ЗЛП возможны случаи, когда область допустимых решений системы ограничений представляет пустое множество (условия задачи противоречивы) или не ограничена. В этих случаях оптимального решения не существует.

Пример 1. Мебельный цех выпускает изделия двух типов: ?! и Т2. На каждое изделие типа Tj расходуется 1 единица ресурса Рр 1 единица ресурса Р2 и единица ресурса Р3. На каждое изделие типа Т, расходуется 1 единица ресурса Pj и 4 единицы ресурса Р2. Ресурсы мебельного цеха ограничены: в день можно расходовать не более 8 единиц ресурса Рр 20 единиц ресурса Р, и 5 единиц ресурса Р3. Какое количество изделий типа Т и Т должен выпускать цех ежедневно, чтобы обеспечить максимальную прибыль, если прибыль от реализации изделия Tj — 1 денежная единица, а от реализации Т - 2 денежные единицы.

РЕШЕНИЕ

Введем обозначения: х, - число изделий типа Тр х2 - число изделий типа Т2. Прибыль от реализации изделий Tj составляет хр а от реализации изделий типа Т - 2х, т.е. необходимо максимизировать целевую функцию

F = Xj + 2х2 —> max.

Ограничения задачи имеют вид

Х + х2 < 8,

х{ + 2 < 20,

< х{ <5, х{ >0, х2 > 0.

Первому ограничению соответствует прямая, проходящая через точки (0; 8) и (8; 0) (рис. 2).

Второму ограничению соответствует прямая, проходящая через точки (0; 5) и (20; 0).

Решением неравенства х < 5 (ограничение по количеству изделий типа Т]) является полуплоскость, лежащая слева от прямой Xj =

5. Таким образом, область допустимых решений ЗЛП представляет собой пятиугольник.

Для определения направления движения к оптимуму построим вектор-градиент /F = (с{2) = (1; 2). При максимизации целевой функции следует двигаться в направлении вектора VF . В крайней угловой точке этого движения (точка А на рис. 2) достигается максимум целевой функции.

Для нахождения координат точки А достаточно решить систему уравнений соответствующих прямых

х{ + х2 = 8,

х{ + 2 = 20.

Отсюда легко получается решение ЗЛП: максимум целевой функции F = 12 достигается при х = 4 и х2 = 4.

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

Поэтому необходимы аналитические методы, позволяющие решать ЗЛП с любым числом переменных.

 
Посмотреть оригинал
< Пред   СОДЕРЖАНИЕ ОРИГИНАЛ   След >