Задача 14

На предприятии для производства двух видов продукции используется 2 вида ресурсов. Расход каждого вида ресурса на изготовление единицы каждого вида продукции, запасы каждого вида ресурсов, а также доходы от реализации единицы каждого вида продукции приведены в таблице.

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

Таблица – Исходная информация задачи

Вид ресурса	Необходимое количество условных единиц ресурсов на единицу продукции			Запас ресурса
	2	1	8
	1	2	10
Доход от реализации единицы продукции	1	1

РЕШЕНИЕ:

Переменные:

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

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

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

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

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

x₁₁ + x₁₂ ≤ 8 (для 1 базы)

x₂₁ + x₂₂ ≤ 10 (для 2 базы)

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

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

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

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

2x₁₁ + 1x₁₂ + 1x₂₁ + 2x₂₂ → max

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

	1	2	Запасы
1	2	1	8
2	1	2	10
Потребности	1	1

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

∑a = 8 + 10 = 18

∑b = 1 + 1 = 2

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

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

	1	2	3	Запасы
1	2	1	0	8
2	1	2	0	10
Потребности	1	1	16

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

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

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

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

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

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

x₂₂ = min(10,1) = 1.

2	x	0	8
1	2	0	10 - 1 = 9
1	1 - 1 = 0	16

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

x₁₁ = min(8,1) = 1.

2	x	0	8 - 1 = 7
x	2	0	9
1 - 1 = 0	0	16

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

x₂₃ = min(9,16) = 9.

2	x	0	7
x	2	0	9 - 9 = 0
0	0	16 - 9 = 7

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

x₁₃ = min(7,7) = 7.

2	x	0	7 - 7 = 0
x	2	0	0
0	0	7 - 7 = 0

	1	2	3	Запасы
1	2[1]	1	0[7]	8
2	1	2[1]	0[9]	10
Потребности	1	1	16

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

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

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

F(x) = 2*1 + 0*7 + 2*1 + 0*9 = 4

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

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

u₁ + v₁ = 2; 0 + v₁ = 2; v₁ = 2

u₁ + v₃ = 0; 0 + v₃ = 0; v₃ = 0

u₂ + v₃ = 0; 0 + u₂ = 0; u₂ = 0

u₂ + v₂ = 2; 0 + v₂ = 2; v₂ = 2

	v1=2	v2=2	v3=0
u1=0	2[1]	1	0[7]
u2=0	1	2[1]	0[9]

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

Максимальная прибыль составит: F(x) = 2*1 + 0*7 + 2*1 + 0*9 = 4

Ответ:

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

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

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

На 1-ом складе остался невостребованным груз в количестве 7 ед.

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

На 2-ом складе остался невостребованным груз в количестве 9 ед.

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