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

Такие задачи описываются системами линейных уравнений и линейными целевыми функциями.

Задача 1. Планирование производства. Положим, цех производит два вида продукции Продукт1 и Продукт2 (П1и П2). Рассчитать оптимальные недельные объемы производства этих продуктов с точки зрения максимизации прибыли. Прибыль (целевая функция – F) первого продукта составляет – 5 единиц, второго – 5,5.

На производстве действуют ограничения по сырью, трудовым ресурсам и транспортным расходам:

. Для Продукта1 требуется 3 единицы сырья, для Продукта2 – 6. Всего цех располагает 18 единицами сырья.

‚. Для изготовления Продукта1 требуется 6 рабочих, для Продукта2 – 4. В цехе 24 рабочих.

ƒ. Транспортные расходы на перевозку Продукта1 составляют 2 единицы, Продукта2 – 1 единицу. Эти затраты не могут быть менее 2 единиц по договору с автокомбинатом.

Очевидно также, что ни одна из переменных (число единиц продукции) не может быть менее нуля.

Отсюда запишем соотношения (объединены фигурной скобкой), из которых можно вычислить оптимальные объемы производства Продукта1 и Продукта2.

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

Область решений ограничена прямыми (пронумерованы), полученными из условий, в которых знаки неравенств заменены на знак “=”. Решение ищется в той полуплоскости, все точки которой удовлетворяют неравенству. Чтобы определить эту полуплоскость, для каждого из неравенств следует приравнять нулю значения П₁ и П₂. Если получено соотношение вида 0 £ Const для прямой, значит начало координат входит в полуплоскость, иначе – нет. На рисунке штриховка для ограничивающих прямых направлена в сторону допустимых решений. Т.о. может быть определен выпуклый многоугольник, удовлетворяющий всем ограничениям (заштрихован). Все возможные решения находятся внутри него, но оптимальное решение обязательно лежит на границе этой области, обычно в одной из ее вершин.

1 2 3 4 5 6

          1,5  

П2

П1

min(1;0))

max(3;1,5)

Рис. 2-1а

Направление перемещения целевой функции  



ƒ

‚

3П₁ + 6П₂ £18 потребность в сырье 6П₁ + 4П₂£ 24 ‚трудовые ресурсы 2П₁ + 1П₂³ 2 ƒтранспортные расходы 5П₁+5,5П₂ÞF=max целевая функция (прибыль) П₁ ³ 0, П₂ ³ 0 условие положительности  

	A	B	C	D	E	F		C	D	E
	№	Вид ресурса	П1	П2	Вычисл. значения	Заданные огранич.		П1	П2	Вычисл. значения
		Сырье								18,0
		Труд								24,0
		Транспорт								7,5
				Прибыль:				Прибыль:
		Целевая функция	5,0	5,5				5,0	5,5	23,25
		Результат				Рис. 2-1б		3,0	1,5	Рис. 2-1в

Для его поиска воспользуемся целевой функцией F. Строго говоря, она не является функцией, поскольку ее правая часть неизвестна. То есть, это бесконечное множество функций, о которых нам известно только, что они имеют одинаковый наклон. Определим его. Возьмем F=0. Тогда преобразуя выражение 5П₁+5,5П₂=0, можем записать что П₁/П₂=–5,5/5. Это тангенс наклона F. Теперь проведем любую прямую с таким наклоном. Ну пусть она и будет проходить через точки П₁=5 и П₂=5,5 (изображена пунктиром). Однако такое положение целевой функции и области решений нас не устраивает. Необходимо, чтобы эти объекты соприкасались. Для этого будем перемещать F параллельно самой себе до пересечения с областью решений. Очевидно, что минимум и максимум находятся на границе многоугольника в точках входа и выхода из него. Как видим, их две. Одна из них – точка пересечения прямых  и ‚. Чтобы найти ее координаты, совместно решим уравнения 1 и 2: 3П₁+6П₂ = 18; 6П₁+4П₂ = 24. Тогда получим П₁=3 и П₂=1,5. При этом прибыль цеха будет равна F=5*3+5,5*1,5=23,25. Еще, однако, не известно максимум ли это. Перемещая далее прямую ЦФ, найдем другое крайнее решение. Это точка, где П₁=1 и П₂=0 (где F=5*1+5,5*0=5). Поскольку 23,25>5, делаем вывод о том, что первая точка является оптимальным решением, вторая – минимальным. Возникает вопрос – почему минимальное значение прибыли 5, а не ноль (т.е. полное сворачивание производства). Дело в том, что условия нашей задачи предопределяют обязательные транспортные расходы в объеме не менее 2-х единиц, поскольку по договору с фирмой-перевозчиком автомобили арендуются в любом случае. Т.е. какую-то продукцию мы должны выпускать.

А сейчас решим эту задачу в Excel. (рис. 2-1б). Ограничения вносим в верхнюю часть таблицы. Коэффициенты уравнений – в C2:D4, правые части уравнений – в F2:F4. Коэффициенты целевой функции – в C6:D6. В процессе расчетов в области Е2:Е4 отобразятся вычисляемые (фактические) значения правой части неравенств. В E2 вводим E2=C2*С$7+D2*D$7, и копируем ее до E6. Результат (оптимальное количество П1 и П2) формируется в С7:D7. Клетки, в которых вычисляются какие-то значения, выделены жирным шрифтом. На рис. 2-1б показана таблица в исходном состоянии, на рис. 2-1в – готовый результат.

Для оптимизации воспользуется инструментом Поиск решения, вызываемым через вкладку Данные, который предъявляет окно поиска рис. 2-1г (вначале пустое). Здесь задаем ячейку, где будет формироваться оптимизируемое значение (Е6), затем указываем, что это максимум. Можно задать не только максимальное/минимальное значения, но и любую произвольную величину, введя ее в поле (Равной значению:). Ограничения устанавливаются с кнопкой Добавить, которая вызывает окно их ввода (рис. 2-1д).

Поиск решения

Установить целевую ячейку:  

Равной: žмаксимальному значению š значению: šминимальному значению

$C$7:$D$7

$C$7:$D$7 >=0 $E$2 <= $F$2 $E$3 <= $F$3 $E$4 >= $F$4

Предположить

Добавить

Изменить

Удалить

Изменяя ячейки:

Ограничения:

Выполнить

Закрыть

Параметры

Восстановить

Справка

$E$6

прибыль

продукция

ресурсы

Ссылка на ячейку: Ограничение:

ОК

Отмена

Добавить

Справка

$C$7:$D$7

>= €

Добавить ограничения

Решение найдено. Все ограничения и условия оптимальности выполнения. Тип отчета

ОК

Отмена

Сохранить сценарии...

Справка

Результаты поиска решения

Рис. 2-1е

  ž Сохранить найденное решение   š Восстановить исходные значения

Результаты  Устойчивость Пределы €

Рис. 2-1г

Рис. 2-1д

После ввода всех ограничений нажать кнопку Выполнить для решения задачи. Если вычисления оказались успешными, Excel предъявит (рис. 2-1е) окно итогов. Их нужно сохранить. Кроме того, можно получить один из трех видов отчетов (Результаты, Устойчивость, Пределы), позволяющие лучше осознать полученные результаты, в том числе, оценить их достоверность.

	A	B	C	D	E	F
	П1	Сырье	Труд	Трансп.	F	Мax
					5,0	5,0
		2,5	4,5		4,1
				#Н/Д	3,2
		1,5	1,5	#Н/Д	2,3
				#Н/Д	1,4
		0,5	#Н/Д	#Н/Д	0,5
			#Н/Д	#Н/Д	-0,5
					Рис	.2-1ж

Как видим, результаты (П1=3, П2=1,5), вычисленные в таблице, совпали с результатами, найденными вручную с помощью графика. Здесь же попутно мы можем сравнить предельные и фактически затребованные значения ресурсов (Сырье: 18 из 18; Труд: 24 из 24; Транспорт: 7,5). Конечно, нельзя отгрузить покупателю полтора изделия. В примере все единицы измерения условны (1,5 на самом деле может означать и 150 и 1500). Если же все-таки результат должен быть строго целым, при расчете на компьютере следует в окне ограничений указать это обстоятельство.

В отличие от графического способа, Excel позволяет получить оптимальное решение без ограничения размерности системы неравенств.

Указания. Графические построения можно вести и с помощью средств деловой графики Excel для чего построим таблицу (рис. 2-1ж). В первом столбце размещаем аргумент П₁ от 1 до 6. В следующих трех столбцах разместим функции-ограничения, разрешенные относительно П₂. Так в В2 поместим функцию (18-3*A2)/6. Поскольку П₂ и П₁ не могут отрицательными, сделаем так, что если это произойдет, клеточная функция выработает значение #Н/Д (нет данных). Такие значения будут игнорироваться при построении графика. Аналогично запишем и другие уравнения

В2=ЕСЛИ(18-3*A2>=0;(18-3*A2)/6;#Н/Д),

С2=ЕСЛИ(24-6*A2>=0;(24-6*A2)/4;#Н/Д),

D2=ЕСЛИ(2-2*A2>=0;2-2*A2;#Н/Д).

В Е2 поместим выражение для целевой функции, также разрешенной относительно П2: E2=-5*A2/5,5+$F$2. Поскольку правая часть целевой функции (т.е. искомый максимум) не задана, здесь можно указать пока любую константу, например 5. Далее можно изменять ее произвольным образом, добиваясь нужного положения целевой функции F на графике.

Приступим к созданию диаграммы, в качестве диапазона построения указав область А1:Е8. Выберем Точечную диаграмму со значениями, соединенными отрезками без маркеров. На мониторе видно, что целевая функция проходит над областью решений. Опустить функцию можно постепенно уменьшая значение в клетке F2 до пересечения с границей многоугольника. Обнаружив точку касания целевой функции и области решений, проведем (уже руками) из нее стрелки до координатных осей. С их помощью установим приблизительные значения П₂ и П₁, дающие максимум целевой функции (максимум содержимого клетки F2). Аналогично можно найти минимум. Теперь сделаем диаграмму более наглядной. Уже на готовом графике удалим цветовой фон, и установим шаг изменения меток, равным 0,5. Сообразуясь с видом ограничивающих уравнений, обведем область допустимых решений (используя фигуру Полилиния ) и закрасим в какой-нибудь цвет.

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

Задача 2. Расфасовка товара. Положим, требуется максимально полно выполнить заказ на поставку некоторого однородного жидкого материала (например, машинного масла) в объеме 1400 кг. в имеющуюся у продавца тару (контейнеры емкостью по 270 кг., бочки по 130 кг. и канистры по 90 кг.). Считаем, что отгружать товар можно в любой таре в любой комбинации таким образом, чтобы, по возможности, весь товар был размещен без остатка, т.е. отгружено £ вес_заказа.

Отсюда можно сформировать еще несколько ограничений:

число_контейнеров=целое, число_бочек=целое, число_канистр =целое,

число_контейнеров ³0, число_бочек ³0, число_канистр ³0,

емкость_контейнера*число_контейнеров +емкость_бочки*число_бочек+

Дата добавления: 2015-07-15