Задача 5.3

Транспортная компания "На колесах" заключила контракт с тремя мебельными фабриками на поставку высококачественной древесины, производимой одним из пяти поставщиков. Транспортные затраты на 1 тыс. м³ древесины содержатся в таблице:

	Фабрика А	Фабрика В	Фабрика С
Поставщик I	350	400	300
Поставщик II	400	590	740
Поставщик III	500	380	440
Поставщик IV	580	240	390
Поставщик V	120	220	290

Потребности фабрики А составляют 120 тыс. м³ в месяц, фабрики В - 140 тыс. м³, фабрики С - 110 тыс. м³, в то время как каждый из поставщиков вырабатывает в тот же период 75 тыс. м³ древесины.

Затраты на погрузку и разгрузку 1 тыс. м3 древесины составляют 30 руб.

Технические возможности не позволяют перевозить древесину от поставщика V на фабрику В.

Каковы минимальные затраты компании на выполнение условий контракта?

Задача 5.4

Маркетинговый отдел литейного завода прогнозирует спрос на производимые заводом детали в начале следующего года: январь - 10 тыс. шт., февраль - 14 тыс. шт., март - 16 тыс. шт., апрель - 12 тыс. шт.

При работе в одну смену можно изготавливать 12 тыс. деталей в месяц. Затраты на производство одной детали составляют 200 рублей. Если завод будет работать и во вторую смену, это позволит производить дополнительно 3 тыс. деталей в месяц, но затраты на производство одной детали во вторую смену составят уже 250 рублей.

Хранение детали на складе обходится заводу в 10 рублей в месяц.

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

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

Общая постановка задачи: требуется распределить n работ между n рабочими так, чтобы затраты на выполнение работ были минимальными или эффективность использования рабочей силы была максимальной.

Модель задачи в случае минимизации затрат о назначениях выглядит так:

(20)

где: с_ij - затраты на выполнение i-м рабочим j-й работы;

x_ij - переменная модели: x_ij=1, если i-й рабочий назначен на работу j, x_ij = 0, если i-й рабочий не назначен на работу j.

В случае максимизации эффективности использования рабочей силы за с_ij обозначают коэффициент, показывающий эффективность выполнения i-м рабочим j-й работы, и задача решается на максимизацию целевой функции.

Если количество рабочих не равно количеству работ, задача является открытой или несбалансированной и требует приведения к замкнутому виду путем введения недостающих рабочих или работ в необходимом количестве, для которых все с_ij = 0.

Пример:

Фирма получила заказ на разработку пяти программных продуктов.

Для выполнения заказа решено привлечь пятерых наиболее опытных программистов. Каждый из них должен написать одну программу. В таблице приведены оценки времени в днях, необходимого программистам для выполнения каждой из этих работ:

	Программа1	Программа2	Программа3	Программа4	Программа5
Галкин	46	59	24	62	67
Палкин	47	56	32	55	70
Малкин	44	52	19	61	60
Чалкин	47	59	17	64	73
Залкинд	43	65	20	60	75

Как распределить работы между программистами, чтобы общее количество человеко-дней, затраченное на выполнение заказа, было минимальным?

Составим модель линейного программирования, отражающую условие:

(21)

Решим задачу при помощи Microsoft Excel:

Рис. 26

При решении задач о назначении особый интерес вызывает способ ввода ограничений при заполнении формы модуля Поиск решения:

Рис. 27

Проведенные расчеты показывают, что минимальное количество человеко-дней для выполнения заказа составляет 234. Назначение программиста для создания программы определяется наличием на пересечении строки и столбца значения 1.

Рис. 28

Для решения задачи в Mathcad необходимо сначала задать целевую функцию, присвоить переменным их стартовые значения, а затем ввести ограничения, как показано на рис. 29.

Рис. 29

Результатом вычислений с использованием функции minimize являются следующие значения переменных:

Значения остальных переменных равны нулю.

Полученное решение означает, что Галкину будет поручено выполнение работы 5, Палкину – работы 4, Малкину – работы 2, Чалкину – работы 3, Залкинду – работы 1.

Полученное решение не совпадает с решением этой задачи, полученным при помощи Microsoft Excel. Однако, присвоив переменным значения, полученные в процессе оптимизации, выясним, что значение целевой функции в данном случае равно 234. При решении задачи в Microsoft Excel значение целевой функции тоже равно 234. Это свидетельствует о наличии как минимум двух альтернативных решений задачи, при которых общее количество затраченных человеко-дней будет минимальным.

Задачи

Задача 6.1

В Центральном административном округе города Москвы открываются 4 магазина торговли по предварительным заказам - в районах Басманный, Замоскворечье, Мещанский и Таганский. Идея проекта состоит в том, что товары хранятся на четырех централизованных складах, находящихся в Северном, Северо-Восточном, Южном и Западном административных округах, и несколько раз в день по мере поступления заказов доставляются в магазины небольшими партиями.

Время, затрачиваемое на доставку продукции со складов в магазины, приведено в таблице (в минутах):

	Басманный	Замоскворечье	Мещанский	Таганский
Северный	20	30	15	30
Северо-Восточный	15	25	20	20
Южный	35	15	30	20
Западный	30	20	20	30

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