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

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

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

1000× (60× x11+15× x21+20× x31)+900× (10× x12+30× x22+20× x32)+800× (40× x13+15× x23+15× x33)® max,

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

x11+x12+x13=50,

x21+x22+x23=75,

x31+x32+x33=50,

60× x11+15× x21+20× x31£ 1000,

10× x12+30× x22+20× x32£ 700,

40× x13+15× x23+15× x33£ 900,

xij³ 0, i, j= .

В транспортной задаче переменные xij занимают не ряд ячеек (строку или столбец), а располагаются в виде таблицы (матрицы), поэтому данная задача называется двухиндексной (по количеству индексов перед переменной x). Значения переменных xij представлены в блоке ячеек B3:D5 (см. рис. 25). Коэффициенты целевой функции, отражающие стоимость единицы выращиваемого продукта находятся по адресам B6:D6. Требования к объему урожая каждой из культур (bj) заданы в ячейках B7:D7. Урожайности культур на единице площади (aij) заданы в блоке B11:D13.

Рис. 25

Формулы целевой функции и ограничений находятся соответственно в ячейке E8 и ячейках B8:D8 (ограничения по минимальному урожаю), E3:E5 (ограничения по площади) (см. рис. 25 и 26). Вид электронной таблицы в режиме отображения формул представлен на рис. 26.

Рис. 26

В окне "Поиск решения" (см. рис. 27) задаются адрес формулы ЦФ ($E$8), адрес блока xij ($B$3:$D$5) и ограничения. В группе Ограничения (см. рис. 27) первой является запись граничных условий. Вторая и третья записи выражают ограничения по уровню минимального урожая и наличию располагаемой площади i-го поля соответственно.

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

Рис. 27

4. 4. Рациональное использование  технологических участков

Предприятию требуется за 30 дней выпустить 400 единиц Продукта1, 350 единиц Продукта2 и 800 единиц Продукта3. Продукция производится на трех различных технологических участках. Производительность каждого участка по каждому продукту (количество единиц продукции j-го вида j= , которое можно произвести на i-м участке i= в день) приведена в таблице.

Известны затраты на производство j-го продукта на i-м участке в день (см. табл.).

Требуется составить оптимальный план работы участков, т.е. найти сколько времени i-й участок будет занят производством j-го продукта с тем, чтобы общие издержки были наименьшими.

№ Участка	Производительность участков (ед-ц в день)
	Продукт1	Продукт2	Продукт3
1	20	20	15
2	14	15	20
3	12	11	15
План. объем вып-ка	400	350	800

Затраты на производство продукции (руб. в день)

№ Участка	Продукт1	Продукт2	Продукт3
1	230	190	140
2	230	180	130
3	190	140	100

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

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

230× x11+190× x12+140× x13+230× x21+180× x22+130× x23+190× x31+140× x32+100× x33® min,

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

x11+x12+x13£ 30,

x21+x22+x23£ 30,

x31+x32+x33£ 30,

20× x11+14× x21+12× x31=400,

20× x12+15× x22+11× x32=350,

15× x13+20× x23+15× x33=800,

xij³ 0, i, j= .

Вид электронной таблицы Excel, созданной для решения задачи, представлен на рис. 28. Значения переменных xij располагаются в блоке ячеек B3:D5 (см. рис. 28). Коэффициенты целевой функции, отражающие затраты на производство продукции в единицу времени находятся по адресам B15:D17. Данные о производительности участков находятся в блоке B10:D12. Требования к планируемому объему выпуска каждого продукта заданы в ячейках B6:D6. Заданное время работы участков введено в E10.

Рис. 28

Рис. 29

Формулы целевой функции и ограничений находятся соответственно в ячейке E7 и ячейках B7:D7 (ограничения по плану), E3:E5 (ограничения по времени) (см. рис. 28 и 29). Вид электронной таблицы в режиме отображения формул представлен на рис. 29.

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

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

Рис. 30

4. 5. Закрепление самолетов за  воздушными линиями

Три типа самолетов требуется распределить между четырьмя авиалиниями. В приводимых ниже таблицах задано число самолетов каждого типа, месячный объем перевозок каждым самолетом на каждой авиалинии и соответствующие эксплуатационные расходы.

Требуется распределить самолеты по авиалиниям так, чтобы при минимальных суммарных эксплуатационных расходах перевезти по каждой из четырех авиалиний соответственно не менее 300, 200, 1000 и 500 единиц груза.

Тип самолета	Число самолетов	Месячный объем перевозок одним самолетом по авиалиниям
		I	II	III	IV
1	50	15	10	20	50
2	20	30	25	10	17
3	30	25	50	30	45

Тип самолета	Эксплуатационные расходы
	I	II	III	IV
1	15	20	25	40
2	70	28	15	45
3	40	70	40	65

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

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

15× x11+20× x12+25× x13+40× x14+70× x21+28× x22+15× x23+45× x24+40× x31+70× x32+40× x33+65× x34® min,

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

15× x11+30× x21+25× x31³ 300,

10× x12+25× x22+50× x32³ 200,

20× x13+10× x23+30× x33³ 1000,

50× x14+17× x24+45× x34³ 500,

x11+x12+x13+x14=50,

x21+x22+x23+x24=20,

x31+x32+x33+x33=30,

xij³ 0, целые (i= , j= ).

Вид электронной таблицы Excel, созданной для решения задачи, представлен на рис. 31. Значения переменных xij располагаются в блоке ячеек B4:E6 (см. рис. 31). Коэффициенты целевой функции, отражающие расходы на перевозку находятся по адресам B18:E20. Данные о месячных объемах перевозок одним самолетом имеются в блоке B12:E14. Задан план перевозок и число самолетов- соответственно блоки B7:E7 и F4:F6.

Рис. 31

Формулы целевой функции и ограничений находятся соответственно в ячейке F8 и ячейках B8:E8 (ограничения по плану), F4:F6 (ограничения по количеству самолетов) (см. рис. 31 и 32). Вид электронной таблицы в режиме отображения формул представлен на рис. 32.

Рис. 32

Рис. 33

В группе Ограничения (см. рис. 33) заданы, помимо остальных, ограничения на целочисленность переменных (первая запись), означающие, что количество выбранных самолетов (значения xij) должно быть целым числом. Задание ограничения на целочисленность увеличивает время вычислений Поиска решения.

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

4. 6. Задача о ранце

В грузовую автомашину надо поместить четыре вида предметов, причем могут потребоваться несколько одинаковых предметов. Имеется три вида ограничений такого типа, как вес, объем и т.д. В приведенной ниже таблице даны aij- i-я характеристика предмета j-го наименования, cj- полезность одного предмета j-го наименования (i= , j= ). Требуется загрузить машину так, чтобы суммарная полезность груза была максимальной.

Ограничения	Предмет1	Предмет2	Предмет3	Предмет4	Значения ограничений
I	3	3	5	2	1000
II	4	2	4	4	600
III	3	5	4	3	600
Полезность	3	4	3	3

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

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

3× x1+4× x2+3× x3+3× x4® max,

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

3× x1+3× x2+5× x3+2× x4£ 1000,

4× x1+2× x2+4× x3+4× x4£ 600,

3× x1+5× x2+4× x3+3× x4£ 600,

xj³ 0, целые, j= .

Вид электронной таблицы Excel, созданной для решения задачи, представлен на рис. 34. Значения переменных xij располагаются в блоке ячеек B3:E3 (см. рис. 34). Коэффициенты целевой функции, отражающие полезности предметов находятся по адресам B6:E6. Данные о характеристиках предметов имеются в блоке B9:E11. Заданы значения ограничений- соответственно блок H9:H11.

Рис. 34

Формулы целевой функции и ограничений находятся соответственно в ячейке F6 и ячейках F9:E11 (ограничения по свойствам) (см. рис. 34 и 35). Вид электронной таблицы в режиме отображения формул представлен на рис. 35.

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

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

Рис. 35

Рис. 36

4. 7. Назначение механизмов на работы

Имеются три механизма М1, М2, М3, каждый из которых может быть использован на трех видах работ Р1, Р2, Р3 с производительностью (в условных единицах), заданной в виде таблицы:

Механизмы	Работы
	Р1	Р2	Р3
М1	1	2	3
М2	2	4	1
М3	3	1	5

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

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

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

x11+2× x12+3× x13+2× x21+4× x22+x23+3× x31+x32+5× x33® max,

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

x11+x12+x13=1,

x21+x22+x23=1,

x31+x32+x33=1,

x11+x21+x31=1,

x12+x22+x32=1,

x13+x23+x33=1.

Вид электронной таблицы Excel, созданной для решения задачи, представлен на рис. 37. Значения переменных xij располагаются в блоке ячеек B4:D6 (см. рис. 37). Коэффициенты целевой функции, отражающие производительность механизмов, находятся по адресам B11:D13.

Рис. 37

Формулы целевой функции и ограничений находятся соответственно в ячейке E8 и ячейках E4:E6 (каждый механизм может быть назначен только на одну работу), B8:D8 (каждая работа выполняется только на одном механизме) (см. рис. 37 и 38). Вид электронной таблицы в режиме отображения формул представлен на рис. 38.

Рис. 38

Рис. 39

Данная задача является задачей линейного булева программирования и в ней переменные xij должны принимать значения либо 0 либо 1. В поиске решения такое ограничение задается тремя ограничениями, по которым изменяемые ячейки в блоке (xij) одновременно больше либо равны 0, меньше либо равны 1 и являются целыми. Первые три записи в группе Ограничения (см. рис. 39) отражают этот факт.

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

4. 8. Задача коммивояжера

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

Пункты	Париж	Берлин	Рим	Лондон
Париж	0	270	430	160
Берлин	70	0	160	10
Рим	200	130	0	350
Лондон	210	160	250	0