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

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

Таблица 34.2

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

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

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

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

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

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

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

I шаг. Основные переменные x₅, x₆, x₇. Условия нашей задачи выглядят следующим образом:

А целевая функция

Составляем первую симплекс-таблицу.

Так как ищем max, то выбираем наибольший отрицательный коэффициент функции Z. Таким образом, ключевым столбцом является столбец . В этом столбце все базисные коэффициенты положительные, . Таким образом, ключевой строкой может быть или . Для удобства выбираем . Б азисная переменная должна быть переведена в разряд свободных, а свободная переменная вводится в число базисных.

Таблица 34.3

базис	св. члены
Z	0	-6	-2	-2,5	-4
	1000	5	1	0	2
	600	4	2	2	1
	150	1	0	2	1

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

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

Таблица 34.4

базис	св. члены
Z
		1

Умножим каждый элемент ключевой строки из таблицы 34.3 (исключая разрешающий элемент) на 1 и полученные значения запишем в строку с измененной базисной переменной.

Таблица 34.5

базис	св. члены
Z
	150	1	0	2	1

Умножим каждый элемент ключевого столбца из таблицы 34.3 (исключая разрешающий элемент) на (-1)и полученные значения запишем в столбец с измененной свободной переменной.

Таблица 34.6

базис	св. члены
Z		6
		-5
		-4
	150	1	0	2	1

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

Таблица 34.7

базис	св. члены
Z		6	-2
		-5	1
		-4	2
	150	1	0	2	1

Пользуясь схемой прямоугольника, заполняем таблицу.

Таблица 34.8

базис	св. члены
Z		6	-2
		-5	1
		-4	2
	150	1	0	2	1

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

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

Таблица 34.9

базис	св. члены
Z		6	-2
		-5	1
		-4	2
	150	1	0	2	1

 

Б азисная переменная должна быть переведена в разряд свободных, а свободная переменная вводится в число базисных.

III шаг. Основные переменные x₁, x₂, x₅. Составляем новую симплекс-таблицу. Разрешающий элемент 2. Заменяем разрешающий элемент на , . Умножим каждый элемент ключевой строки из таблицы 34.9 (исключая разрешающий элемент) на и полученные значения запишем в строку с измененной базисной переменной. Умножим каждый элемент ключевого столбца из таблицы 34.9 (исключая разрешающий элемент) на и полученные значения запишем в столбец с измененной свободной переменной. С толбец, у которого в ключевой строке имеется 0, в новой таблице будет таким же. С трока, у которой в ключевой строке имеется 0, в новой таблице будет такой же. Пользуясь схемой прямоугольника, заполняем таблицу.

Таблица 34.10

базис	св. члены
Z	900		1
	250		-0,5
	0	-2	0,5	-3	-1,5
	150	1	0	2	1

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

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

Таблица 34.11

базис	св. члены
Z		2	1	3,5	-1
		-3	-0,5	-7	-1,5
		-2	0,5	-3	-1,5
	150	1	0	2	1

Б азисная переменная должна быть переведена в разряд свободных, а свободная переменная вводится в число базисных.

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

Таблица 34.12

базис	св. члены
Z				5,5
		-1,5	-0,5	-4	1,5
		-0,5	0,5		1,5

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

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