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

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. Результаты расчета представлены в табл.

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

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

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

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

Решение задачи с использованием системы Mathcad

Введем сначала поясняющий текст в рабочем листе. Для этого разместим курсор (визир – красный крестик) в месте ввода текста. Затем выберем (щелчком мыши или с помощью клавиатуры) пункт Insert (Вставка) главного меню Mathcad. В появившемся падающем меню щелкнем по пункту Text Region (Текстовая область) или в месте расположения курсора нажмем клавишу с двойной кавычкой (команда для ввода текста). В обоих случаях появится шаблон, указывающий место и начало ввода текста, после чего можно приступить к этой операции. Текстовая область будет автоматически увеличиваться по мере ввода текста. По окончании этого действия выведем курсор за рамки текстовой области.

Далее введем критерий оптимизации – целевую функцию. Для этого разместим курсор (визир – красный крестик) в месте ввода математического выражения, затем, используя соответствующие клавиши, начнем ввод, в первую очередь – имени критерия оптимизации с аргументами в скобках через запятые. Затем нажмем комбинацию Shift+: (двоеточие) для ввода знака присваивания:= (двоеточие и знак ``равно''). На месте правой метки помещаем все выражение критерия оптимизации. Аналогично вводятся начальные приближения.

Для решения задачи используем блок функций Given…Maximize. Для этого необходимо:

• ввести, если требуется, комментарии, ввод которых начинается с нажатия клавиши с двойной кавычкой;

• ввести ключевое слово Given;

• ввести систему ограничений с использованием жирного знака равенства, нажав комбинацию клавиш Ctrl+=;

• ввести граничные значения;

• ввести вектор-столбец искомых параметров, используя диалоговое окно Insert Matrix (Вставить матрицу) и комбинацию Ctrl+M. В диалоговом окне число строк (Rows) – элементов вектора столбца – должно быть равно 7, а число столбцов (Columns) – 1;

• ввести знак присваивания, нажав комбинацию клавиш Shift+: (двоеточие);

• ввести функцию Maximize с искомыми параметрами, используя диалоговое окно Insert Function (Вставить функцию) и комбинацию Ctrl+E;

• ввести вектор-столбец искомых параметров и знак ``равно''.

На рис. 1 показан процесс оптимизации распределения неоднородных ресурсов с помощью Mathcad.

Решение задачи А с помощью Mathcad

Оптимальное распределение неоднородных ресурсов зафиксировано в векторе . Из полученного решения видно, что , , , , , . Это означает, что изделия ,  и  предприятие изготавливать не должно. Ему нужно производить только второе изделие в количестве 3 единиц. Цифра в переменной  определяет изделие, планируемое для изготовления. Оптимальное распределение ресурсов обеспечит получение максимальной прибыли , которая составит 150 единиц.

В качестве еще одного примера решим в системе Mathcad следующую задачу линейного программирования:

Приведем ее к каноническому виду:

(6)

Очевидно, что в качестве начального приблежения необходимо взять  Решение задачи приведено на рисунке 2.

Решение задачи (6) с помощью Mathcad pic2

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

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

Решение задачи не имеющей максимума pic3

К сожалению Mathcad некорректно решает задачи в которых оптимальное решение неединственно. В этом случае решением служит одна из точек в которых достигается максимум (минимум). Так например при решении задачи (6) симплекс-методом, то получим, что . В обоих случаях . Лучше всего это прослеживается при решении следующей задачи:

(7)

Очевидно, что , а

Задавая начальные приближения в соответствии с формулой приведенной выше, Mathcad будет выдавать в качестве ответа начальные приближения.

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

Заключение

Как было показано выше система символьной математики идеально подходит для решения задач исследования операций и в частности задач оптимального распределения неоднородных ресурсов. Mathcad в считаные секунды находит решение подобных задач, даже в случае порядка ста или двухсот переменных.

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

Mathcad не требует от пользователя знание каких-то определенных методов решения поставленных задач, пользователь должен только уметь составить математическую модель, а все остальное сделает Mathcad. Но поскольку Mathcad – это всего лишь программа пользователь должен понимать, что при решении может возникнуть ошибки, могут быть получены далеко не все решения и, самое главное, Mathcad не интерпретирует полученные результаты, а только решает.

Литература

1. Венцель Е.С., Исследование операций, – М., 1980

2. Давыдов Э.Г., Исследование операций, – М., 1990

3. Вагнер Г., Основы исследования операций в 2-х т.

4. Кудрявцев Е.М., Mathcad 8, – М.: ДМК, 2000

5. Гермейер Ю.Б., Введение в теорию ИСО