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

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

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

Дана целевая функция (формула (4.1)):

L=с₁x₁+с₂x₂ — extr, (4.1)

при условиях (формулы (4.2, 4.3)):

a_i1x_i1+a_i2x_i2 £ b_i, i=1,m (4.2)

x_j³0, j=1,2 (4.3)

Здесь условия (4.3) означают, что допустимые планы принадлежат геометрическому квадрату, каждое из условий (4.2) определяет полуплоскость по одну сторону от прямой a_i1x_i1+a_i2x_i2£b_i, а пересечение полуплоскости (4.2) и неотрицательность квадрата (4.3) представляет собой выпуклый многоугольник — геометрическое место допустимых планов, рисунок 20.

Целевая функция (4.1) является прямой, перпендикулярной вектору С=(С₁; С₂). Придавая параметру L различные значения, получаем семейство параллельных прямых. Переход от одной прямой этого семейства к другой в направлении, определяемом вектором С, приводит к возрастанию значений целевой функции, а движение в противоположном направлении — к убыванию, следовательно, переместив опорную прямую L так, чтобы целевая функция приняла экстремальное значение, и хотя бы одна точка многоугольника условий принадлежала этой прямой, найдем экстремальное значение целевой функции.

Рис. 20.

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

1. Построить многоугольник решений системы ограничений.

2. Построить опорную прямую координаты, которой состоят из коэффициентов при неизвестных в целевой функции. Причем коэффициент Х₁ откладывается на оси Х₂, а коэффициент Х₂ на оси Х₁. Это исходит из того, что целевую функцию можно представить к виду уравнения в отрезках:

z=P₁x₁+P₂x₂,

пусть z=P₁P₂, тогда:

.

3. Для выбора направления максимума и минимума построить направляющий вектор, перпендикулярно к опорной прямой. Он строится двумя способами. Как отрезок соединим начало координат с точкой, имеющей координаты коэффициентов при неизвестных целевой функции.

4. Переместить опорную прямую параллельно самой себе до тех пор, пока она не «оторвется» от допустимых решений, если находится максимум, или пока она не соприкоснется с самой крайней вершиной многоугольника допустимых решений.

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

6. Затем полученные координаты подставить в целевую функцию, вместо х₁, х₂ и найти общее решение задачи.

Пример: Пусть задача линейного программирования задана в двухмерном пространстве, то есть ограничения содержат две переменные.

Организуется побочный цех на предприятии, чтобы использовать материалы, остающиеся от основного производства. Цех может освоить выпуск продукции двух видов: столы, книжные шкафы. Количество рабочих мест и ресурсы основных материалов ограничены. Задача состоит в том, чтобы запланировать цеху ежемесячный выпуск продукции, обеспечив при этом наибольшую возможную сумму прибыли. Исходные данные сведены в таблицу 8.

Таблица 8

Обозначим: х₁ — количество столов

х₂ — количество шкафов,

тогда: 3x₁+2x₂ ® max;

9,2x₁+4x₂£520,

0,3x₁+0,6x₂£24,

2x₂£40,

x₁³0; x₂³0.

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

На графике проведем прямую 9,2x₁+4x₂=520, найдем две точки, в которых искомая прямая пересекает оси х₁ и х₂.

При х₂=0, х₁= =56,5, при х₁=0, х₂= =130

Через точку (56,5; 130) проведем прямую АВ.

Проведем прямую соответствующую уравнению 0,3x₁+0,6x₂=24; х₂=0; х₁=80; х₁=0; х₂=40.

Прямая СD(80;40)

Третья прямая EF соответствует уравнению 2х₂=40 , она проходит параллельно оси х₁ и пересекает ось х₂ в точке х₂=20 (рисунок 21).

Убедиться в том, с какой стороны от прямой лежит полуплоскость, точки которой удовлетворяют заданному неравенству, можно путем подстановки координат точек одной или другой полуплоскости в неравенство. Когда прямая, ограничивающая полуплоскость, не проходит через начало координат, удобнее всего подставлять точку с координатами (0,0). Если координаты точки удовлетворяют неравенству, то эта точка лежит в полуплоскости, соответствующей данному неравенству. В противном случае неравенству будет соответствовать другая полуплоскость.

Существует и другой способ определения полуплоскости. Если коэффициент при х₂ в ограничении положительный, то неравенству «>» соответствует полуплоскость, лежащая выше граничной прямой, а неравенству «<» — полуплоскость, лежащая ниже граничной прямой. Если коэффициент при х₂ в ограничении отрицательный, то наоборот.

Рис. 21.

Область определения задачи будет представлять собой пересечение всех построенных полуплоскостей. В данном случае это пятиугольник ОАРFЕ. В этой области находятся все допустимые решения задачи. Необходимо выбрать такое, которое обеспечивало бы большую прибыль, т.е. 3x₁+2x₂®max. Положим произвольно: 3x₁+2x₂=120. Тогда прямая KL пройдет через точки х₁=40; х₂=60. Точки, лежащие на этой прямой отвечают программам, при которых прибыль составляет 120тенге. Это не максимум прибыли. Для решения задачи нужно найти прямую, которая расположена дальше других (наибольшая прибыль), но имеет хотя бы одну общую точку с пятиугольником OAPFE. Нужно переместить прямую KL параллельно самой себе так, чтобы она не "оторвалась" от этого пятиугольника и имела с ними хотя бы одну общую точку. В задаче это прямая MN и общая точка Р. Найдем координаты точки Р. 1-ый способ — снять с графика, 2-ой способ — решить совместно уравнения 2-х прямых АВ и СD.

9,2x₁+4x₂=520

0,3x₁+0,6x₂=24 Получим: х₁=50; х₂=15

Максимальная прибыль 3∙50+2–15=180(тг.)

Свойства решений задач линейного программирования. Ранее отмечалось, что все допустимые планы задачи линейного программирования образуют так называемую область определения задачи. Примем без доказательства следующую теорему: область определения задачи линейного программирования представляет собой выпуклое множество.

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

Определение 2. Множество называется замкнутым, если ему принадлежат все граничные точки.

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

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

В двумерном пространстве утверждение второй части теоремы будет иметь место, если прямая f(x)=c₁x₁+c₂x₂=0 при передвижении по области в необходимом направлении совпадает с одной из граничных прямых области. Такое совпадение возможно только при равенстве угловых коэффициентов данных прямых.

Если целевая функция достигает своего экстремального значения в одной точке, то задача имеет единственное оптимальное решение; если — более чем в одной точке, то задача имеет бесконечное число оптимальных решений.

Множество планов задачи линейного программирования может быть:

1) замкнутым ограниченным — в этом случае задача обязательно имеет одно или бесконечное число оптимальных решений;

2) замкнутым неограниченным — в этом случае задача имеет одно или бесконечное число решений, когда в силу неограниченности множества значение целевой функции не ограничено;

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

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

Пример: Ежедневный рацион кормления сельскохозяйственных животных состоит из двух видов кормов (сено и концентраты), и требования к качеству кормов ограничивается содержанием трех компонентов — кормовых единиц, белка и кальция. В таблице 9 приведены числовые данные о суточной потребности одного животного в питательных веществах, о содержании питательных веществ в 1кг кормов каждого вида и о себестоимости кормов в данном хозяйстве.

Таблица 9

Требуется найти самый дешевый рацион с тем условием, чтобы он содержал необходимое количество питательных веществ не меньше установленной потребности.

Обозначим: х₁ — необходимое количество сена,

х₂ — необходимое количество концентратов,

тогда:

1,5x₁+2,5x₂®min;

0,5x₁+x₂³20,

50x₁+200x₂³2000,

10x₁+2x₂³100,

x₁³0; x₂³0.

Прямая АВ: 0,5x₁+x₂=20 Координаты (40;20)

Прямая АС: 50x₁+200x₂=2000 Координаты (40;10)

Прямая DЕ: 10x₁+2x₂=100 Координаты (10;50)

Произвольно приравняем 1,5x₁+2,5x₂=30

Рис. 22

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

Это прямая MN с общей точкой Р (пересечение прямых АВ и DЕ):

0,5x₁+x₂=20,

10x₁+2x₂=100.

Решив систему, получим: х₁=6,67, х₂=16,67.

Себестоимость данного рациона составляет: 1,5×6,67+16,67×2,5=51,7 (тг.)

Примечание: прямая АС (белки) не участвует в области образования допустимых решений.