Методические рекомендации к практическим занятиям по дисциплине «Математическое и имитационное моделирование» для студентов специальности «Прикладная информатика (в менеджменте)» (стр. 4 )

.

Задачи для самостоятельной работы

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

Вид ресурса	Вид товара	Объём ресурса
1	2	3	4
Сырьё (кг)	3	5	2	4	60
Рабочая сила (ч)	22	14	18	30	400
Оборудование (станко-часы)	10	14	8	16	130
Прибыль на ед. товара (ден. ед.)	30	24	56	48	max

По этим исходным данным решить следующие задачи:

а)        выяснить, какой ассортимент товара надо выпускать, чтобы прибыль была максимальной;

б)        определить оптимальный ассортимент при дополнительном условии: первого товара выпустить не более 7 ед., второго — не менее 8 ед., а третьего и четвертого — в отношении 1:2.

Задача 2. Для изготовления изделий № 1 и № 2 имеется 180 кг металла. На изготовление одного изделия № 1 расходуется 2 кг металла, а изделия № 2 - 3 кг. Составить план производства, обеспечивающий получение наибольшей выручки от продажи изделий, если отпускная цена одного изделия № 1 равна 13 руб., а изделия № 2 — 17 руб., причем изделий № 1 требуется изготовить не более 60, а изделий № 2 — не более 40.

Вид сырья	Запасы (ед. объёма)	Вид продукции
П1	П2	П3
S1	2106	3	3	9
S2	2340	10	9	15
S3	650	5	5	1
Стоимость продукции (ден. ед.)	80	60	50

Задача 3. Для изготовления трех видов продукции П1, П2, П3 используются три вида сырья S1, S2, S3, запасы которых указаны в таблице. Известны количества единиц сырья S1, S2, S3, необходимые для производства единиц продукции П1, П2, П3 соответственно, и стоимость реализации каждой единицы готовой продукции.

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

Практическое занятие «Решение транспортных задач»

Цели занятия: научиться строить математические модели транспортных задач и находить оптимальное решение.

Транспортная задача

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

ai > 0 — объем (запас) груза в пункте Ai,

bj > 0 — объем груза, необходимого в пункте Bj,

сij >0 — стоимость (тариф) перевозки единицы груза из Ai. в Bj.

Требуется определить план перевозок груза из пунктов Ai. в Bj так, чтобы:

вывезти весь груз от отправителей Ai.. удовлетворить потребность в грузе (спрос) каждого потребителя Bj транспортные расходы были минимальными.

Под планом задачи подразумевается матрица

,

где xij — количество единиц груза, который необходимо перевезти из точки Ai в точку Bj.

Для разрешимости транспортной задачи необходимо и достаточно, чтобы имело место условие баланса

В этом случае транспортная задача называется закрытой.

Если условие баланса нарушено, то транспортная задача называется открытой.

Если задача с неправильным балансом (открытая), то:

при (спрос меньше предложения) необходимо ввести «фиктивного» потребителя груза: . при (спрос больше предложения) необходимо ввести «фиктивного» поставщика груза: .

Стоимости перевозок от «фиктивного» поставщика до всех потребителей и от любого поставщика до «фиктивного» потребителя принимаются равными нулю.

Неотрицательная матрица X, удовлетворяющая условиям задачи называется планом (или допустимым планом) задачи. Допустимый план называется оптимальным, если он доставляет минимум целевой функции. опустимый план, имеющий не более n+m–1 отличных от нуля компонентов xij, называется базисным, или опорным. Опорный план, имеющий ровно n+m–1 отличных от нуля компонент, называется невырожденным, а если число отличных от нуля компонент меньше, чем n+m–1, то план называется вырожденным.

Алгоритм решения транспортной задачи (для закрытой транспортной задачи):

1) Строим начальный опорный план. Одним из возможных методов нахождения первоначального опорного плана является метод "северо-западного" угла, метод минимальных тарифов.

Начальный и последующие планы заносятся в распределительную таблицу, в которой заранее записываются исходные данные задачи. Таблица с внесенными пунктами отправления Ai, их запасами ai, пунктами назначения Bj, их запросами bj и тарифами cij (i = 1,2,..., т; j = 1,2,...,п) имеет вид:

Bj Запас	B1	B2	...	Bn
Ai Спрос	b1	b2	...	bn
A1	a1	c11	c12	…	c1n
A2	a2	c21	c22	…	c2n
...	...	…	…	…	…
Am	am	cm1	cm2	…	cmn

2) Проверяем опорный план на оптимальность методом потенциалов.

Находим потенциалы строк Ui и потенциалы столбцов Vj по формуле: Ui + Vj = cij для занятых клеток, cij - тариф.

Количество потенциалов — (m + n), а количество занятых клеток равно (m + n - 1). Т. е. однозначно потенциалы не находятся. Обычно полагают, что U1 = 0, тогда остальные потенциалы вычисляются однозначно.

Находим оценки свободных клеток Δij= cij — (Ui + Vj).

Если все оценки свободных клеток Δij ≥ 0, то опорный план является оптимальным — решение закончено. Если при этом все Δij > 0, то оптимальный план является единственным. В противном случае имеет место альтернативная оптимизация.

Если хотя бы одна из оценок Δij < 0, то опорный план допускает улучшения.

3) Среди свободных клеток с отрицательными оценками находим клетку с наименьшей оценкой и обозначаем ее "*".

4) Строим означенный цикл с начальной вершиной в этой клетке.

Циклом с начальной вершиной в данной клетке называется замкнутая ломаная, обладающая следующими свойствами:

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

Цикл называется означенным, если в его вершинах расставлены знаки "+" и "-" так, что в свободной клетке стоит знак "+", а соседние вершины имеют противоположные знаки.

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

5) Выбираем минимальную поставку z среди поставок в клетках со знаком "-". Найденная поставка передвигается по циклу. При этом поставка в клетках цикла со знаком "+" увеличивается на z, а в клетках со знаком "-" уменьшается на z. Клетка с выбранной поставкой z, после перераспределения поставок по циклу считаться свободной остальные клетки цикла — заполненными. Таким образом, получен новый опорный план.

6) См. п.2 алгоритма.

Задачи для самостоятельной работы

В задачах 1-6 решить транспортные задачи, заданные таблицами

Задача 1.

Вj Ai	125	75	200	380	220
222	20	18	11	8	3
188	10	10	5	2	4
210	2	17	8	4	3
300	3	9	17	8	4

Задача 2.