8.2. Графоаналитический метод

Чтобы понять основные свойства линейных моделей и из чего скла­дывается процесс получения решения задач линейного программирова­ния, рассмотрим геометрическую интерпретацию линейного программи­рования, получившего название графоаналитического метода. Необходи­мо учитывать, что графоаналитический метод может быть использован только в том случае, если задача содержит два, максимум три неизвестных. В последнем случае приходится пользоваться про­странственной моделью. Несмотря на простоту решения задач этим ме­тодом, его применение при разработке технологических процессов весь­ма ограничено.

Сущность графоаналитического метода рассмотрим на решении сле­дующей задачи:

максимизировать функцию 10Х₁+13Х₂ (8.11)

при наличии ограничений

Решение задачи может быть найдено графически, как показано на рис. 8.2. Ограничения (8.12) и (8.13) на рис. 8.2 изображены прямыми ли­ниями как уравнения, полученные заменой неравенств на равенства. Площадь под каждой из двух прямых эквивалентна математической формулировке, имеющей направленный смысл «меньше, чем» (<). Так как X₁ и X₂ не могут принимать отрицательных значений, область до­пустимых значений переменных ограничивается осями координат. Таким образом, многоугольник ОABC содержит в себе область значений Х_х и Х₂, удовлетворяющих всем имеющимся ограничениям. Множество то­чек, принадлежащих области, ограниченной линиями ОАВС (вместе с граничными точками), называется множеством решений. Это множест­во является выпуклым, т. е. любой отрезок, соединяющий две произвольным образом выбранные точки данного множества, лежит внутри или проходит вдоль границы ОABC.

Изменяя степень достижения цели Z₀, получаем на рис. 8.2 семейст­во параллельных изолированных прямых, уравнение которых

Из уравнения (8.16) следует, что чем выше степень достижения цели, тем выше располагается соответствующая изоцелевая прямая. Оптималь­ное решение определяется экстремальной точкой В, для которой

Если в формуле для целевой функции (8.11) изменить коэффициенты при переменных (при этом угол наклона параллельных линий по отноше­нию к оси абсцисс также будет другим), то в результате точка, задающая оптимальное решение, может перемещаться. Если при наличии ограни­чений (8.12), (8.13), (8.14) целевая функция будет иметь вид

то в этом случае все точки, лежащие на отрезке АВ, будут являться опти­мальными (рис. 8.3). Решение X₁ = 0,95, Х₂=1,8 будет оптимальным. Однако оптимальным будет и решение X₁ = 0, Х₂ = 2 . Оптимальное значение целевой функции будет равно 28,0.

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

при наличии ограничений:

то приходится пользоваться пространственной моделью.

Когда ограничения являются уравнениями, то каждое из них можно считать уравнением плоскости, лежащей в трехмерном пространстве, и точка, общая этим трем плоскостям, есть единственная точка, представ­ляющая собой допустимое решение (рис. 8.4, а). Если ограничения яв­ляются неравенствами, то область оптимальных решений образуют точки некоторого выпуклого многогранника, расположенного в первом октанте. Придавая переменной Z₀, формула (8.18), различные значения, по­лучим семейство параллельных изоцелевых плоскостей (см. рис. 8.4, а), при­чем большим значениям Z₀ будут соответствовать плоскости, располо­женные дальше от начала координат. Решение задачи дается координа­тами одной из вершин выпуклого многогранника допустимых решений.

Если вместо трех уравнений ограничений имеется лишь два, до­пустим, уравнения (8.19) и (8.20), то в этом случае областью допусти­мых решений окажется линия пересечения плоскостей, являющихся изо­бражениями уравнений ограничений (рис. 8.4, б). При одном уравнении ог­раничений областью допустимых решений будет являться треугольник, образованный линиями пересечения плоскости, изображающей это урав­нение, с плоскостями координат (рис. 8.4, в).

В случае, когда необходимо получить не максимум, а минимум функции, то многоугольник будет вогнутым.

Особенности решения задач графоаналитическим методом рас­смотрим на следующих примерах

Задача 8.3. От поставщика А груз перевозится автомобилями КаMA3-5320 двум потребителям B₁ и В₂ на расстояние 15 и 25 км соот­ветственно. При перевозке груза потребителю B₁ на одну ездку затрачи­вается 1,23 ч, а потребителю В₂ - 1,8 ч. Продолжительность работы ав­томобилей на линии -8 ч. Работая на маршруте В₁, водитель делает 6 ездок, затрачивая на это 7,38 ч рабочего времени. На маршруте В₂ во­дитель делает 4 ездки и затрачивает 7,2 ч рабочего времени. Требуется организовать работу так, чтобы максимально использовать рабочее время водителей.

Математическая модель запишется в следующем виде:

максимизировать

при наличии ограничения

где: X₁ - число ездок на маршруте В₁;

Х₂ - число ездок на маршруте В₂.

будут оптимальными. Точки Q, С₂ и так далее, заключенные между прямой АВ и осями координат, имеющие координатами целые числа, изображают все возможные варианты работы автомобиля. Точки, которые ближе расположены к прямой или лежат на ней, дают наилучшие - оптимальные решения.

В рассматриваемом примере точки C₁ с координатами X₁=5 и Х₂ = 1 и С₄ с координатами X₁ = 2, Х₂ =3 ближе всех расположены к линии АВ. В первом случае продолжительность работы водителя на ли­нии составит

1,23-5 + 1,8*1 = 7,95 ч,

а во втором

1,23-2 + 1,8*3 = 7,86 ч.

Задача 8.4. Определить потребное число поддонов для перевозки грузов пакетами, упакованными в потребительскую тару двух размеров - А и В. Количество грузов в таре типа А составляет 600 единиц и типа В - 300 единиц. Количество тары, загружаемой на поддон различными спо­собами, приведено в табл. 8.1.

Таблица 8.1

Математическая модель задачи будет сформулирована следующим образом:

минимизировать Х_{ + Х₂ + Х₃ + Х₄ = Z₀, (8.24)

при наличии ограничений

где: X_i - число поддонов, загруженных по i-способу размещения тары.

Для решения задачи начертим прямоугольную систему координат АОВ (рис. 8.6) и каждому возможному способу размещения тары на под­доне поставим точку, координаты которой соответствуют числу соответ­ствующей тары, размещаемой на поддоне. Буквой С с индексом обозначим номер способа размещения тары на поддоне. Множество всевозможных планов размещения тары на поддоне изображается совокупностью точек выпуклого многоугольника С₁ С₂ С₄ С₃. Например, точки на отрезке С₁ С₂будут указывать

Обозначим через δ долю поддонов, загружаемых по способу C₁, а остальную часть (l-δ) - по способу С₃, долю одного и другого способа размещения поддонов найдем из условия комплектности

Минимальное число поддонов Z₀ определится из уравнения

откуда Z₀ =212. Таким образом, по способу C₁ будет загружено 194 поддона и по способу С₃ - 18.