Методы оптимальных решений

Задача 1.  Найти максимум целевой функции L =4x+3y при следующих ограничениях:

Решить задачу при дополнительном условии (ДУ):

ДУ: Найти  минимум целевой функции L=2x-3y при тех же ограничениях.

Решение:

1. Найдем множество  допустимых планов.

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

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

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

 

В нашем случае множеством ограничений выступает набор из 5 неравенств. На рисунке им соответствуют полуплоскости, образованные прямыми АE, DE, BC, OX и OY (координатные оси соответствуют условиям x≥0 и y≥0). Пересечение всех полуплоскостей образует пятиугольник ABCDE. Чтобы в этом убедиться, возьмём какую-нибудь точку внутри него, например (2,2). Подставляя координаты х=2 и у=2 в ограничения, видим, что выполняются все. Любая точка пятиугольника будет решением системы ограничительных неравенств, поскольку лежит в тех же полуплоскостях, что и (2,2). Таким образом, множество допустимых планов замкнуто и максимум линейной формы достигается на одной из его граничных точек. 

 

Рисунок 1.

                                                                                                                                                                                                                         

 

 

 

 

 

 

 

 

 

 

 

2. Найдем оптимальное  решение L= max.

Построим вектор = grad L(x,y) , который укажет направление наибольшего возрастания целевой функции. Прямая, перпендикулярная вектору (в нашем случае его координаты (4,3)), соответствует L=const. Если перемещать такую прямую в направлении вектора , значения L будут возрастать. Максимальное значение L, т.е. оптимальное решение, достигается в последней точке ее пересечения с множеством допустимых планов. На рис.2 показана прямая, соответствующая L=0, она проходит через начало координат.

 

 

Рисунок 2.

                                                                                                                                                                                                                         

 

 

 

 

 

 

 

 

Решение задачи сводится к нахождению точки области ABCDE, наиболее удаленной от прямой L=0. Из рисунка видно, что это одна из точек A, D, E.

 

Угол наклона прямой ах+bу=с к оси ОХ определяется отношением a/b. Для прямой L=const это отношение составляет 4/3, что больше отношения 8/7 и меньше отношения 9/6 для прямых AE и ED. Это значит, что ED проходит круче PQ (проходящая через точку E L=const), а PQ – круче AE. Точки A и D лежат ниже прямой PQ, значит максимальное значение L и оптимальное решение достигаются в точке E. Найдем ее координаты .

 

Точка Е лежит на пересечении прямых 8х+7у=56 и 9х+6у=54 (см. рис. 1). Координаты точки Е должны быть решениями уравнений обеих прямых, т.е. надо решить систему

 

Вычтем второе уравнение из первого, получим у-х=2, у=х+2

Подставим у=х+2 в первое уравнение, получим 8х+7х+14=56, 15х=42, х=42/15, у=72/15

 

Итак, максимум L достигается в точке (42/15,72/15), значение L в этой точке составит (42/15)*4+(72/15)*3=384/15

 

3. Найдем минимум функции L=2x-3y при тех же условиях.

 

Градиент  имеет координаты (2, -3). На рис. 3 показана прямая, соответствующая значению L=16. Будем мысленно перемещать ее в направлении, противоположном , т.е. влево и вверх по чертежу. Достигнув точки D, она пройдет над областью допустимых планов и покинет ее в точке A. При этом значение L будет всё время уменьшаться. Значит, минимальное значение L на области допустимых планов достигается в точке А с координатами (0,8). L(0,8) = 2*0 - 3*8= -24.

 

 

 

 

 

Рисунок 3

 

                                                                                                                                                                                                                         

 

 

 

 

 

 

 

 

 

 

 

 

 

Ответ: Целевая функция L=4x+3y на области допустимых планов достигает максимального значения 384/15 при х=42/15 и у=72/15. Функция L = 2х - 3у при тех же ограничениях достигает минимума -24 при х=0, у=8.

 

 

3.2.  Предприятие производит изделия  А и В и использует сырье трех видов. На производство одного изделия А требуется 3 т сырья первого вида, 2 т – второго и 2 т – третьего вида, а на производство одного изделия В соответственно 4 т, 2 т и 3 т. Производство обеспечено сырьем первого вида в количестве 120 т, второго 60 т. Условия поставки и хранения сырья третьего вида таковы, что его расход должен быть не менее 30 т. Одно изделие А дает предприятию 2 млн. руб прибыли, а изделие В – 3 млн. руб прибыли. Составить план производства изделий А и В, максимизирующий общую прибыль предприятия.

 

Решение.

 

1. Приведение условий  задачи к канонической форме.

 

Составим сводную таблицу данных:

Таблица 1.

Сырье, т	Продукция		Запасы, т
	А	В
1	3	4	120
2	2	2	60
3	2	3	≥30
Прибыль, млн.р.	2	3

 

Пусть х₁ - количество изделий А, х₂ – количество изделий В, которое произведет предприятие. При этом оно израсходует  (3х₁+4х₂) т сырья первого вида, (2х₁+2х₂) т сырья второго вида, (2х₁+3х₂) т сырья третьего вида и получит прибыль (2х₁+3х₂) млн.р.

Итак, следует решить задачу линейного  программирования:

 

(1)

 

Сразу обратим  внимание на то, что при положительных  х₁, х₂ второе неравенство сильнее первого. Действительно, 4х₁+4х₂≤120, так что 3х₁+4х₂≤120 верно при всяком неотрицательном х₁. Следовательно, первое ограничение ничего не добавляет в систему и может быть исключено. Это существенно упростит задачу.

Чтобы преобразовать неравенства в равенства, введем вспомогательные переменные х₃ и х_4. Система ограничений при этом примет вид:

 

           (2)

 

Экономический смысл переменной х₃ – остаток сырья второго вида, х₄ – использованное сверх минимальной установленной нормы сырье третьего вида.

Следует найти такие допустимые х_1… х_4, при которых целевая функция L=2х₁+3х₂+0х₃+0х₄ достигает максимума. Для решения задачи применим симплекс-метод.

 

2. Нахождение начального  опорного плана. 

 

Система ограничений (2) не является приведенной  в смысле преобразования Гаусса, поскольку  х₄  входит во второе уравнение со знаком минус. Мы можем, конечно, умножить это уравнение на -1, получив таким образом базис {х₃ х₄} и опорный план (0,0,60,-30), но последний содержит отрицательное значение, что противоречит условиям поставленной задачи. Поэтому следует найти какой-нибудь другой базис, который бы соответствовал опорному плану с положительными координатами. Нам подойдет, например, базис {х₂ х₃}.

Приведем систему (2) к этому базису. Для этого, во-первых, избавимся от х₂ в первом уравнении. Для этого умножим второе уравнение на 2/3 и вычтем из первого. Затем разделим второе  уравнение на 3, так чтобы х₂ входил в него с коэффициентом 1. В итоге получим (поменяв местами уравнения)

 

           (3)

 

Присвоив свободным переменным х₁ и х₄ значение 0, получим х₂=10 и х₂=40

Вектор х⁰ = (0, 10, 40, 0) и будет начальным опорным планом нашей задачи.

 

3. Итерации симплекс-метода  и отыскание оптимального плана.

 

Заполним симплекс-таблицу 2 в следующем порядке:

Сначала разместим по столбцам х_1… х₄, b и строкам х₂ х₃ расширенную матрицу системы (3).

 

	х1	х2	х3	х4	b	bi/αik
х2	2/3	1	0	-1/3	10
х3	2/3	0	1	2/3	40
Δ

 

Далее, заполним нижнюю строку оценками опорного плана. Рассчитаем их по формулам ([1], с.169):

 

      (4)

где с=(2,3,0,0) – коэффициенты целевой функции, σ= {2,3} – список базисных индексов, т.е. с_σ = (3,0). j=1…5

 

Δ₀=2*0+3*10+0*40+0*0=30

Δ₁=3*2/3+0*2/3-2= 0

Δ₂=3*1+0*0-3=0

Δ₃=3*0+0*1-0=0

Δ₄=3*(-1/3)+0*2/3-0=-1

 

Заносим Δ_j в j-е столбцы, Δ₀ в столбец b:

Таблица 2

	х1	х2	х3	х4	b	bi/αik
х2	2/3	1	0	-1/3	10
х3	2/3	0	1	2/3	40
Δ	0	0	0	-1	30

 

Среди оценок есть отрицательные, значит выбранный нами опорный план не является оптимальным. Введем в базис вектор х₄ – ему соответствует минимальная оценка -1. В старом базисе он имел координаты (-1/3, 2/3), из которых положительна только одна – по вектору х₃ – его следует вывести из базиса.

 

Пересчитаем таблицу 2 так, чтобы столбец х₄ принял вид (0,1,0). Для этого строку х₃ следует разделить пополам и прибавить к строке х₂ , а также умножить на 3/2  и прибавить к индексной строке. Результаты преобразований занесем в таблицу 3.

 

Таблица 3

	х1	х2	х3	х4	b	bi/αik
х2	1	1	1/2	0	30
х3	1	0	3/2	1	60
Δ	1	0	3/2	0	90

 

Подставляя  х₁ = х₃ =0, получим новый опорный план: х¹ = (0, 30, 0, 60). В индексной строке больше нет отрицательных значений, значит полученный опорный план и будет оптимальным. Значение целевой функции на этом плане 2*0+3*30 = 90.

 

Ответ: Предприятию  следует производить только изделия В в количестве 30 шт. Прибыль составит 90 млн. р.

 

 

Задача 3.  Из пунктов отправки a₁ … a₃ требуется перевезти груз в пункты назначения b₁ … b₃ . Количество груза и цены на перевозку приведены в таблице 1. Найти минимально затратный план перевозок.

Таблица 1

По\Пн	=2	=5	=4
=6	3	2	3
=3	1	1	1
=2	2	2	2

Решение.

 

1. Найдем начальный опорный план.

 

   В опорном плане должно быть n+m-1, базисных переменных, а значит в таблице столько же занятых клеток, где n – количество По, а m – Пн. В нашем случае n+m-1=3+3-1=5, значит столько заполненных клеток должно быть в нашей транспортной таблице.

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