Рис. 5п-4. Оптимальная точка

XI+ 3X2= 12 4X1 + 3X2 = 24

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

При одновременном решении двух уравнений, приходится изменять одно или оба уравнения таким образом, чтобы получить наборы одинаковых коэффициентов. Затем, вычитая одно уравнение из другого, мы получим одно уравнение с единственной переменной. В данном случае, коэффициенты при Х2 равны, так что изменять их нет необходимости. (В конце данного приложения, решение задачи 1 показывает более общий случай.) Итак, просто вычитая одно уравнение из другого, мы получим нужный результат: 4X1 + 3 Х2 = 24

1 + 3x2)= 12 3x7 = 12

Решив полученное уравнение, находим xi = 4. Затем, подставив найденное значение xi водно из уравнений (безразлично в какое), находим значениеХ2. Например, для второго уравнения: 4+3x2= 12

Решая, находим Х2 = 8:3 или 2,67. Таким образом, решение данной задачи, которое даст максимальную прибыль, таково: произвести 4 единицы изделия 1 и 2,67 единиц изделия 2. Подставляя эти значения в целевую функцию, получим оптимальную прибыль:

4(4)+ 5(2,67)= 29,35.

Решения и угловые точки

Область возможных решений в графическом линейном программировании представляет собой многоугольник. Более того, решение любой задачи будет находиться в одной из угловых точек этого многоугольника. В редких случаях линия целевой функции может быть параллельна одной из линий ограничения. Когда это случается, каждая комбинация xi и Х2 на сегменте ограничения, который касается области возможных решений, представляет собой оптимальное решение. Следовательно, одна задача может иметь несколько оптимальных решений. Но даже в этом случае, решение будет находиться в угловой точке. Фактически, решение будет в двух угловых точках: на

2 4 6 8

Рис. 5п-5. Решение всегда находится в угловой точке

2 4 6 8 10 12 14 X,

Рис. 5п-6. Целевая функция параллельна одной из линий ограничения

концах сегмента, который касается области возможных решений. На рис. 5п-5 и 5п-6 показаны решения в угловых точках и линия целевой функции, которая параллельна линиям ограничений. Н а рис. 5п-5 показана задача, которая только что была решена в этом разделе, но для другой целевой функции: Z=2x, + 14x2-

Минимизация

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

Пример 2

Решение следующей задачи использует графическое линейное программирование. Минимизировать: Z = 8xi +12 Хг Ограничения: 5xi + 2x2 > 20

4X1 + 3x2 > 24

Х2>2 XI, Х2>0

решение:

1. Постройте линии ограничений (как показано на рис. 5п-7).

а. Перепишите ограничения в виде равенств.

б. Для каждого ограничения приравняйте xi=0 и решите относительно Х2, затем приравняйте Х2=0 и решите относительно xi.

в. Отобразите каждое ограничение графически. При этом обратите внимание, что Х2 = 2 - это горизонтальная линия, параллельная оси координат xi и распо-ложеная на 2 единицы выше нее.

2. Заштрихуйте область возможных решений (см. рис. 5п-7).

3. Постройте целевую функцию.

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

Попробуйте так: 8 х 12 = 96; 8xi+ 12x2 = 96 (приемлемо).

б. Постройте линию целевой функции (см. рис. 5п-8).

4. Перемещайте линию целевой функции к началу координат, сохраняя ее параллельность с исходной линией.

5. Оптимум (последняя точка осуществимости) показан на рис. 5п-8. Координата Х2 (Х2 = 2) может быть определена непосредственно по графику. Обратите внимание, что точка оптимума находится на пересечении линий Х2 = 2 и линии, заданной уравнением 4xi+ 3 Х2 = 24. Подставляя значение Х2 в последнее уравнение, получим значение xi на пересечении:

4X1+3(2) = 24 XI =4,5

Таким образом, оптимум получен при значениях xi = 4,5 и Х2 = 2.

6. Вычисление минимальных затрат: 8X1+ 12X2 = 8(4,5) + 12 (2) = 60.

10 12 14

Рис. 5п-7. Ограничения определяют область возможных решений