Пример 8

Вернемся к примеру 6.

В 1–м столбце указаны мощности поставщиков, в 1-й строке - спрос потребителей. Остальные числа таблицы - это стоимость перевозки единицы груза от соответствующего поставщика к соответствующему потребителю. Например, стоимость перевозки единицы груза от 3-го поставщика ко 2-му потребителю равна 3. Нужно составит оптимальный план поставок.

B данном случае модель закрытая (13000=13000). В таблице указана форма для решения задачи, введена зависимость для целевой функции.

	А	В	С	D	E
		4000	5000	1000
	6000	6
	3000	5
	4000	2
	Переменные
	Целевая функция	=6*В5+4*С5+9*D5+8*E5 +5*B6+3*C6+2*D6+8*E6 +2*B7+3*C7+6*D7+8*E7
	Oграничения
	4000	=В5+В6+В7
	5000	=С5+С6+С7
	1000	=D5+D6+D7
	3000	=E5+E6+E7
	6000	=В5+C5+D5+E5
	3000	=В6+C6+D6+E6
	4000	=В7+C7+D7+E7

Вводим формулы (указан способ введения формул без использования Мастер функций. Выделяем ячейку В8, в которой вычисляется целевая функция. Вызываем Сервис Поиск решения. В диалоговом окне в поле ввода Установить целевую ячейку уже содержится $B$8. Установим переключатель Равной минимальному значению. В поле ввода Изменяя ячейки нужно указать В5:Е7.

Поместим указатель мыши на кнопку Добавить. Появится диалоговое окно Добавление ограничения. В поле ввода Ссылка на ячейку укажем В10. Правее в выпадающем списке с условными операторами выберем =. В поле ввода Ограничение введем А10. Щелкнем кнопку Добавить и введем другие ограничения. Когда закроем поле ввода, мы окажемся в диалоговом окне и увидим введенные ограничения. С помощью кнопок Изменить и Добавить мы можем изменить и удалить ограничение. В поле ввода Выберите метод решения укажем Поиск решения линейной задачи симплекс методом. Щелкнем кнопку Параметры. Установим флажки по необходимости. Принять решение.

В ячейке В8 указано 52000. Это минимальные затраты на перевозку. В ячейках В5:Е7 указаны значения оптимального плана поставок.

	А	В	С	D	E
	Переменные

1-й поставщик должен доставит 3000 единиц груза 2-му и 4-му потребителю. 2-й поставщик должен доставить 2000 единиц груза 2-му потребителю и 1000 единиц груза 3-му. 3-й поставщик должен доставить 4000 единиц груза 1-му потребителю.

Задача о назначениях.

Задача о назначениях - это распределительная задача, в которой для выполнения каждой работы требуется один и только один ресурс (один человек, одна автомашина и т. п.), и каждый ресурс может быть использован на одной и только одной работе, т. е. ресурсы неделимы между работами, а работы - между ресурсами. Задача о назначениях является частным случаем транспортной задачи. Задача о назначениях имеет место при распределении людей на должности или работы, автомашин на маршруты, водителей на машины, групп по аудиториям, научных тем по научно-исследовательским лабораториям и т. п.

Исходные параметры задачи о назначениях:

m - количество ресурсов;

n - количество работ;

a_i = 1 – единичное количество ресурса А_i, (например: один работник; одно транспортное средство; одна научная тема);

b_j = 1 - единичное количество работы В_j, (например: одна должность; один маршрут; одна лаборатория);

с_ij – характеристика качества выполнения работы В_j c помощью ресурса А_i (например: компетентность работника i при работе на должности j; время, за которое транспортное средство i перевезет груз по маршруту j: степень квалификации лаборатории i при работе над научной темой j).

Искомые параметры:

x_ij - факт назначения или не назначения ресурса А_i на работу В_j:

x_ij =

f (X) - общая (суммарная) характеристика качества распределения ресурсов по работам.

Исходные данные задачи о назначениях можно свести в таблице.

Модель:

,

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

Работник	Время выполнения работы, часы
М1
М2
М3
М4
М5

1. Требуется назначить на каждый вид работы одного из работников. Как это нужно сделать, чтобы общее время, необходимое для завершения всех видов работ, было минимальным?

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

Рабочий по совместительству	Время выполнения работы, ч
М6
Определим, каким образом данная мера повлияет на назначение рабочих и минимизацию общего времени выполнения работ. Решение. Переменные: xij = i = ; j = . Целевая функция - суммарное время, необходимое для завершения всех видов работ, которое необходимо минимизировать. (Х) = 25 х 11 + 16 х 12 + 15 х 13 + 14 х 14 + 13 х 15 + 25 х 21 + 17 х 22 + 18 х 23 + 23 х24 + 15 х 25 + 30 х 31 + 15 х 32 + 20 х 33 + 19 х 34 + 14 х 35 + 27 х 41 + 20х 42 + 22 х 43 + 25 х 44 + 12 х 45 + 29 х 51 + 19 х 52 + 17 х 53 + 32 х 54 + 10 х 55 Функциональные ограничения: по работам по работникам Прямые ограничения: xij 0. Значения переменных xij располагаются в блоке ячеек В13:F17, в ячейку G18 введена формула для вычисления значения целевой функции. Введены формулы для вычисления ограничений по работам: в ячейку G13 введено =СУММ(В13:F13); в ячейку G14 ¾ =СУММ(В14:F14); в ячейку G15 ¾ =СУММ(В15:F15); в ячейку G16 ¾ =СУММ(В16:F13); в ячейку G17 ¾ =СУММ(В17:F17); в ячейку G18 ¾ =СУММПРОИЗВ(В4:F8,В13:F17); Аналогично вводятся формулы для вычисления ограничений по работникам. В окне Поиск решения, в частности Оптимизировать целевую функцию уже указана ячейка $G$18. Выбрать Равной минимальному значению. В окне Изменяя ячейки указать В13:F17.В группе Ограничения указать В18:F18=1; G13:G17=1, В13:F17=двоичное или бинарное, т.к. хi должно быть 0 или 1 (добавляя ограничение, следует выбрать опцию двоичное или бинарное в раскрывшемся списке Ограничения). В результате решения будет получен ответ на первый вопрос задачи.

Чтобы получить ответ на второй вопрос задачи, необходимо добавить ограничения по шестому работнику и в ограничениях по работникам знак = заменить на знак ≤.

В таблице указано закрепление шести работников за работами.

В окне Поиск решения, в частности Оптимизировать целевую функцию будет уже указана ячейка $G$21. Выбрать Равной минимальному значению. В окне Изменяя ячейки указать В15:F20.В группе Ограничения указать В21:F21=1; G15:G20 =1, В15:F20=двоичное или бинарное.

О т в е т.

1. Общее время, необходимое для завершения всех видов работ, равно 83 часа. Закрепление работников за работами приведено в таблице.

2. Прием на работу работника М6 приведет к изменению назначений работников на работы и позволит снизить общее время, необходимое для завершения всех видов работ, до 81 часа, но при этом работник М4 должен быть уволен или отправлен в отпуск.