Учись Учиться

Решение задачи линейного программирования (ЗЛП)  графическим методом

Общая постановка злп

Найти значения n переменных x₁, x₂, …,x_n, доставляющих экстремум (минимум или максимум) линейной функции Z=C₁x₁,+ C₂x_2+…+ C_nx_n

и одновременно удовлетворяющих m ограничениям вида

a_1,1x₁+a_1,2x₂+…+a_1,nx_n £ =≥b₁,

a_2,1x₁+a_2,2x₂+…+a_2,nx_n £ = ≥b₂,

. . . . . . . . . . . . . . . . . . . . . . .,

a_m,1x₁+a_m,2x₂+…+a_m,nx_n £ = ≥b_m,

при заданных a_i,j, b_i,, C_j (i=1,2,…,m; j=1,2,…,n). Знак отношения может принимать любое из трех приведенных значений.

Пример задачи линейного программирования

Рассмотрим следующую задачу. Менеджер предприятия, изготавливающего два вида красок, описал исследователю операций ситуацию, сложившуюся на производстве и рынке сбыта красок. Оказалось, что фабрика изготавливает два вида красок: для внутренних и внешних работ. Обе краски поступают в оптовую продажу. Для производства красок используются два исходных продукта – А и В. Максимально возможные суточные запасы этих продуктов 6 и 8 тонн соответственно. Опыт показал, что суточный спрос на внешнюю краску никогда не  превышает спрос на внутреннюю более чем на 1 тонну. Кроме того, установлено, что спрос на внешнюю краску никогда не превышает 2 тонны в сутки. Оптовые цены одной тонны красок сложились следующим образом: 3 тысячи рублей на внешнюю краску и 2 тысячи рублей – на внутреннюю. Какое количество краски каждого вида должна производить фабрика, чтобы доход от реализации был максимальным?

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

При построении математической модели специалист по исследованию операций ставит перед собой три вопроса.

• Для каких величин должна быть построена модель? Иначе говоря, нужно идентифицировать переменные задачи.
• Какие ограничения должны быть наложены на переменные, чтобы выполнялись условия, характерные для моделируемой системы?
• В чем состоит цель, для достижения которой из всех возможных (допустимых) значений переменных нужно выбрать те, которые будут соответствовать оптимальному (наилучшему) решению задачи?

Введем переменные:

x₁ – суточный объем производства  внешней краски (в тоннах),

x₂ – суточный объем производства внутренней краски (в тоннах).

Учитывая оптовые цены на тонну каждого вида краски, суточный доход от продажи произведенной продукции задается линейной целевой функцией Z = 3x₁ + 2x₂.

Целью производства является получение максимальной прибыли, значит, необходимо найти  значения x₁ и x₂, которые максимизируют целевую функцию Z.

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

Первый тип ограничений определяется запасами продуктов А и В, из которых производятся краски. Из технологии производства известно, что на производство тонны внешней краски идут две части продукта А, а на тонну внутренней –  одна часть. Для продукта В соотношение обратное. Эти технологические условия описываются неравенствами

2x₁ + x₂ £ 6     (на складе 6 тонн продукта А),

x₁ + 2x₂ £ 8    (на складе 8 тонн продукта В).

Последние два ограничения означают очевидное обстоятельство: нельзя использовать для производства красок больше продуктов А и В, чем их имеется фактически на складе.

Ситуация с реализацией красок на рынке приводит к следующим ограничениям: x₁ – x₂ £ 1 (внешней краски реализуется не более, чем на одну тонну больше внутренней), x₁ £ 2 (внешней краски продается не более двух тонн в день).

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

найти ®max{ Z=2×x₁ + 3×x₂} при следующих ограничениях на значения переменных x₁ и x₂

2×x₁ +   x₂ £ 6  ограничение (1),

x₁ + 2×x₂ £ 8  ограничение (2),

x₁ -   x₂ £ 1  ограничение (3),

x₁ £ 2  ограничение (4)

и требование неотрицательности переменных x₁ ³ 0  (5), x₂ ³ 0  (6).

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

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

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

Математическая модель, полученная для сформулированной типовой задачи, требует исследования, так как заранее не известно, имеет ли она (как математическая задача) решение. Исследование проведем с использованием графических построений. Одновременно с таким исследованием найдем (если оно есть) и решение.

1 этап. Построение области допустимых решений

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

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

• · заменить в ограничении  знак неравенства на равенство (получим уравнение прямой);

• · построить прямую по двум точкам;

• · определить, какую полуплоскость задает знак неравенства. Для этого подставить в неравенство какую-нибудь точку (например, начало координат). Если она удовлетворяет неравенству – закрашиваем полуплоскость, ее содержащую.

Такие действия выполняем для всех ограничений. Каждую из прямых обозначим номерами, принятыми при нумерации ограничений (см. рис).

Областью допустимых решений (удовлетворяющей всем ограничениям) является множество точек первого квадранта координатной плоскости (x₁, x₂), представляющее собой пересечение всех полуплоскостей, определяемых неравенствами ограничений.

 

Множество точек, удовлетворяющих всем шести ограничениям задачи – многоугольник AFEDCB.

2 этап Построение линий уровня целевой функции и определение точки максимума

Цель - найти в построенном многоугольнике AFEDCB точку, в которой функция цели Z=2x₁ + 3x₂ принимает максимальное  значение.

Проведем  прямую 2x₁ + 3x₂ = Сonst (линию уровня) так, чтобы она пересекала многоугольник AFEDCB (например,  Const=10). Эта линия уровня на рисунке изображена пунктирной линией.

Если рассматривать значения линейной целевой функции Z на множестве точек (x₁,x₂), принадлежащих отрезку пунктирной прямой, расположенному внутри шестиугольника, то все они равны одному и тому же значению (Const=10).

Определим направление возрастания функции. Для этого построим линию уровня с бОльшим значением. Это будет прямая, параллельная с построенной, но расположенная правее. Значит, в заданном направлении значение целевой функции возрастает, и в наших интересах сдвинуть ее как можно дальше в этом направлении.

Сдвиг можно продолжать до тех пор, пока перемещаемая прямая пересекает многоугольник допустимых решений. Последнее положение прямой, когда она имеет одну общую точку с многоугольником AFEDCB (точка С), соответствует максимальному значению целевой функции Z и достигается в точке С с координатами x₁= 4/3 (»1.333), x₂ =10/3 (»3.333). При этом Z = 38/3 ( »12.667).

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

Первое. Область допустимых решений – выпуклый многоугольник (Почему выпуклый? Может ли область допустимых решений представлять собой пустое множество? Точку? Отрезок? Луч? Прямую? Если да, приведите пример системы ограничений).

Второе. Максимум целевой функции достигается в вершине многоугольника допустимых решений (а может ли быть не единственное решение? Может ли решения не быть?)

Задание 1 (выполнить на занятии, показать преподавателю)

Решить графическим методом

А) F=2x1+3x2 è max При ограничениях x1+3x2 ≤ 18 2x1+x2 ≤ 16 x2 ≤ 5 3x1 ≤ 21 x1 ≥ 0 x2 ≥ 0	B) F=4x1+6x2 è min При ограничениях 3x1+x2 ≥ 9 x1+2x2 ≥ 8 x1+6x2 ≥ 12 x1 ≥ 0 x2 ≥ 0
C) F=3x1+3x2 è max При ограничениях x1+x2 ≤ 8 2x1-x2 ≥ 1 x1-2x2 ≤ 2 x1 ≥ 0 x2 ≥ 0	D) F=2x1-3x2 è min При ограничениях x1+x2 ≥ 4 2x1-x2 ≥ 1 x1-2x2 ≤ 1 x1 ≥ 0 x2 ≥ 0

Ответы:

A) x1=6          x2=4    F=24

B) x1=2          x2=3    F=26

C) x1Î [3..6] x2=8-x1          F=24

D) F=-∞

Задание 2 (выполнить на занятии, показать преподавателю)

Ответить на вопросы, выделенные курсивом.

Задание 3 (домашнее)

Написать программу.

Дан текстовый файл вида

2 3 (коэффициенты целевой функции)

4 (количество ограничений)

2 2 12 (ограничения)

1 2 8

4 0 16

0 4 12

Построить прямые так, чтобы многоугольник допустимых решений был целиком на экране (определение масштаба см. в кн. Онегова). Прямые могут быть параллельны осям!

Построить несколько линий уровня целевой функции (нажимаем клавишу – прямая перемещается, отображается значение целевой функции). Отобразить масштаб.