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

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

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

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

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

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

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

Изменяя степень достижения цели 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₁ - число ездок на маршруте В₁;

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

Решение может быть найдено графически, как показано на рис. 8.5. При X1 = 0, Х2 = 4,4. При Х2 = 0, X1 = 6,5. Соединив полученные точки А и В, получим область допустимых решений X, и Х2. Левые части уравнений целевой функции (8.22) и ограничения (8.23) совпадают. Это значит, что все точки, лежащие на линии 1,23Х1+1,8Х2=8.

будут оптимальными. Точки 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) и каждому возможному способу размещения тары на под­доне поставим точку, координаты которой соответствуют числу соответ­ствующей тары, размещаемой на поддоне. Буквой С с индексом обозначим номер способа размещения тары на поддоне. Множество всевозможных планов размещения тары на поддоне изображается совокупностью точек выпуклого многоугольника С₁ С₂ С₄ С₃. Например, точки на отрезке С₁ С₂ будут указывать

своими координа­тами количество тары типа А и ти­па В, приходящейся на один под­дон в различных способах разме­щения их, сочетающих собой размещения по способу С1 и С2 (рис. 8.6). Из всех решений нас ин­тересует выполнение условия ком­плектности, т. е. отношение числа тары А к числу тары В. В соот­ветствии с заданием это соотно­шение равно 2 (600:300). Если из начала системы координат про­вести луч, координаты которого А= 2, В = 1, то оптимальным бу­дет план размещения тары на под­доне, которому соответствует точка, одновременно принадлежащая многоугольнику и лучу, и имеющая наи­большие координаты, т. е. соответствующая плану наибольшего исполь­зования площади поддонов. Такой точкой будет Р, лежащая на отрезке С1 С3. Это указывает на то, что оптимальный план размещения тары на поддонах представляет собой комбинацию размещения тары по способу C1 и С3.

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

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

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

Дата добавления: 2015-08-09