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

Подбор параметра

 

Инструмент Подбор параметра (вкладка Данные >группа Работа с данными> пиктограмма Анализ “что-если” >пунктПодбор параметра) позволяет найти значение аргумента, удовлетворяющее желаемому значению функции. С его помощью можно получать результаты, которые трудно или невозможно получить прямо.

Замечание. Здесь и далее клетки, содержащие формулы выделены фоном (в электронной версии – желтым).

Задача 1. Пусть расчет зарплаты выполняется следующим образом (рис.1-1а). Налогом облагается не вся зарплата. Сумма обложения меньше заработка на налоговый вычет (1000р) на самого работника и на каждого ребенка. Здесь же учитываются вычеты медицинской страховки (2%). Что бы избежать отрицательности суммы обложения, в D3 используется функция МАКС(), которая обеспечивает равенство нулю суммы обложения, если она становится отрицательной. На рис. 1-1а представлены формулы. На рис. 1-1в – результат для штатного работника Ивана. Для него расчет ведется в обычном порядке – вводится заработок (30000р) и автоматически вычисляется результат (26060р).

Теперь решим обратную задачу. Пусть вы договорились с некоторым исполнителем (Петром) о выполнении разовой работы за 5000 руб. “чистыми” и с Олегом за 500р. Чтобы провести эти выплаты в бухгалтерии следует определить исходную зарплату до изъятия всех вычетов. Т.е. решить обратную задачу – определить неизвестную исходную зарплату Петра по известной сумме “на руки”. Вызвав Подбор параметра, зададим (рис. 1-1б) аргументы: Установить в ячейке: G4, в новое Значение: 5000, Изменяя значение ячейки: B4. После нажатия ОK, Excel выдает окно Результат подбора параметра, где отображаются ожидаемые результаты операции. В данном случае системе удалось подобрать аргумент (B4 =5663) при котором для Петра результат равен 5000. Далее, если Решение найдено и пользователь согласен с ними, следует нажать ОК, если нет – кнопку Отмена (произойдет возврат к исходным значениям). Аналогичные действия совершаем для Олега. Здесь (маленькая зарплата) видим, что налог с него не удерживается

При наборе, клетки в строках 4 и 5, заполняются формулами, скопированными из строки 3. Клетки В4 и В5 не заполняются в ручную, а вычисляются компьютером.

 

 

	A	B	C	D	E	F	G		Подбор параметра   Установить в ячейке: G4   Значение:   Изменяя значение ячейки: $B$4   ОК Отмена
	Вычет:			Расчет зарплаты			Рис. 1-1а
	Имя	Зарплата	Дети	Сумма обложения	Налог	Страховка	НА РУКИ
	Иван			=МАКС(B3-B$1*C3;0)	=13%*D3	=1%*B3	=B3-E3-F3
							Рис. 1-1в
	Иван
	Петр
	Олег								Рис.1-1б

 

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

	A	B	C	D		Подбор параметра
	Продуктовый расчет
	Объем сырья:				Установить в ячейке:	$D$6
	Этап	Коэфф. потерь	Объем потерь	Выход		Значение:
	Изменяя значение ячейки:	$C$2
		0,05	?	?
		0,11	?	?
		0,02	?	?
				Рис.		-2
	A	B	C			Подбор параметра
	Вклад:
	Сложные проценты			Установить в ячейке:	$C$7
	Норма	Доход	Сумма			Значение:
	10%	?	?			Изменяя значение ячейки:	$B$1
	12%	?	?
	15%	?	?
	18%	?	?	Рис.		-3

Задача 2. Продуктовый расчет. Пусть (рис. 1-2) нужно по известному объему используемого сырья (С2) вычислить выход некоторого продукта на каждом этапе обработки (столбец D) и итоговый выход D6. Известны потери продукта на каждом этапе обработки относительно предыдущего этапа (столбец В). Написать формулы расчета. Это была формулировка прямого продуктового расчета. Однако часто нужно вычислить требуемый объем сырья для производства заданного количества продукта (обратный продуктовый расчет). Пусть, мы хотим выяснить, сколько сырья требуется для выпуска 2000 единиц продукции. Для этого в окне Подбор параметра нужно задать аргументы. В результате мы должны получить объем потребного сырья в 2414. Кроме этого, будет произведен перерасчет потерь и остатков на выходе для всех этапов технологического процесса. Введите нужные формулы. Выполните подбор.

Задача 3. Расчет дохода. Обычно требуется найти сумму на счету от начального вклада (у нас 100 т. руб.) в течение нескольких лет при известной ежегодной норме прибыли. Заполните таблицу рис.1-3 необходимыми формулами. Поставим задачу обратным образом. Пусть нужно выяснить, сколько средств следует положить на счет, чтобы в конце расчетного периода накопить 500 т.руб. (клетка С7). Используя Подбор параметра. можно выяснить, что нужно вложить 299,1 т.руб. Введите формулы. Сделайте подбор.

Задача 4. Пусть нужно выяснить перспективы производства некоторого продукта. Известно, что понадобятся первоначальные инвестиции на строительство цеха и закупку минимального оборудования в объеме 50000$ для выпуска первых 1000 единиц продукции в месяц. Изготовление одного изделия требует сырья на 5$. Расширение выпуска возможно только партиями до 1500 штук для чего каждый раз требуется покупка оборудования (станка) на 7000$. Известна рыночная цена изделия 20$. Нужно найти уровень производства, обеспечивающий его безубыточность, а также графически проанализировать динамику доходов, расходов, прибыли и себестоимости в зависимости от количества выпущенного товара. Отобразим наши данные и формулы в таблице на рис. 1-4а.

Здесь: Расходы=Строительство+Сырье+Затраты_на_расширение

или G2=A2+E2*C2+ОКРУГЛВВЕРХ((E2-B2)/1500;0)*D2.

Последнее слагаемое в формуле учитывает дискретный характер расходов на расширение производства. Каждый раз, когда число единиц товара, на которое увеличивается выпуск, превышает 1,5 тыс. к расходам добавляется 7000$ на покупку нового станка. Остальные формулы:

Себестоимость=Расходы/Произведено_товара или H2=G2/E2.

Доход=Произведено_товара*Рыночная_цена или I2=E2*F2.

Прибыль=Доход–Расходы или J2=I2-G2.

Первоначальный выпуск установлен в 1000 штук. Видим, что при этом результаты нашей деятельности принесут только убытки в объеме 35000$.

Задача состоит в том, чтобы определить минимальное количество единиц выпускаемого товара, которое обеспечит безубыточность производства, т.е. когда прибыль=0 или, что тоже самое, когда себестоимость=рыноч­ная цена.

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

 

	A	B	C	D	E	F	G	H	I	J
	Строи- тельство	Начальный выпуск	Расходы сырья на 1 штуку	Затраты на следующие 1,5 тысячи	Произведено единиц товара	Рыночная цена единицы	ВСЕГО расходов	Себестоим. единицы	Доход	Прибыль
	50000$		5$	7000$		20$	55000$	55$	20000$	-35000$	Рис.1-4а
	50000$		5$	7000$		20$	94667$	20$	94667$	0$	Рис.1-4б

Подбор параметра
Установить в ячейке: $L$2   Рис.1-4в Значение:   Изменяя значение ячейки: $E$2   ОК Отмена
Рис.1-4в

С тем, чтобы проанализировать динамику бизнеса в наглядном виде, на том же листе ниже построим таблицу (рис.1-4г), содержащую формулы

B6=ОКРУГЛВВЕРХ((A6-$B$2)/1500;)*$D$2+$A$2+A6*$C$2, C6=A6*$F$2, D6=C6-B6, E6=B6/A6.

	A	B	C	D	E
	Единиц	Расходы	Доходы	Прибыль	Себест.
				-35000	55,0
				-34500	43,0
				-27000	33,5
				-19500	27,8
				-19000	26,3
				-11500	23,3
				-4000	21,0
				-3500	20,8
					19,2
					17,9
					18,0
					17,0
					16,1
			Рис.1-4г

Точка безубыточности

Рис.1-4д

 

Аргументом таблицы является объем выпуска товара, начиная с 1000 шагом 500. Из нее построим (рис.1-4д) графики изменения расходов, доходов, прибыли (единицы измерения слева) и себестоимости (единицы справа) товара. Ступенчатый характер кривых объясняется вливанием очередных инвестиций (покупок станков) в расширение производства.

Инструмент Подбор параметра позволяет решать сравнительно простые задачи с единственным неизвестным значением. Ниже будет рассмотрено более сильное средство.

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

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

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

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

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

Задача 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П1 + 6П2 £18 потребность в сырье 6П1 + 4П2£ 24 ‚трудовые ресурсы 2П1 + 1П2³ 2 ƒтранспортные расходы 5П1+5,5П2ÞF=max целевая функция (прибыль) П1 ³ 0, П2 ³ 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,

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