2. Задача о распределении механизмов между участками

Имеются четыре типа механизмов: Механизм 1, Механизм 2, Механизм 3 и Механизм 4, которые необходимо распределить между тремя участками работ A, B и C. Количество механизмов каждого типа составляет 74, 53, 45 и 24 штуки соответственно. Известны потребности в механизмах каждого участка: 90, 61 и 45 штук, а также производительность каждого типа механизма на каждом участке работ (в единицах работы/единицу времени).

Исходные данные задачи представлены в нижеследующей таблице.

Тип механизма	Производительность на участке			Парк механизмов	Спрос участка
	A	B	C
Механизм 1	3	5	3	74	Уч-ка A 90
Механизм 2	7	3	7	53	Уч-ка B 61
Механизм 3	6	3	5	45	Уч-ка C 45
Механизм 4	8	5	5	24

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

Решение

Задача о распределении механизмов между участками работ по своему характеру не имеет ничего общего с транспортировкой груза, однако ее можно представить как задачу транспортного типа.

Пусть x_ij – количество механизмов i-го вида, распределенное на j-й участок работы. Известны величины c_ij – производительность i-го механизма при работе на j-м участке.

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

В задаче о распределении механизмов по участкам работ ставится цель: максимизировать суммарную производительность всех механизмов, работающих на участках. Сама целевая функция S имеет вид:

S = 3x₁₁ + 5x₁₂ + 3x₁₃ + 7x₂₁ + 3x₂₂ + 7x₂₃ + 6x₃₁ + 3x₃₂ + 5x₃₃ + 8x₄₁ + 5x₄₂ + 5x₄₃.

В транспортной задаче целевая функция минимизируется. Поэтому, чтобы решить рассматриваемую задачу как транспортную, нужно умножить все значения коэффициентов функции S (производительностей механизмов) на -1. Целевая функция примет вид:

P = -S = -3x₁₁ – 5x₁₂ – 3x₁₃ – 7x₂₁ – 3x₂₂ – 7x₂₃ – 6x₃₁ – 3x₃₂ – 5x₃₃ – 8x₄₁ – 5x₄₂ – 5x₄₃

и нужно будет найти ее минимум.

Проверим, является ли рассматриваемой задача закрытой. Для этого вычислим общее количество механизмов:  = 196 и потребности всех участков работ в механизмах: =196. Так как = , то задача является закрытой.

Экономико-математическая модель задачи имеет вид:

x₁₁ + x₁₂ + x₁₃ = 74, (2.1)

x₂₁ + x₂₂ + x₂₃ = 53, (2.2)

x₃₁ + x₃₂ + x₃₃ = 45, (2.3)

x₄₁ + x₄₂ + x₄₃ = 24, (2.4)

x₁₁ + x₂₁ + x₃₁ + x₄₁ = 90, (2.5) x₁₂ + x₂₂ + x₃₂ + x₄₂ = 61, (2.6)

x₁₃ + x₂₃ + x₃₃ + x₄₃ = 45, (2.7)

x_ij 0, i = ; j = , (2.8)

P = –3x₁₁ – 5x₁₂ – 3x₁₃ – 7x₂₁ – 3x₂₂ – 7x₂₃ – 6x₃₁ – 3x₃₂ – – 5x₃₃ – 8x₄₁ – 5x₄₂ – 5x₄₃ min. (2.9)

Таким образом, задача (2.1) – (2.9) представляет собой задачу транспортного типа и в дальнейшем используется терминология транспортной задачи.

2.1. Для нахождения начального опорного плана используем метод минимального элемента. Кратко опишем схему этого метода.

В транспортной таблице находится клетка с минимальным тарифом. Если таких клеток несколько, то берется любая из них. Пусть это клетка (i, j). Тогда сравниваются запасы поставщика a_i и потребность потребителя b_j. В качестве перевозки берется величина x_ij = min{a_i, b_j}. Если a_i < b_j, то закрывается строка i; если же a_i > b_j, то закрывается столбец j. Если a_i = b_j, то закрываются одновременно и строка, и столбец, а в одну из клеток, расположенных в этой строке или столбце, заносится 0 (нулевая перевозка). Затем среди оставшихся клеток таблицы выбирается клетка с наименьшим тарифом, и в нее записывается максимально возможная перевозка. Процесс продолжается до тех пор, пока не будет получен опорный план перевозок, возможно, вырожденный.

Применим этот метод к транспортной таблице решаемой задачи (см. табл. 2.0). Ищем минимальный элемент (наименьший транспортный тариф): c₄₁ = – 8. В клетку (4, 1): помещаем перевозку x₄₁ = min{a₁, b₁} = min{24, 90} = 24. Четвертая строка закрывается, так как запас четвертого поставщика исчерпан.

В оставшейся части таблицы снова находим минимальный элемент: c₂₁ = –7. Определим поставку, которую нужно занести в клетку (2,1). Предложение второго поставщика a₂ = 53 единицы, а спрос первого потребителя b₁ частично уже удовлетворен предыдущей поставкой x₄₁. Он теперь равен b₁′ = b₁ – x₄₁ = 90 – 24 = 66 единиц. Отсюда x₂₁ = min{a₂, b₁′} = min{53, 66} = 53. Вторая строка закрывается, так как исчерпан запас второго поставщика.

Находим в оставшейся части таблицы наименьший элемент: c₃₁ = –6. Определим поставку, которую нужно занести в клетку (3, 1). Запас третьего поставщика a₃ = 45 единиц, а спрос b₁′ у первого потребителя уменьшился на величину предыдущей поставки x₂₁ и стал равен b ₁′′ = b₁′ – х₂₁ = 66 – 53 = 13 единиц. Отсюда, х₃₁ = min{45, 13} = 13. Первый столбец закрывается, так как спрос первого потребителя полностью удовлетворён.

Среди оставшихся тарифов наименьшим будет с₃₃ = –5. Определим поставку, которую нужно занести в клетку (3, 3). У третьего поставщика неиспользованный запас составляет a₃ – х₃₁ = 45 – 13 = 32 единицы. У третьего потребителя объём потребности b₃ = 45, значит х₃₃ = min {32, 45} = 32 единицы. Этой поставкой полностью исчерпано предложение третьего поставщика, поэтому третья строка закрывается.

Среди оставшихся клеток выбираем минимальный элемент: с₁₂ = –5. Следовательно, в клетку (1, 2) отправляется поставка х₁₂ = min{a₁, b₂} = min{74, 61} = 61. Второй столбец закрывается, поскольку спрос второго потребителя полностью удовлетворён этой поставкой.

Среди оставшихся клеток выбираем минимальный элемент с₁₃ = –3 и определяем величину поставки в клетку (1, 3): х₁₃ = min{a₁′, b₃′}. Так как предложение первого поставщика a₁ = 74 уменьшилось на величину предыдущей поставки х₁₂ = 61, то оставшийся запас a₁′ = a₁ – х₁₂ = 74 – 61 = 13. В то же время спрос третьего потребителя b₃ = 45 уменьшился за счёт поставки х₃₃ = 32 и составляет на данный момент величину b₃′ = b₃ – х₃₃ = 45 – 32 = 13. Таким образом, х₁₃ = min{13, 13} = 13.

Полученный опорный план Х₀ содержит 6 занятых клеток с положительными поставками и, следовательно, является невырожденным (m + n – 1 = 4 + 3 – 1 = 6).

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

Таблица 2.0

bj ai	90	61	45	Ui
74	-3	-5 61	-3 13	0
53	- 7 – 53	-3	-7 +	3
45	-6 13 +	-3	-5 32 –	2
24	-8 24	-5	-5	4
Vj	-4	-5	-3	P0 = -1145

Получен первоначальный опорный план Х₀ методом минимального элемента, для которого значение целевой функции P₀ = –1145.

– 61 13

Х₀ = 53 – – , Р₀ = –1145.

13 – 32

24 – –

2.2. Дальнейшее решение продолжим методом потенциалов.

Шаг 1. Используем условие (6) критерия оптимальности плана транспортной задачи (см. стр. 6) для задачи (2.1) – (2.9). Пусть U₁ = 0. Тогда

V₂ = U₁ + C₁₂ = 0 – 5 = –5,

V₃ = U₁ + C₁₃ = 0 – 3 = –3,

U₃ = V₃ – C₃₃ = –3 – (–5) = 2,

V₁ = U₃ + C₃₁ = 2 – 6 = –4,

U₂ = V₁ – C₂₂ = – 4 – (–7) = 3,

U₄ = V₁ – C₄₁ = – 4 – (–8) = 4.

Далее рассчитываются значения ∆_ij = V_j – U_i – C_j для всех свободных клеток по условию (7) критерия оптимальности:

∆₁₁ = –4 + 3 = –1,

∆₂₂ = –5 – 3 + 3 = –5,

∆₂₃ = –3 – 3 + 7 = 1,

∆₃₂ = –5 – 2 + 3 = –4,

∆₄₂ = –5 – 4 + 5 = –4,

∆₄₃ = –3 – 4 + 5 = –2.

Анализ значений ∆_ij показывает, что условие оптимальности для плана Х₀ не выполнено, т.к. имеется значение ∆₂₃ = +1. Необходима корректировка плана.

Составляем цикл, включающий клетки: (2, 3), (3, 3), (3, 1), (2, 1). Среди значений, стоящих в минусовых клетках, выбирается минимальное. Это и будет корректирующая величина θ = 32. Свободная клетка (2, 3) заполняется значением 32, а клетка (3, 3) освобождается. В соответствии со знаком клетки меняются значения в клетках цикла: в клетку (3,1) заносится число 45 (13 + θ = 13 + 32 = 45), а в клетку (2,1) — число 21 (53 – θ = 53 – 32 = 21).

Таким образом, начальный план скорректирован и получен новый опорный план Х₁ со значением целевой функции Р₁ = Р₀ – ∆₂₃ θ = –1145 – 1 × 32 = –1177. Этот план представлен в таблице 2.1.

– 61 13

Х₁ = 21 – 32 , Р₁ = –1177.

45 – –

24 – –

Шаг 2. Опорный план X₁ проверяется на оптимальность. Рассчитаем для него значения потенциалов строк U_i и столбцов V_j. Определим значение ∆_ij для всех свободных клеток:

∆₁₁ = –3 + 3 = 0,

∆₂₂ = –5 – 4 + 3 = –6,

∆₃₂ = –5 – 3 + 3 = –5,

∆₃₃ = –3 – 3 + 5 = –1,

∆₄₂ = –5 – 5 + 5 = –5,

∆₄₃ = –3 – 5 + 5 = –3.

Таблица 2.1

bj ai	90	61	45	Ui
74	-3	-5 61	-3 13	0
53	-7 21	-3	-7 32	4
45	-6 45	-3	-5	3
24	-8 24	-5	-5	5
Vj	-3	-5	-3	P1 = -1177

План, представленный в таблице 2.1, оптимален, т.к. выполнено условие (2) оптимальности плана транспортной задачи: все ∆_ij ≤ 0; значит, получено окончательное решение задачи. Умножив значение P₁ на –1, получим максимальное значение целевой функции.

Наличие ∆₁₁ = 0 говорит о том, что при заданных исходных данных в этой задаче существует ещё одно оптимальное распределение механизмов по участкам работ с тем же значением целевой функции.

О твет:

– 61 13

Х ^* = 21 – 32 , Р^* = 1177.

45 – –

24 – –

Экономическая интерпретация оптимального решения задачи распределения механизмов между участками работ

Для получения максимальной производительности всех механизмов на всех участках работ в размере 1177 (единиц работы/единицу времени) необходимо распределить их следующим образом:

• механизм 1 — на участок В (61 единицы) и участок С (13 единиц);

• механизм 2 — на участок А (21 единицы) и участок С (32 единицы);

• механизм 3 — на участок А (45 единиц);

• механизм 4 — на участок А (24 единиц).