Задача об использовании сырья

Пример

Задача об использовании сырья

Для производства четырех видов изделий A₁, A₂, A₃, A₄ завод должен использовать три вида сырья I, II, III, запасы которого на планируемый период составляют соответственно 1000, 600 и 150 условных единиц. В приведенной ниже таблице даны технологические коэффициенты, т.е. расход каждого вида сырья на производство единицы каждого изделия и прибыль от реализации единицы изделия каждого вида.

 

Виды сырья	Запасы сырья	Технологические коэффициенты
		A1	A2	A3	A4
I
II
III
Прибыль от реализации				2,5

 

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

Составим математическую модель задачи

Обозначим через x₁, x₂, x₃, x₄ количество единиц соответствующих изделий: A₁, A₂, A₃, A₄. Тогда экономико-математическая модель задачи будет следующая: найти максимум функции

при выполнении системы ограничений

Для обращения системы ограничений-неравенств в систему уравнений прибавим к левой части каждого неравенства добавочные неотрицательные переменные x₅, x₆, x₇. Эти добавочные переменные в условиях данной задачи имеют конкретное экономическое содержание, а именно: объем остатков сырья каждого вида после выполнения плана выпуска продукции.

После введения добавочных переменных получим систему уравнений: Нужно найти такое допустимое базисное решение системы, которое бы максимизировало целевую функцию F, т.е. необходимо найти оптимальное решение задачи. Так как система ограничений состоит из трех независимых уравнений с семью переменными, то число основных (базисных) переменных должно равняться трем, а число неосновных — четырем.
Для решения задачи симплексным методом, прежде всего, нужно найти любое базисное решение. В условиях данной задачи оно может быть найдено без труда. Для этого достаточно принять за основные добавочные переменные x₅, x₆, x₇. Так как коэффициенты при этих переменных образуют единичную матрицу, то отпадает необходимость вычислять определитель (определитель единичной матрицы равен 1, т.е. отличен от нуля).
Положив неосновные (свободные) переменные x₁, x₂, x₃, x₄ равными нулю, получим базисное решение (0; 0; 0; 0; 1000; 600; 150), которое оказалось допустимым. Поэтому в условиях данной задачи отпадает надобность в применении первого этапа симплексного метода. Переходим сразу ко второму этапу, т.е. к поискам оптимального решения.

I шаг. Основные переменные x₅, x₆, x₇. Составляем первую симплекс-таблицу. Находим разрешающий элемент.

 

Базисные переменные	Свобод. члены	x5	x6	x7	x1	x2	x3	x4
x5
x6
x7
F					-6	-2	-2,5	-4

 

Базисное решение (0; 0; 0; 0; 1000; 600; 150).

II шаг. Основные переменные x₁,x₅, x₆. Составляем новую симплекс-таблицу. Снова находим разрешающий элемент.

 

Базисные переменные	Свобод. члены	x5	x6	x7	x1	x2	x3	x4
x5				-5			-10	-3
x6				-4			-6	-3
x1
F						-2	9,5

 

Базисное решение (150; 0; 0; 0; 250; 0; 0).

III шаг. Основные переменные x₁, x₂, x₅. Составляем новую симплекс-таблицу. Находим разрешающий элемент.

 

Базисные переменные	Свобод. члены	x5	x6	x7	x1	x2	x3	x4
x5			-0,5	-3			-7	-1,5
x2			0,5	-2			-3	-1,5
x1
F							3,5	-1

Базисное решение (150; 0; 0; 0; 250; 0; 0).

IV шаг. Основные переменные х2, х4, х5. Переходим к следующей таблице.

Базисные переменные	Свобод. члены	x5	x6	x7	x1	x2	x3	x4
x5			-0,5	-1,5	1,5		-4
x2			0,5	-0,5	1,5
x4
F							5,5

Эта таблица является последней, по ней читаем ответ задачи. Оптимальным будет решение (0; 225; 0; 150; 475; 0; 0) при котором F_max =1050, т.е. для получения наибольшей прибыли, равной 1050 денежных единиц, предприятие должно выпустить 225 единиц продукции вида A₂, 150 единиц продукции вида A₄, (продукцию вида A₁ и A₃ в данных условиях производить не выгодно) при этом сырье типа II и III будет использовано полностью, а 475 единиц сырья типа I останутся неизрасходованными.

 

http://matmetod-popova.narod.ru/theme24.htm