Задача 11

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

Ресурс	Вид продукции					Объем ресурса
Трудовой	1	1	1	1	16
Сырье	6	5	4	3	110
Оборудование	4	6	10	13	100
Прибыль	60	70	120	130

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

РЕШЕНИЕ:

Переменные:

x₁₁ – количество груза из 1-го склада к 1-у потребителю.

x₁₂ – количество груза из 1-го склада к 2-у потребителю.

x₁₃ – количество груза из 1-го склада к 3-у потребителю.

x₁₄ – количество груза из 1-го склада к 4-у потребителю.

x₂₁ – количество груза из 2-го склада к 1-у потребителю.

x₂₂ – количество груза из 2-го склада к 2-у потребителю.

x₂₃ – количество груза из 2-го склада к 3-у потребителю.

x₂₄ – количество груза из 2-го склада к 4-у потребителю.

x₃₁ – количество груза из 3-го склада к 1-у потребителю.

x₃₂ – количество груза из 3-го склада к 2-у потребителю.

x₃₃ – количество груза из 3-го склада к 3-у потребителю.

x₃₄ – количество груза из 3-го склада к 4-у потребителю.

Ограничения по запасам:

x₁₁ + x₁₂ + x₁₃ + x₁₄ ≤ 16 (для 1 базы)

x₂₁ + x₂₂ + x₂₃ + x₂₄ ≤ 110 (для 2 базы)

x₃₁ + x₃₂ + x₃₃ + x₃₄ ≤ 100 (для 3 базы)

Ограничения по потребностям:

x₁₁ + x₂₁ + x₃₁ = 60 (для 1-го потребителя.)

x₁₂ + x₂₂ + x₃₂ = 70 (для 2-го потребителя.)

x₁₃ + x₂₃ + x₃₃ = 120 (для 3-го потребителя.)

x₁₄ + x₂₄ + x₃₄ = 130 (для 4-го потребителя.)

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

1x₁₁ + 1x₁₂ + 1x₁₃ + 1x₁₄ + 6x₂₁ + 5x₂₂ + 4x₂₃ + 3x₂₄ + 4x₃₁ + 6x₃₂ + 10x₃₃ + 13x₃₄ → max

Стоимость доставки единицы груза из каждого пункта отправления в соответствующие пункты назначения задана матрицей тарифов

	1	2	3	4	Запасы
1	1	1	1	1	16
2	6	5	4	3	110
3	4	6	10	13	100
Потребности	60	70	120	130

Проверим необходимое и достаточное условие разрешимости задачи.

∑a = 16 + 110 + 100 = 226

∑b = 60 + 70 + 120 + 130 = 380

Как видно, суммарная потребность груза в пунктах назначения превышает запасы груза на базах. Следовательно, модель исходной транспортной задачи является открытой. Чтобы получить закрытую модель, введем дополнительную (фиктивную) базу с запасом груза, равным 154 (226—380). Тарифы перевозки единицы груза из базы ко всем потребителям полагаем равны нулю.

Занесем исходные данные в распределительную таблицу.

	1	2	3	4	Запасы
1	1	1	1	1	16
2	6	5	4	3	110
3	4	6	10	13	100
4	0	0	0	0	154
Потребности	60	70	120	130

Этап I. Поиск первого опорного плана.

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

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

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

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

Искомый элемент равен c₃₄=13. Для этого элемента запасы равны 100, потребности 130. Поскольку минимальным является 100, то вычитаем его.

x₃₄ = min(100,130) = 100.

1	1	1	1	16
6	5	4	3	110
x	x	x	13	100 - 100 = 0
0	0	0	0	154
60	70	120	130 - 100 = 30

Искомый элемент равен c₂₁=6. Для этого элемента запасы равны 110, потребности 60. Поскольку минимальным является 60, то вычитаем его.

x₂₁ = min(110,60) = 60.

x	1	1	1	16
6	5	4	3	110 - 60 = 50
x	x	x	13	0
x	0	0	0	154
60 - 60 = 0	70	120	30

Искомый элемент равен c₂₂=5. Для этого элемента запасы равны 50, потребности 70. Поскольку минимальным является 50, то вычитаем его.

x₂₂ = min(50,70) = 50.

x	1	1	1	16
6	5	x	x	50 - 50 = 0
x	x	x	13	0
x	0	0	0	154
0	70 - 50 = 20	120	30

Искомый элемент равен c₁₄=1. Для этого элемента запасы равны 16, потребности 30. Поскольку минимальным является 16, то вычитаем его.

x₁₄ = min(16,30) = 16.

x	x	x	1	16 - 16 = 0
6	5	x	x	0
x	x	x	13	0
x	0	0	0	154
0	20	120	30 - 16 = 14

Искомый элемент равен c₄₄=0. Для этого элемента запасы равны 154, потребности 14. Поскольку минимальным является 14, то вычитаем его.

x₄₄ = min(154,14) = 14.

x	x	x	1	0
6	5	x	x	0
x	x	x	13	0
x	0	0	0	154 - 14 = 140
0	20	120	14 - 14 = 0

Искомый элемент равен c₄₃=0. Для этого элемента запасы равны 140, потребности 120. Поскольку минимальным является 120, то вычитаем его.

x₄₃ = min(140,120) = 120.

x	x	x	1	0
6	5	x	x	0
x	x	x	13	0
x	0	0	0	140 - 120 = 20
0	20	120 - 120 = 0	0

Искомый элемент равен c₄₂=0. Для этого элемента запасы равны 20, потребности 20. Поскольку минимальным является 20, то вычитаем его.

x₄₂ = min(20,20) = 20.

x	x	x	1	0
6	5	x	x	0
x	x	x	13	0
x	0	0	0	20 - 20 = 0
0	20 - 20 = 0	0	0

	1	2	3	4	Запасы
1	1	1	1	1[16]	16
2	6[60]	5[50]	4	3	110
3	4	6	10	13[100]	100
4	0	0[20]	0[120]	0[14]	154
Потребности	60	70	120	130

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

2. Подсчитаем число занятых клеток таблицы, их 7, а должно быть m + n - 1 = 7. Следовательно, опорный план является невырожденным.

Значение целевой функции для этого опорного плана равно:

F(x) = 1*16 + 6*60 + 5*50 + 13*100 + 0*20 + 0*120 + 0*14 = 1926

Этап II. Улучшение опорного плана.

Проверим оптимальность опорного плана. Найдем предварительные потенциалы u_i, v_j. по занятым клеткам таблицы, в которых u_i + v_j = c_ij, полагая, что u₁ = 0.

u₁ + v₄ = 1; 0 + v₄ = 1; v₄ = 1

u₃ + v₄ = 13; 1 + u₃ = 13; u₃ = 12

u₄ + v₄ = 0; 1 + u₄ = 0; u₄ = -1

u₄ + v₂ = 0; -1 + v₂ = 0; v₂ = 1

u₂ + v₂ = 5; 1 + u₂ = 5; u₂ = 4

u₂ + v₁ = 6; 4 + v₁ = 6; v₁ = 2

u₄ + v₃ = 0; -1 + v₃ = 0; v₃ = 1

	v1=2	v2=1	v3=1	v4=1
u1=0	1	1	1	1[16]
u2=4	6[60]	5[50]	4	3
u3=12	4	6	10	13[100]
u4=-1	0	0[20]	0[120]	0[14]

Опорный план является оптимальным, так все оценки свободных клеток удовлетворяют условию u_i + v_j ≤ c_ij.

Максимальная прибыль составит: F(x) = 1*16 + 6*60 + 5*50 + 13*100 + 0*20 + 0*120 + 0*14 = 1926

Ответ:

Анализ оптимального плана.

Из 1-го склада необходимо весь груз направить к 4-у потребителю.

Из 2-го склада необходимо груз направить к 1-у потребителю (60), к 2-у потребителю (50)

Из 3-го склада необходимо весь груз направить к 4-у потребителю.

Потребность 2-го потребителя остается неудовлетворенной на 20 ед.

Оптимальный план является вырожденным, так как базисная переменная x₄₂=0.

Потребность 3-го потребителя остается неудовлетворенной на 120 ед.

Оптимальный план является вырожденным, так как базисная переменная x₄₃=0.

Потребность 4-го потребителя остается неудовлетворенной на 14 ед.

Оптимальный план является вырожденным, так как базисная переменная x₄₄=0.