Задача 15

Предприятие располагает двумя видами сырья S₁ и S₂ в количествах 15 и 13 условных единиц и изготавливает из него изделия двух видов П₁ и П₂. Изготовление единицы изделия П₁ требует расхода сырья S₁ в 1 усл.ед., S₂ в 3 усл.ед., а для производства единицы изделия П₂ необходимо сырья S₁ – 3 усл.ед., сырья S₂ - 1 усл.ед. Известна прибыль от реализации одной единицы продукции каждого вида. Для вида П₁ она составляет 2 ден.ед, для вида П₂ – 3 ден.ед. Требуется найти оптимальный план производства продукции, реализация которого обеспечит предприятию максимальную прибыль.

1) Составим математическую модель исходной задачи.

Представим исходные данные в виде таблицы:

Вид сырья	Нормы расхода сырья на одно изделие		Запасы сырья
	П1	П2
S1	1	3	15
S2	3	1	13
Прибыль от реализации одной единицы продукции, ден.ед.	2	3

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

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

Для решения поставленной задачи введем обозначения:

х₁ – объем производства изделий вида П₁;

х₂ – объем производства изделий вида П₂.

Общую прибыль от реализации изделий можно определить по формуле:

(ден.ед.)

Функция F называется целевой, ее следует максимизировать. Поэтому получаем:

На целевую функцию накладываются следующие ограничения:

а) объем выпуска изделий каждого вида не может быть отрицательным:

x₁ 0, x₂ 0.

б) ограничение по запасам сырья вида S₁:

;

в) ограничение по запасам сырья вида S₂:

.

Математическая модель задачи: составить оптимальную производственную программу (х₁, х₂), обеспечивающую максимальную прибыль от реализации изделий:

при ограничениях:

Математическая модель исходной задачи линейного программирования составлена.

2) Решим исходную задачу симплексным методом.

Приведем задачу к канонической форме.

Чтобы перейти от общей формы записи ЗЛП к канонической, нужно ограничения-неравенства исходной ЗЛП преобразовать в ограничения-равенства добавлением к их левой части дополнительной неотрицательной переменной со знаком «+» в случае неравенства вида «» и со знаком «-» - в случае неравенства вида «».

В первое ограничение системы добавим переменную со знаком «+» и во второе ограничение системы добавим переменную со знаком «+». В результате получаем следующую систему ограничений:

Следовательно, исходная задача может быть записана в канонической форме так: найти максимум функции

при ограничениях:

В полученной системе уравнений системы ограничений имеются две базисные переменные. Решим систему уравнений относительно базисных переменных x₃ и x₄. Запишем базисное решение в стандартной форме:

или

.

Составим симплекс-таблицу:

Базис	Свободный член	x1	x2	x3	x4
x3	15	1	3	1	0
x4	13	3	1	0	1
F(X0)	0	-2	-3	0	0

Переходим к основному алгоритму симплекс-метода.

Итерация 1. Текущий опорный план не является оптимальным, так как в индексной строке находятся отрицательные коэффициенты.

В индексной строке F(х) выбираем максимальный отрицательный элемент. В качестве генерального столбца будет выступать x₂. Вычислим значения D_i по строкам как частное от деления: b_i / a_i2 и из них выберем наименьшее:

.

Таким образом, строка х₃ является генеральной. Разрешающий элемент равен РЭ = 3 и находится на пересечении генерального столбца и генеральной строки.

Формируем следующую часть симплексной таблицы. Вместо переменной x₃ в план 1 войдет переменная x₂.

Строка, соответствующая переменной x₂ в плане 1, получена в результате деления всех элементов строки x₃ плана 0 на разрешающий элемент РЭ=3. На месте разрешающего элемента получаем 1. В остальных клетках столбца x₂ записываем нули. Таким образом, в новом плане 1 заполнены строка x₂ и столбец x₂.

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

Элементы разрешающей строки делим на разрешающий элемент и записываем в соответствующей по номеру строке новой таблицы:

, при i = r.

Все остальные элементы новой таблицы рассчитываем по формулам:

, при i ≠ r

где - элемент новой симплекс-таблицы, a_ij, - элемент предыдущей симплекс-таблицы, a_rk - разрешающий элемент , a_ik - элемент разрешающего столбца, a_rj - элемент разрешающей строки.

Представим расчет каждого элемента в виде таблицы:

Свободный член	x1	x2	x3	x4
15 / 3	1 / 3	3 / 3	1 / 3	0 / 3
13-(15 * 1)/3	3-(1 * 1)/3	1-(3 * 1)/3	0-(1 * 1)/3	1-(0 * 1)/3
0-(15 * (-3))/3	-2-(1 * (-3))/3	-3-(3 * (-3))/3	0-(1 * (-3))/3	0-(0 * (-3))/3

После перерасчета получаем новую таблицу:

Базис	Свободный член	x1	x2	x3	x4
x2	5	0,333	1	0,333	0
x4	8	2,667	0	-0,333	1
F(X1)	15	-1	0	1	0

Итерация 2. Текущий опорный план не является оптимальным, так как в индексной строке находится отрицательный коэффициент.

В качестве генерального столбца будет выступать x₁. Вычислим значения D_i по строкам как частное от деления: b_i / a_i1 и из них выберем наименьшее:

.

Таким образом, строка х₄ является генеральной. Разрешающий элемент равен РЭ = 2,667 и находится на пересечении генерального столбца и генеральной строки.

Формируем следующую часть симплексной таблицы. Вместо переменной x₄ в план 2 войдет переменная x₁.

Строка, соответствующая переменной x₁ в плане 2, получена в результате деления всех элементов строки x₄ плана 1 на разрешающий элемент РЭ=2,667. На месте разрешающего элемента получаем 1. В остальных клетках столбца x₁ записываем нули. Таким образом, в новом плане 2 заполнены строка x₁ и столбец x₁.

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

После перерасчета получаем новую таблицу:

Базис	Свободный член	x1	x2	x3	x4
x2	4	0	1	0,375	-0,125
x1	3	1	0	-0,125	0,375
F(X2)	18	0	0	0,875	0,375

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

Таким образом, получаем:

;

.

Ответ. ; . Для получения максимальной прибыли от реализации продукции на предприятии необходимо производить 3 единицы изделий вида П₁ и 4 единицы изделий вида П₂. При использовании данного плана производства продукции прибыль от реализации продукции будет максимальной и составит 18 ден.ед.