Оптимальное распределение неоднородных ресурсов (стр. 2 из 4)

Граничные условия будут записаны следующим образом:

(4)

Совокупность системы ограничений (2), целевой функции (3) и граничных условий (4) образует математическую модель для нашей задачи.

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

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

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

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

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

(5)

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

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

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

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

Симплекс-таблица

Базисные переменные	Свободные члены	Коэффициенты при базисных и небазисных переменных
	15	3		2	7	1	0	0
	9	4	3	3	5	0	1	0
	30	5	6	4	8	0	0	1
	0	40	50	30	20	0	0	0

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

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

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

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

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

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

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

.

5. Представление новой базисной переменной через небазисные. Строится новая симплекс-таблица. Отмечается звездочкой строка и столбец в предыдущей симплекс-таблице, соответственно для выводимой из базиса и для вводимой в него переменной. Коэффициент, находящийся на пересечении строки и столбца, отмеченных звездочками, называется разрешающим и помечается звездочкой. Все коэффициенты строки, отмеченной звездочкой, делятся на разрешающий элемент, а результаты расчета заносятся в новую симплекс-таблицу. В нашей задаче на первой итерации разрешающий элемент равен 5. Результаты деления каждого элемента строки, отмеченной звездочкой, на разрешающий коэффициент заносятся в строку 1 новой таблицы.

6. Представление остальных базисных переменных и целевой функции через новый набор небазисных переменных. Для этого коэффициенты в новой таблице при новой базисной переменной умножаются на такое число, чтобы после сложения с преобразуемой строкой предыдущей таблицы в столбце при новой базисной переменной в новой таблице появился ноль. Результаты сложения заносятся в новую симплекс-таблицу. Исходя из этого, для получения коэффициентов второй строки в новой табл. умножаем коэффициенты при новой базисной переменной

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

Вторая итерация симплекс-метода

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

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

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