Определение оптимального ассортимента продукции

Данная задача разобрана в задачнике [4 ] на стр.10, 11. Для выпуска трех видов продукции требуются затраты сырья, электроэнергии и оборудования:

Далее рассмотрена аналогичная задача, но заданы цены ресурсов, и прибыль (“Итого”, целевая ячейка, максимум) вычисляется как разность Дохода и Суммы затрат. Поиграйте ценами, в частности немного увеличьте цену на продукт № 3 (с 243 до 244). Вы получите резкое изменение плана, т.е. данный вектор цен является критическим. Вначале не выставляйте ограничение значений Выпуска Целые, затем выставьте, и сравните планы выпуска.

Планирование перевозок

Транспортная задача подробно рассмотрена в [ 4 ] на стр.79 – 98; на стр. 94 – 98 рассмотрено решение транспортной задачи средствами табличного процессора Excel.

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

Создайте таблицы:

- расстояния между заводами и стройками,

- потребности строек (строка),

- мощности заводов (столбец)

- первоначальный план перевозок – количество рейсов с

i-го завода на j-ю стройку:

Суммарная потребность всех строек должна совпадать с суммарной мощностью всех заводов (здесь S (D8:I8)=S(J5:J7) ).

- Запустите Сервис - Поиск решения и заполните окна появившейся экранной формы. Целевая ячейка в данном случае – J17, в которой находится суммарный пробег машин со всех заводов на все стройки, и значение в которой надо сделать минимальным (или заданным, если надо “нагнать” план по километражу). Изменять можно ячейки D10 : I12 (план перевозок) при условии равенства мощностей заводов и потребностей строек, то есть ячеек J10 : J12 и D13 : I13 значениям, заданным в J5 : J7 и D8 : I8. Кроме того, следует задать условие, что количества рейсов – величины положительные и целые. В окне Параметры установите флажок Показывать результаты итераций и отслеживайте изменение вывезенного и привезенного бетона и суммарного пробега. Запустите выполнение программы (Выполнить).

Планирование закупок

Предлагаемое упражнение является предельно упрощенным вариантом реальной задачи по составлению рациона для животных, которую можно сформулировать следующим образом: заданы нормы потребления различных компонент – жиров, белков и т.д. (в экономической интерпретации – благ) и их содержания в различных видах кормов, а также цены кормов. Требуется составить план закупки кормов, обеспечивающий минимальную стоимость рациона при потреблении благ не меньше норм. Для решения задачи требуется внести в таблицы Excel нормы, содержания компонент в кормах, цены кормов, а также опорный план – произвольные значения масс закупаемых кормов. Содержания компонент умножаем на массы кормов и суммируем по компонентам, получая их суммарные количества (сколько всего съедено жиров, белков и т.д.), которые в ограничениях Поиска решения устанавливаются больше или равными нормам. Умножаем цены кормов на их количества, суммируем произведения и получаем стоимость закупки – целевую функцию, для которой в Поиске решения задаем минимизацию. Изменяемые ячейки – массы закупаемых кормов, на них накладывается глобальное ограничение – требование неотрицательности. Все числа в данном примере – условные.

Составьте рацион для коровы из 4 видов кормов, содержащих 4 компонента (жиры, белки, углеводы, витамины), имеющий минимальную стоимость:

· составьте таблицу по приведенному образцу; рацион (количество кормов) задайте произвольно;

· перемножьте содержание компонент в кормах и их цены на количество соответствующих кормов (=B8*$G8, копируйте формулу);

· просуммируйте результаты умножения по столбикам (результаты – сколько всего компонент будет съедено и сколько это стоит);

· вызовите Сервис – Поиск решения;

· задайте Целевую ячейку с суммарной стоимостью (здесь F18), цель – Минимальное значение,

· Изменяя ячейки с количеством кормов (здесь G8:G11),

· Ограничения Добавить : суммарное потребление компонент должно быть не меньше норм (здесь B16:E16 ³ B6:E6) и количество кормов не может быть отрицательным (здесь G8:G11 ³ 0);

· ознакомьтесь с Параметрами и нажмите Выполнить.

	A	B	C	D	E	F	G
		жиры	белки	углеводы	витамины	цена	количество
	нормы
	Корма
	Сено
	Овес
	Ячмень
	Силос
	Сено	=B8*$G8
	Овес
	Ячмень
	Силос
18	Сумма	S(B13:B16)					Целевая

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

U(x)=П(x_i - a_i) ^ai

где a_i – минимально необходимое количество i - го блага, которое приобретается в любом случае (в данном случае – нормы),

a_i характеризует степень важности блага (эластичность).

Применительно к данной задаче функция Стоуна характеризует количество молока, и мы можем минимизировать стоимость рациона при заданном количестве молока или максимизировать количество при заданной стоимости. Для этого зададим a_i и вычислим функцию Стоуна, которую используем в качестве дополнительного ограничения. Целесообразно к выражению в скобках добавить очень малое число, например 10^-7, чтобы избежать отрицательных чисел, которые могут возникнуть из-за погрешности расчетов при вычитании равных величин.

 

	жиры	белки	углеводы	витамины
ai	0,3	0,3	0,15	0,25		Количество
(Si -норма i)^a i	4,761	3,265	2,245	2,864

 

Здесь приведены числа после решения задачи минимизации стоимости рациона при соблюдении норм и обеспечении количества 100.

Без изменения таблиц можно решить другую задачу – максимизировать функцию Стоуна, объявив ее целевой ячейкой, при заданной стоимости рациона, которая становится ограничением.

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

Далее представлен упрощенный вариант задачи. Благами являются пиво, рыба и раки, полезность рациона (целевая функция) вычислена по формуле Стоуна, ограничения: количества неотрицательные и целые, суммарная стоимость менее 1500.

	Цена	Минимум	Полезность α	Количество X	(X-Xmin)^α	Стоимость
Пиво			0,3		1,620
Рыба			0,25		1,626
Раки			0,45		1,866
					Целевая
					4,919

Нелинейное программирование

В предыдущей работе были решены задачи нелинейного и целочисленного программирования, т.е. целевая функция или ограничение задавались мультипликативной функцией Стоуна, а на изменяемые переменные накладывалось ограничение целочисленность. Технология решения задач нелинейного и динамического программирования с использованием Поиска решения аналогична решению задач линейного программирования, но следует знать о некоторых “подводных камнях”, связанных с возможным наличием нескольких или многих “волн” в целевой функции и в функциях ограничений. Компьютер ищет экстремумы градиентным итерационным методом, и он находит решение, ближайшее к точке начальных значений (“опорному плану”), а остальных решений, может быть существенно лучших с точки зрения экономики, “не видит”. Возможно, компьютер вообще не найдет решения, хотя оно существует. Поэтому при решении нелинейных задач следует внимательно отнестись к выбору начальных значений, т.к. от этого могут зависеть результаты. Возможно, при реальном планировании целесообразно взять старый план в качестве опорного. Вообще, здесь большой простор для экспериментов.

Пример: определить условный экстремум функции

Z = 3X₁² + 2X₂² – X₁ +1 при X₁² +X₂² = 4

Здесь хорошо видна зависимость решения от начальных значений Х₁ и Х₂.

Динамическое программирование