Решение задачи традиционными методами

 

Алгоритм решения. Для решения данной задачи разработано много способов. Рассмотрим один из наиболее распространенных - симплекс-метод Для его использования необходимо определить начальный базис, то есть решение, удовлетворяющее системе равенств (3.3.2.2). В некоторых задачах базис просматривается непосредственно, но во многих его необходимо найти.

В данной задаче базис определить легко. Для этого требуется взять m неизвестных - по числу уравнений в системе (3.3.2.2). В нашей системе уравнений (т = 3) это х₅, х₆, х₇, которые и выражаем через оставшиеся неизвестные х., х₂, х₃, х₄.

Систему уравнений необходимо записать в следующем виде:

x₅=15-(3х₁ + 5х₂+2х₃ + 7х₄)

x₆=9 - (4х₁ + 3х₂+3х₃ + 5х₄) (3.3.2.5)

х₇ = 30 - (5x_t +6x₂ + 4x₃ + 8х₄)

Переменные, находящиеся в левой части системы, называются базисными (основными), а находящиеся справа - небазисными (неосновными). Для определения значений базисных переменных х₅, х₆, х₇ необходимо приравнять к нулю небазисные

x_1, х₂, х₃, x₄ и подставить их в систему уравнений (3.3.2.5). Полученное таким образом решение является базисным. В нашей задаче оно будет выглядеть следующим образом:

(Х₁, Х₂, Х₃, Х₄, Х₅, Х₆, Х₇)

(0, 0, 0, 0, 15, 9, 30)

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

1. Заполнение исходной симплекс-таблицы. В соответствии с полученной системой уравнений и критерием оптимизации заполним исходную симплекс-таблицу (табл. 3.3.2.3).

2. Проверка базисного решения на оптимальность. Просматриваются знаки коэффициентов при небазисных переменных в целевой функции (критерий оптимизации) - последняя строка табл. 3.3.2.3.

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

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

4. Выбор из небазисных переменных той, которая способна при введении ее в базис увеличить значение целевой функции. Наиболее простой и чаще всего используемый способ состоит в выборе той небазисной переменной, которой соответствует наибольший положительный коэффициент в целевой функции. В нашей задаче это переменная х₂ (наибольший положительный коэффициент равен 50). Значит, х₂ необходимо ввести в базис.

5. Определение базисной переменной, которая должна быть выведена из базиса. Для всех положительных коэффициентов в системе уравнений определяется отношение свободного члена уравнения к коэффициенту при вводимой в базис переменной. Для нашей задачи это будут следующие отношения: 15/5 = 3; 9/3 = 3; 30/6 = 5.

Минимальное из полученных отношений указывает строку и базисную переменную, которая должна быть выведена из базиса. При наличии нескольких одинаковых отношений берется любое. В нашей задаче выведем из базиса переменную х₅.

6. Представление новой базисной переменной через небазисные. Строится новая симплекс-таблица (табл. 3.3.2.4). Отмечается звездочкой строка и столбец в предыдущей симплекс-таблице (табл. 3.3.2.3) для выводимой из базиса и для вводимой в него переменной.

Коэффициент, находящийся на пересечении строки и столбца, отмеченных звездочками, называется разрешающим и также помечается звездочкой (табл. 3.3.2.3). Все коэффициенты строки со звездочкой делятся на разрешающий

 

Таблица 3.3.2.3

Базисные переменные	Свободные члены	Коэффициенты при базисных и небазисных переменнвх
XJ	°i	X]	х|	Х3	*4	Х5	Хб	х?
V* Х5			ri*l i_ — _j
Хб
X?
П.

 

 

Таблица 3.3.2.4

Базисные переменные	Сбободние члены	Коэффициенты при базисных и небаэисных переменных
х,	а,	X)	Х2	*3	Х4	*5	Хб	*7
Х2		3/5		2/5	7/5	1/5
Хб		11/5		9/5	4/5	-3/5
Х7		7/5		8/5	-2/5	-6/5
п.	-150				-50	-10

 

элемент, а результаты расчета заносятся в новую симплекс-таблицу. В нашей задаче на первой итерации разрешающий элемент равен 5 (табл. 3.3.2.3). Результаты деления каждого элемента строки, отмеченной звездочкой, на разрешающий коэффициент заносятся в строку 1 новой таблицы (табл. 3.3.2.4). 7. Представление остальных базисных переменных и целевой функции через новый набор небазисных переменных. Для этого коэффициенты в последней таблице при новой базисной переменной умножаются на такое число, чтобы после сложения с преобразуемой строкой предыдущей таблицы в столбце новой таблицы при базисной переменной появился ноль. Результаты сложения заносятся в новую симплекс-таблицу. Исходя из этого, для получения коэффициентов второй строки в новой таблице (табл. 3.3.2.4) умножаем коэффициенты при новой базисной переменной х₂ на число -3, складываем с соответствующими коэффициентами второй строки предыдущей симплекс-таблицы (табл. 3.3.2.3) и результаты расчета заносим во вторую строку новой таблицы (табл. 3.3.2.4).

Аналогичные преобразования проводим и для других строк. После этого выполняем новую итерацию. Цикл расчета начинается с этапа 2 и повторяется до нахождения оптимального решения.

Поскольку в последней строке табл. 3.3.2.4 не все коэффициенты целевой функции при небазисных переменных положительны, то решение неоптимально; следовательно, выполняется следующий итерационный цикл расчета и строится новая симплекс-таблица (табл. 3.3.2.5). В качестве вводимой в базис небазисной переменной принимаем х_а (или х,), имеющую наибольший положительный коэффициент. Отмечаем звездочкой столбец х₃. В качестве выводимой из базис переменной берем х₆, так как для нее частное от деления свободного члена на соответствующий положительный коэффициент минимально. Разрешающий множитель равен 9/5. Результаты расчета представлены в табл. 3.3.2.5

 

Таблица 3.3.2.5

Базисные переменные	Свободные члены	Коэффициенты при базисных и небазисных переменных
X,	а,	> П	Х2	*з	Х4	*5	Хб	х?
Х2		1/9			1/9	1/3	-2/9
хз		11/9			4/9	-3/9	5/9
xt		-5/9			-10/9	-2/3	-8/9
П;	-150	-20/9			-490/9	-20/3	-50/9

 

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

(х₁, х₂, х₃, х₄, х₅, х₆, х₇)

(0, 3, 0, 0, 0, 0, 12)

Из полученных результатов следует, что предприятию наиболее выгодно изготовление только изделия И₂, производство которого обеспечит максимальную прибыль в размере Y_max = 150. При этом материальные и трудовые ресурсы будут задействованы полностью, а финансовые - недоиспользованы на 12 единиц.