Решение задачи. 
Оптимальное использование ресурсов предприятия (на примере Новосибирского электровозоремонтного завода)

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

(b1).

при.

(b2).

(b3).

(b4).

(b5).

Базисными переменными для ограничений (b2) — (b4) служат s1, s2 и s3 соответственно (каждая из них входит в «свое» ограничение с коэффициентом 1 и не входит в другие ограничения).

Составим первую симплекс-таблицу (табл. 4) для задачи (b1) — (b5). В верхней строке все переменные задачи (над ними в скобках для удобства при вычислении z-строки указаны соответствующие коэффициенты ЦФ). В первом столбце таблицы стоят базисные переменные (возле базисных переменных в скобках — соответствующие коэффициенты ЦФ). Нижняя строка рассчитана по формулам (12).

Из таблицы 4 находим первое БДР задачи и соответствующее значение ЦФ:

(x1, x2, x3, s1, s2, s3) = (0, 0, 0, 160, 2200, 34), z = 0.

Решение не оптимально, так как элементы z-строки отрицательны. Выбираем столбец переменной х1 в качестве направляющего (соответствующий элемент z-строки — наибольший по модулю отрицательный элемент). Вычисляем отношения элементов столбца «Решение» к соответствующим элементам направляющего столбца, результат заносим в столбец «Отношение». Минимум достигается в строке переменной s3, она и становится направляющей, разрешающий элемент выделен серым цветом.

Вторую симплекс-таблицу (табл. 5) строим по правилам, указанным на с. 8. Текущее БДР:

(x1, x2, x3, s1, s2, s3) = (28,33; 0; 0; 97,67; 840,00; 0), z = 5156,67.

В z-строке второй симплекс-таблицы два отрицательных элемента — продолжим оптимизацию. Столбец переменной х3 и строка переменной s2 становятся направляющими.

В z-строке третьей симплекс-таблицы (табл. 6) один отрицательный элемент, следовательно, решение не оптимально. Текущее БДР:

(x1, x2, x3, s1, s2, s3) = (20,56; 0; 46,67; 96,11; 0; 0), z = 8081,11.

Продолжим оптимизацию. Столбец переменной х2 и строка переменной х1 становятся направляющими. Строим четвертую симплекс-таблицу (табл. 7). В z-строке нет отрицательных элементов, следовательно, мы нашли оптимальное базисное решение задачи (b1) — (b5):

Оптимальный базис образован столбцами переменных s1, x3, x2 (удобно записывать столбцы именно так, чтобы на месте j стоял столбец базисной переменной для строки i).

Максимальная возможная прибыль равна 9641 рублю. Ее можно получить, если в соответствии с планом x* (предварительно округлив до целого) произвести 22 сейфа и 67 шкафов. Вектор x* дает информацию и об использовании ресурсов при оптимальном плане производства. Материалы — сталь 3 и сварочные электроды — используются полностью (так как s2 = s3 = 0); сталь 20 (53,09 кг) — в избытке.

Для решения данной задачи ЛП можно использовать программу, входящую в пакет программ TORA, взятую на сайте экономического факультета НГУ.

После запуска программы, входа в подпрограмму линейного программирования (Linear programming), в появившемся окне редактирования заполнены необходимые строки: имя задачи (Problem Title) — Kursrab, число переменных (Nbr of Variables) — 3, число ограничений (Nbr of constraints) — 3. Далее, в таблицу вводится целевая функция (Obj. Function) и формируются ограничения (Constraints). Исходные данные сохранены в файле под именем MLK. В распечатанном виде данные показаны в таблице 8.

Таблица 8. Исходные данные.

————————————————————————————-;

Title: Kursrab.

x1 x2 x3 RHS.

————————————————————————————-;

max 182 155 93.

————————————————————————————-;

Constraint 1: 2.2 3.5 0.4 <= 160.

Constraint 2: 48 20 26 <= 2200.

Constraint 3: 1.2 0.9 0.2 <= 34.

————————————————————————————-;

Далее программа предлагает выбрать метод решения (меню Algorithms); для данной задачи достаточен прямой симплекс-метод (Primal simplex), его и выбираем. Теперь TORA запрашивает способ поиска первого базисного решения (меню Starting Solution). Структура включенной в курсовую работу задачи позволяет строить первый базис из «переменных недостатка» (Slack variables). Выбираем соответствующий пункт меню.

В первой симплекс-таблице (табл. 9) в верхней строке окна указаны имя задачи и номер итерации. В первом столбце таблицы (с заголовком Basic) записан текущий базис (имена базисных переменных для соответствующих ограничений, sxi — переменная недостатка для ограничения i). В заголовках следующих столбцов видим имена всех переменных канонической формы задачи. В последнем столбце (Solution) — значение целевой функции на текущем базисном решении (верхний элемент) и значения базисных переменных в текущем базисном допустимом решении (небазисные переменные равны нулю). Элементы второй строки таблицы (кроме последнего) — это коэффициенты целевой функции, выраженной через небазисные переменные.

Таблица 9. Первая симплекс-таблица.

———————————————————————————————————;

Title: Kursrab Iteration No: 1.

Basic x1 x2 x3 sx4 sx5 sx6 Solution.

———————————————————————————————————;

z -182.00 -155.00 -93.00 0.00 0.00 0.00 0.00.

———————————————————————————————————;

1)sx4 2.20 3.50 0.40 1.00 0.00 0.00 160.00.

2)sx5 48.00 20.00 26.00 0.00 1.00 0.00 2200.00.

3)sx6 1.20 0.90 0.20 0.00 0.00 1.00 34.00.

———————————————————————————————————;

После автоматического выполнения очередной итерации (Next iteration), сохраним текущую симплекс-таблицу в новом файле и распечатаем ее (табл.10).

Таблица 10. Вторая симплекс-таблица.

———————————————————————————————————;

Title: Kursrab Iteration No: 2.

Basic x1 x2 x3 sx4 sx5 sx6 Solution.

———————————————————————————————————;

z 0.00 -18.50 -62.67 0.00 0.00 151.67 5156.67.

———————————————————————————————————;

1)sx4 0.00 1.85 0.03 1.00 0.00 -1.83 97.67.

2)sx5 0.00 -16.00 18.00 0.00 1.00 -40.00 840.00.

3)x1 1.00 0.75 0.17 0.00 0.00 0.83 28.33.

———————————————————————————————————;

Далее следуют третья (табл.11) и четвертая (табл.12) симплекс-таблицы, полученные машиной.

Таблица 11. Третья симплекс-таблица.

———————————————————————————————————;

Title: Kursrab Iteration No: 3.

Basic x1 x2 x3 sx4 sx5 sx6 Solution.

———————————————————————————————————;

z 0.00 -74.20 0.00 0.00 3.48 12.41 8081.11.

———————————————————————————————————;

1)sx4 0.00 1.88 0.00 1.00 -0.00 -1.76 96.11.

2)x3 0.00 -0.89 1.00 0.00 0.06 -2.22 46.67.

3)x1 1.00 0.90 0.00 0.00 -0.01 1.20 20.56.

———————————————————————————————————;

Таблица 12. Последняя симплекс-таблица.

———————————————————————————————————;

Title: Kursrab Final Iteration No: 4.

Basic x1 x2 x3 sx4 sx5 sx6 Solution.

———————————————————————————————————;

z 82.62 0.00 0.00 0.00 2.72 111.86 9779.38.

———————————————————————————————————;

1)sx4 -2.09 0.00 0.00 1.00 0.02 -4.28 53.09.

2)x3 0.99 0.00 1.00 0.00 0.05 -1.03 67.01.

3)x2 1.11 1.00 0.00 0.00 -0.01 1.34 22.89.

———————————————————————————————————;

После четвертой итерации появляется меню Optimum, свидетельствующее о получении оптимального решения. Таблица 13 предоставляет итоговые данные. В верхней строке окна записаны имя задачи и номер итерации. Непосредственно над таблицей — оптимальное значение целевой функции (Obj value). Каждая строка таблицы соответствуют одной из переменных исходной задачи и указывает: ее имя (Variable), оптимальное значение (Value), соответствующий коэффициент целевой функции (Obj Coef), «вклад» переменной — произведение оптимального значения на коэффициент целевой функции (Obj Val Contrib).

Таблица 13. Оптимальное решение.

————————————————————————————————;

Title: Kursrab Final iteration No: 4.

Objective value (max) = 9779.3818.

————————————————————————————————;

Variable Value Obj Coeff Obj Val Contrib.

————————————————————————————————;

x1 0.0000 182.0000 0.0000.

x2 22.8866 155.0000 3547.4229.

x3 67.0103 93.0000 6231.9585.

————————————————————————————————;