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

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

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

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

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

Задача 1. Планирование производства. Положим, цех производит два вида продукции Продукт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 для прямой, значит начало координат входит в полуплоскость, иначе – нет. На рисунке штриховка для ограничивающих прямых направлена в сторону допустимых решений. Т.о. может быть определен выпуклый многоугольник, удовлетворяющий всем ограничениям (заштрихован). Все возможные решения находятся внутри него, но оптимальное решение обязательно лежит на границе этой области, обычно в одной из ее вершин.

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

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

	A	B	C	D	E	F
1	П1	Сырье	Труд	Трансп.	F	Мax
2	0	3	6	2	5,0	5,0
3	1	2,5	4,5	0	4,1
4	2	2	3	#Н/Д	3,2
5	3	1,5	1,5	#Н/Д	2,3
6	4	1	0	#Н/Д	1,4
7	5	0,5	#Н/Д	#Н/Д	0,5
8	6	0	#Н/Д	#Н/Д	-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,

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

емкость_канистры*число_канистр  вес_заказа.

На рис. 2-2а показана таблица оптимизации, содержащая исходные данные и формулы:

E2=B2*B3+C2*C3+D2*D3, G2=F2–E2.

Снова используем Поиск решения, где введем следующие параметры:

	A	B	C	D	E	F	G
1	Расфа- совка:	Контей- неры	Бочки	Кани- cтры	Отгру- зка	Заказ	Раз- ность
2	Емкость:	270кг	130кг	90кг	0кг	1400кг	1400кг
3	Единиц:	0шт	0шт	0шт			Рис. 2-2а
2	Емкость:	270кг	130кг	90кг	1400кг	1400кг	0кг
3	Единиц:	1шт	8шт	1шт			Рис. 2-2б

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

равной минимальному значению.

Изменяя ячейки: B3:D3.

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

B3:D3 целое,

B3:D3 0,

E2 F2.

В качестве критерия используется значение разности (G2) между заказанным объемом и фактически отгруженным. На рис. 2-2б показан результат.

Задача 3. Транспортная задача. Решим проблему оптимальной (самой дешевой) доставки некоторого объема груза из нескольких исходных пунктов (складов) в несколько пунктов доставки (магазинов).

Пусть с трех складов требуется развезти закупленные в них грузы в объемах (столбец B на рис. 2-3а) 50, 30 и 40 тонн потребителям в два магазина в объеме 40 и 80 тонн соответственно (D7 и F7). Известна цена (в тыс. руб.) доставки одной тонны груза с каждого склада в каждый пункт доставки (столбцы С и Е). Задача заключается в том, чтобы определить такие объемы перевозок со складов в магазины (области D3:D5 и F3:F5), чтобы стоимость транспортировки (G7) была минимальной. Стоимость перевозки в каждый магазин вычисляется в столбце G: G3=C3*D3+E3*F3, G4=C4*D4+E4*F4, G5=C5*D5+E5*F5. Общая сумма доставки в G7=СУММ(G3:G5). Кроме того, введем функции суммирования (Фактически доставлено) в D6=СУММ(D3:D5), F6= СУММ(F3:DF).

На рис. 2-3б показана таблица в исходном состоянии.

Далее используя Поиск решения, введем параметры:

	A	B	C	D		E	F	G
1			Магазин 1			Магазин 2			Стоим.
2	Грузы на складах (т)		Цена достав.		Груз (тонн)	Цена достав.	Груз (тонн)		доставки
3	склад 1	50	1			0,5
4	склад 2	30	2			2,5
5	склад 3	40	1,5			1
6			Факт:			Факт:		ИТОГО:
7			Нужно:	40		Нужно:	80
								Рис.2-3б
3	склад 1	50	1	10		0,5	40	30
4	склад 2	30	2	30		2,5	0	60
5	склад 3	40	1,5	0		1	40	40
6			Факт:	40		Факт:	80	ИТОГО:
7			Нужно:	40		Нужно:	80	130
								Рис.2-3в
3	склад 1	100	1	36,67		0,5	63,33	68,3
4	склад 2	100	2	0		2,5	0	0,0
5	склад 3	100	1,5	33,33		1	16,67	21,7
6			Факт:	40		Факт:	80	ИТОГО:
7			Нужно:	40		Нужно:	80	90
								Рис.2-3г

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

равной минимальному значению.

Изменяя ячейки: D3:D5; F3:F5.

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

грузы, вывозимые со складов:

B3=D3+F3; B4=D4+F4; B5=D5+F5

условие положительности объемов доставки:

F3:F5>=0; D3:D5>=0

условие выполнения заявок магазинов:

D7=D6; F7=F6

На рис. 2-3в таблица после оптимизации. Видим, стоимость доставки – 130 тыс.

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

D3:D5=целое и F3:F5=целое.

В рассмотренной задаче подразумевалось, что вес имеющегося для покупателя груза на складах равен весу запрошенного (сбалансированная задача). Это может быть в случае, когда товар предварительно отобран и закуплен у продавца именно в таких объемах на каждом из его складов. Если общий вес товара на складах превышает запрошенный и продавцу безразлично с какого из складов осуществляется его вывоз, вероятно можно найти более дешевое решение. Пусть (рис. 2-3г) на складах имеется товар в объемах 100т. Полученный результат равен 90т. руб. Здесь только потребовалось изменить условия B3<=D3+F3; B4<=D4+F4; B5<=D5+F5.

Такое решение соответствует интересам покупателя. В интересах перевозчика, наоборот, желательно увеличить транспортные расходы и сделать максимальным значение С7, т.е.