Разработка управленческого решения

Математическая модель задачи выглядит следующим образом.

Целевая функция имеет вид:

0x11+270× x12+430× x13+160× x14+70× x21+0× x22+160x23+10x24+200× x31+130x32+0× x33+ +350× x34+210× x41+160x42+250× x43+0× x44® min,

Ограничения имеют вид:

x11+x21+x31+x41=1,

x12+x22+x32+x42=1,

x13+x23+x33+x43=1.

x14+x24+x34+x44=1,

x11+x12+x13+x14=1,

x21+x22+x23+x24=1,

x31+x32+x33+x34=1,

x41+x42+x43+x44=1,

u2-u3+3× x23£ 2,

u2-u4+3× x24£ 2,

u3-u2+3× x32£ 2,

u3-u4+3× x34£ 2,

u4-u2+3× x42£ 2,

u4-u3+3× x43£ 2.

Вид электронной таблицы, созданной для решения задачи, представлен на рис. 40. Значения переменных xij располагаются в блоке B3:E6. В данном блоке ячейки, расположенные по диагонали обнулены (пункт назначения не может быть одновременно пунктом прибытия) и выделены, для удобства задания ограничений. Даны стоимости проезда из города в город (блок B11:E14). Для вычислений необходимо задать размерность задачи n (количество городов)- ячейка F16.

Рис. 40

Целевая функция расположена в ячейке F8. Ограничения находятся в блоках B7:E7 (коммивояжер въезжает один раз в каждый город) и F3:F6 (коммивояжер выезжает из каждого города один раз) (см. рис. 40 и 41). Вид электронной таблицы в режиме отображения формул представлен на рис. 41. В задаче коммивояжера есть ряд специфических ограничений по дополнительным переменным ui (см. мат модель). Формулы этих ограничений находятся в блоке ячеек B17:E19. Значения самих переменных располагаются в блоке B8:E8.

На рис. 42 представлена запись условий задачи в окне "Поиск решения". Как известно, дополнительные переменные не относятся к целевой функции, но они, также как и xij, являются изменяемыми, поэтому адреса содержащих их ячеек должны быть введены в поле Изменяя ячейки одновременно с адресами переменных целевой функции.

Операцию ввода удобно проводить с помощью мыши. Необходимо установить курсор ввода в поле Изменяя ячейки, затем выделить мышью блок ячеек переменных целевой функции, нажать <Ctrl> и, удерживая эту клавишу, выделить мышью блок ячеек рабочего листа, отведенный для переменных ui. В поле ввода адреса блоков отделяются ";" (см. рис. 42).

Рис. 41

Перечислим ограничения, которых не видно на рис. 42: $C$4=0; $D$5=0; $E$6=0; $F$3:$F$6=1.

Рис. 42

Первая запись в группе Ограничения представляет собой совокупность ограничений по дополнительным переменным ui. Каждая ячейка блока в левой части неравенства содержит формулу одного ограничения (см. рис. 41 и мат. модель), правую часть представляет одно значение, равное n-2, содержащееся в F18. Такая запись означает, что каждая ячейка блока $B$17:$D$19 меньше либо равна 2 (4-2=2).

В поиске решения нельзя явно задать ограничение i¹ j. Исходя из смысла переменных xij можно предположить, что значения тех xij, для которых i=j (расположенных по диагонали в блоке переменных), всегда должны быть равны 0 и ввести соответствующие ограничения. В группе Ограничения таких ограничений четыре: $B$3=0, $C$4=0, $D$5=0, $E$6=0.

По результатам поиска решения найден ответ задачи: из Парижа коммивояжер летит в Лондон, оттуда в Рим, затем в Берлин, откуда возвращается в Париж. Общая стоимость перелета составит 610 д. е. (см. рис. 40).

4. 9. Задача о доставке

Фирма обслуживает 5 клиентов. Каждый день она доставляет своим клиентам товары на грузовых машинах. Существует 3 допустимых маршрута доставки, каждый из которых позволяет обслужить определенное количество клиентов и требует использования в течении дня одного транспортного средства. Каждый маршрут характеризуется определенными расходами (см. табл.). Необходимо выбрать такое множество маршрутов, при котором обеспечивается обслуживание каждого из клиентов и, кроме того, суммарные расходы минимальны, при условии, что каждый клиент обслуживается один раз в день.

Таблица обслуживания клиентов по маршрутам
Клиенты	Маршруты
	1	2	3
1	1		1
2	1
3	1		1
4		1
5		1	1
Расходы по маршруту	900	1000	800

Математическая модель задачи выглядит следующим образом.

Целевая функция имеет вид:

900× x1+1000× x2+800× x3® min,

Ограничения имеют вид:

1× x11+0× x21+1× x31=1,

1× x12+0× x22+0× x32=1,

1× x13+0× x23+1× x33=1,

0× x12+1× x22+0× x32=1,

0× x13+1× x23+1× x33=1.

Вид электронной таблицы Excel, созданной для решения задачи, представлен на рис. 43. Значения переменных xj располагаются в блоке ячеек B10:D10 (см. рис. 43). Коэффициенты целевой функции, отражающие стоимость доставки по маршруту, находятся по адресам B9:D9. Данные об обслуживании клиентов по маршрутам имеются в блоке B4:D8

Рис. 43

Формулы целевой функции и ограничений находятся соответственно в ячейке E10 и ячейках E4:E8 (каждый клиент обслуживается по каждому маршруту только один раз в день) (см. рис. 43 и 44). Вид электронной таблицы в режиме отображения формул представлен на рис. 44.

Рис. 44

Запись условий задачи в окне "Поиск решения" можно увидеть на рис. 45.

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

Рис. 45

5. Варианты заданий

В приводимых ниже задачах требуется по словесному описанию составить экономико-математическую модель задать исходные данные и получить результат средствами Microsoft Excel.

5.1. Завод выпускает изделия двух типов: А и В. При этом используется сырье четырех видов. Расход сырья каждого вида на изготовление единицы продукции и запасы сырья заданы следующей таблицей:

Изделия	Сырье
	I	II	III	IV
А	2	1	0	2
B	3	0	1	1
Запасы сырья	21	4	6	10

Выпуск одного изделия типа А приносит 3 денежные единицы прибыли, одного изделия типа В- 2 денежные единицы. Составить план выпуска продукции, обеспечивающий наибольшую прибыль.

5.2. На заводе используется сталь трех марок: А, В и С, запасы которых соответственно равны 10, 16, и 12 ед. Завод выпускает два вида изделий. Для изделия I требуется по одной единице стали всех марок. Для изделия II требуется 2 единицы стали марки В, одна- марки С и не требуется сталь марки А. От реализации единицы изделия вида I завод получает 300 руб. прибыли, вида II- 200 руб. Составить план выпуска продукции, дающий наибольшую прибыль.

5.3. Предприятие располагает ресурсами двух видов в количестве 120 и 80 ед. соответственно. Эти ресурсы используются для выпуска продукции I и II, причем расход на изготовление единицы продукции первого вида составляет 2 ед. ресурса первого вида и 2 ед. ресурса второго вида, единицы продукции второго вида- 3 ед. ресурса первого вида и 1 ед. ресурса второго вида. Прибыль от реализации единицы продукции первого вида составляет 600 руб., второго вида- 400 руб. Составить план выпуска продукции, обеспечивающий наибольшую прибыль, при условии, что продукции первого вида должно быть выпущено не менее продукции второго вида.

5.4. Фабрика выпускает три вида тканей. Суточные ресурсы фабрики следующие: 700 ед. производственного оборудования, 800 ед. Сырья и 900 ед. электроэнергии, расход которых на единицу ткани представлен в таблице.

Ресурсы	Ткани
	I	II	III
Оборудование	2	3	4
Сырье	1	4	5
Электроэнергия	3	4	2

Цена одного метра ткани I равна 8 руб., ткани II- 7 и ткани III- 6 руб. Сколько надо произвести ткани каждого вида, чтобы прибыль от реализации была наибольшей?

5.5. Четыре станка обрабатывают два вида деталей: А и В. Каждая деталь проходит обработку на всех четырех станках. Известны: время обработки детали на каждом станке, время работы станков в течении одного цикла производства и прибыль, получаемая от выпуска одной детали каждого вида. Эти данные приведены в таблице.

Станки	Время обработки одной детали, ч.		Время станка за один цикл производства, ч.
	A	B
I	1	2	16
II	2	3	25
III	1	1	10
IV	3	1	24
Прибыль на одну деталь, руб.	400	100

Составить план производства, обеспечивающий наибольшую прибыль.

5.6. Для откорма животных употребляют два корма: 1 и 2. Стоимость одного килограмма корма 1- 5 руб., корма 2- 2 руб. В каждом килограмме корма 1 содержится 5 ед. витамина А, 2,5 ед. витамина В и 1 ед. витамина С. В каждом килограмме корма 2 содержится 3 ед. витамина А, 3 ед. витамина В и 1 ед. витамина С.

Какое количество корма каждого вида необходимо расходовать ежедневно, чтобы затраты на откорм были минимальными, если суточный рацион предусматривает не менее 225 питательных единиц витамина А, не менее 150 ед. витамина В и не менее 80 ед. витамина С?

5.7. На птицеферме употребляется два вида кормов- I и II. В единице веса корма I содержится единица вещества А, единица вещества В и единица вещества С. В единице веса корма II содержатся четыре единицы вещества А, две единицы вещества В и не содержится вещество С. В дневной рацион каждой птицы надо включить не менее единицы вещества А, не менее четырех единиц вещества В и не менее единицы вещества С. Цена единицы веса корма I составляет 30 руб., корма II- 20 руб. Составить ежедневный рацион кормления птицы так, чтобы обеспечить наиболее дешевый рацион питания.

5.8. На трех станциях отправления А, В и С имеется соответственно 50, 20 и 30 ед. однородного груза, который нужно доставить в пять пунктов назначения П1, П2, П3, П4, П5 в количестве соответственно 30, 5, 25, 15 и 25 ед. Эти данные, а также стоимость перевозки единицы груза от каждой станции отправления к каждому пункту назначения указаны в таблице.

Пункты	Запасы	Пункты назначения и их потребности
отправления	груза	П1	П2	П3	П4	П5
А	50	4	1	2	3	3
В	20	3	1	5	2	4
С	30	5	6	1	4	2
		30	5	25	15	25

Составить такой план перевозок грузов, чтобы затраты на эти перевозки были минимальными.