- •Выпускная квалификационная работа
- •Глава 1. Теория линейного программирования 4
- •Глава 2. Применение симплекс-метода для составления плана производства (на примере нэрз) 23
- •Введение
- •Глава 1. Теория линейного программирования
- •1.1. Линейное программирование — инструмент исследования линейных моделей
- •3. Выражаем базисные переменные через небазисные1
- •1.2. Основы симплекс-метода
- •1. Описываем целевую функцию уравнением
- •2. Выбираем исходное базисное допустимое решение
- •4. Выражаем целевую функцию через небазисные переменные
- •5. Проверяем оптимальность текущего базисного решения
- •6. Проверяем ограниченность задачи
- •7. Переход к другому базису 2
- •8. Конечность симплекс-метода
- •9. Построение исходного базисного допустимого решения 3
- •1.3. Симплекс-таблицы
- •1.4. Двойственность в линейном программировании
- •Глава 2. Применение симплекс-метода для составления плана производства (на примере нэрз)
- •2.1. Общая характеристика предприятия
- •2.2. Моделирование экономической ситуации в инструментальном цехе
- •2.3. Решение задачи
- •2.3. Разработка рекомендаций по улучшению найденного плана производства
- •Заключение
- •Обозначения
- •Литература
- •Источники
2.3. Решение задачи
Для решения данной задачи ЛП мною была использована программа, входящая в пакет программ TORA, взятая на сайте экономического факультета НГУ.
После запуска программы, входа в подпрограмму линейного программирования (Linear programming), в появившемся окне редактирования заполнены необходимые строки: имя задачи (Problem Title) — NERZ, число переменных (Nbr of Variables) — 6, число ограничений (Nbr of constraints) — 7. Далее, в таблицу вводится целевая функция (Obj. Function) и формируются ограничения (Constraints). Исходные данные сохранены в файле под именем GAA. В распечатанном виде данные показаны в таблице 5.
Таблица 5. Исходная таблица
x1 x2 x3 x4 x5 x6 RHS
-------------------------------------------------------------------
max 67 16 182 155 22 93
-------------------------------------------------------------------
Constraint 1: 1.3 0.8 2.2 3.5 0.5 0.4 <= 160
Constraint 2: 0 0 48 20 0.4 26 <= 2200
Constraint 3: 0.2 0.05 0 0 0 0 <= 14
Constraint 4: 0 0 1.2 0.9 0.1 0.2 <= 34
Constraint 5: 5 0 0 5 10 8 <= 900
Constraint 6: 0.9 0.3 2.1 1.4 0.3 0.7 <= 136
Constraint 7: 0 0 0 0 0 1 = 50
-------------------------------------------------------------------
Так как ограничения в модели операции двух видов (“≤” и “=”), то в меню “Algorithms” последовательно выбираю “Primal simplex” “Two-phase method”.
Далее следует решение, начинающееся со вспомогательной задачи.
На первом этапе базис симплекс-таблицы (табл. 6) составлен из шести переменных недостатка (sx7 — sx12) и одной “искусственной” переменной (Rx13). Целевая функция вспомогательной задачи минимизируется.
Таблица 6. Первая симплекс-таблица
Title: NERZ
(phase_1) min Iteration No: 1
Basic x1 x2 x3 x4 x5 x6 sx7
-------------------------------------------------------------------------
z 0.00 0.00 0.00 0.00 0.00 1.00 0.00
-------------------------------------------------------------------------
1)sx7 1.30 0.80 2.20 3.50 0.50 0.40 1.00
2)sx8 0.00 0.00 48.00 20.00 0.40 26.00 0.00
3)sx9 0.20 0.05 0.00 0.00 0.00 0.00 0.00
4)sx10 0.00 0.00 1.20 0.90 0.10 0.20 0.00
5)sx11 5.00 0.00 0.00 5.00 10.00 8.00 0.00
6)sx12 0.90 0.30 2.10 1.40 0.30 0.70 0.00
7)Rx13 0.00 0.00 0.00 0.00 0.00 1.00 0.00
-------------------------------------------------------------------------
Basic sx8 sx9 sx10 sx11 sx12 Rx13 Solution
--------------------------------------------------------------------------
z 0.00 0.00 0.00 0.00 0.00 0.00 50.00
--------------------------------------------------------------------------
1)sx7 0.00 0.00 0.00 0.00 0.00 0.00 160.00
2)sx8 1.00 0.00 0.00 0.00 0.00 0.00 2200.00
3)sx9 0.00 1.00 0.00 0.00 0.00 0.00 14.00
4)sx10 0.00 0.00 1.00 0.00 0.00 0.00 34.00
5)sx11 0.00 0.00 0.00 1.00 0.00 0.00 900.00
6)sx12 0.00 0.00 0.00 0.00 1.00 0.00 136.00
7)Rx13 0.00 0.00 0.00 0.00 0.00 1.00 50.00
--------------------------------------------------------------------------
Из второй симплекс-таблицы (табл. 7) видно, что “искусственная” переменная (Rx13) ушла из базиса, ее место заняла переменная x6, значение ЦФ равно нулю. Получено оптимальное решение вспомогательной задачи.
Таблица 7. Вторая симплекс-таблица
Title: NERZ
(phase_1) min Iteration No: 2
Basic x1 x2 x3 x4 x5 x6 sx7
-------------------------------------------------------------------------
z 0.00 0.00 0.00 0.00 0.00 0.00 0.00
-------------------------------------------------------------------------
1)sx7 1.30 0.80 2.20 3.50 0.50 0.00 1.00
2)sx8 0.00 0.00 48.00 20.00 0.40 0.00 0.00
3)sx9 0.20 0.05 0.00 0.00 0.00 0.00 0.00
4)sx10 0.00 0.00 1.20 0.90 0.10 0.00 0.00
5)sx11 5.00 0.00 0.00 5.00 10.00 0.00 0.00
6)sx12 0.90 0.30 2.10 1.40 0.30 0.00 0.00
7)x6 0.00 0.00 0.00 0.00 0.00 1.00 0.00
-------------------------------------------------------------------------
Basic sx8 sx9 sx10 sx11 sx12 Rx13 Solution
--------------------------------------------------------------------------
z 0.00 0.00 0.00 0.00 0.00 -1.00 0.00
--------------------------------------------------------------------------
1)sx7 0.00 0.00 0.00 0.00 0.00 -0.40 140.00
2)sx8 1.00 0.00 0.00 0.00 0.00 -26.00 900.00
3)sx9 0.00 1.00 0.00 0.00 0.00 0.00 14.00
4)sx10 0.00 0.00 1.00 0.00 0.00 -0.20 24.00
5)sx11 0.00 0.00 0.00 1.00 0.00 -8.00 500.00
6)sx12 0.00 0.00 0.00 0.00 1.00 -0.70 101.00
7)x6 0.00 0.00 0.00 0.00 0.00 1.00 50.00
--------------------------------------------------------------------------
С третьей симплекс-таблицы (табл. 8) начинается второй этап решения. В z-строке коэффициенты максимизируемой целевой функции, выраженной через небазисные переменные. Значение ЦФ равно 4650.
Таблица 8. Третья симплекс-таблица
Title: NERZ
<max> (phase_2)
Iteration No: 3
Basic x1 x2 x3 x4 x5 x6 sx7
-------------------------------------------------------------------------
z -67.00 -16.00 -182.00 -155.00 -22.00 0.00 0.00
-------------------------------------------------------------------------
1)sx7 1.30 0.80 2.20 3.50 0.50 0.00 1.00
2)sx8 0.00 0.00 48.00 20.00 0.40 0.00 0.00
3)sx9 0.20 0.05 0.00 0.00 0.00 0.00 0.00
4)sx10 0.00 0.00 1.20 0.90 0.10 0.00 0.00
5)sx11 5.00 0.00 0.00 5.00 10.00 0.00 0.00
6)sx12 0.90 0.30 2.10 1.40 0.30 0.00 0.00
7)x6 0.00 0.00 0.00 0.00 0.00 1.00 0.00
-------------------------------------------------------------------------
Basic sx8 sx9 sx10 sx11 sx12 Rx13 Solution
--------------------------------------------------------------------------
z 0.00 0.00 0.00 0.00 0.00 93.00 4650.00
--------------------------------------------------------------------------
1)sx7 0.00 0.00 0.00 0.00 0.00 -0.40 140.00
2)sx8 1.00 0.00 0.00 0.00 0.00 -26.00 900.00
3)sx9 0.00 1.00 0.00 0.00 0.00 0.00 14.00
4)sx10 0.00 0.00 1.00 0.00 0.00 -0.20 24.00
5)sx11 0.00 0.00 0.00 1.00 0.00 -8.00 500.00
6)sx12 0.00 0.00 0.00 0.00 1.00 -0.70 101.00
7)x6 0.00 0.00 0.00 0.00 0.00 1.00 50.00
--------------------------------------------------------------------------
При автоматическом выполнении очередной итерации появляется меню Optimum, свидетельствующее о получении оптимального решения (на седьмой итерации). Распечатав последнюю симплекс-таблицу (Print optimum tableau) (табл. 9), обнаруживаю, что в z-строке нет отрицательных коэффициентов, значение ЦФ равно 12843,82, оптимальный базис образован столбцами переменных sх8, x3, sх9, x4, sх11, x1, x6, а оптимальное базисное решение задачи выглядит следующим образом:
.
Таблица 9. Последняя симплекс-таблица
Title: NERZ
<max> (phase_2)
Final Iteration No: 7
Basic x1 x2 x3 x4 x5 x6 sx7
-------------------------------------------------------------------------
z 0.00 11.83 0.00 0.00 4.51 0.00 14.99
-------------------------------------------------------------------------
1)sx8 0.00 2.79 0.00 0.00 -2.56 0.00 7.61
2)x3 0.00 -0.13 1.00 0.00 0.03 0.00 -0.36
3)sx9 0.00 -0.02 0.00 0.00 -0.03 0.00 -0.02
4)x4 0.00 0.17 0.00 1.00 0.06 0.00 0.48
5)sx11 0.00 -2.71 0.00 0.00 8.92 0.00 -2.84
6)x1 1.00 0.37 0.00 0.00 0.15 0.00 0.09
7)x6 0.00 0.00 0.00 0.00 0.00 1.00 0.00
-------------------------------------------------------------------------
Basic sx8 sx9 sx10 sx11 sx12 Rx13 Solution
--------------------------------------------------------------------------
z 0.00 0.00 31.80 0.00 52.79 43.69 12843.82
--------------------------------------------------------------------------
1)sx8 1.00 0.00 -34.72 0.00 -10.99 -14.41 22.01
2)x3 0.00 0.00 0.59 0.00 0.52 -0.34 16.16
3)sx9 0.00 1.00 0.38 0.00 -0.20 0.07 0.69
4)x4 0.00 0.00 0.33 0.00 -0.69 0.22 5.13
5)sx11 0.00 0.00 7.75 1.00 -1.45 -7.40 141.61
6)x1 0.00 0.00 -1.88 0.00 0.98 -0.35 66.55
7)x6 0.00 0.00 0.00 0.00 0.00 1.00 50.00
--------------------------------------------------------------------------
Таблица 10 отражает некоторые итоги решения. В верхней строке записаны имя задачи и номер итерации. Непосредственно над таблицей — оптимальное значение целевой функции (Obj value). Каждая строка таблицы соответствуют одной из переменных исходной задачи и указывает: ее имя (Variable), оптимальное значение (Value), соответствующий коэффициент целевой функции (Obj Coef), „вклад” переменной — произведение оптимального значения на коэффициент целевой функции (Obj Val Contrib).
Таблица 10. Сводка результатов решения
Title: NERZ Final iteration No: 7
Objective value (max) =12843.8174
--------------------------------------------------------------
Variable Value Obj Coeff Obj Val Contrib
--------------------------------------------------------------
x1 66.5522 67.0000 4458.9961
x2 0.0000 16.0000 0.0000
x3 16.1559 182.0000 2940.3691
x4 5.1255 155.0000 794.4523
x5 0.0000 22.0000 0.0000
x6 50.0000 93.0000 4650.0000
--------------------------------------------------------------
Максимальная возможная прибыль равна 12759 рублям. Ее можно получить, если в соответствии с планом x* (предварительно округлив до целого) произвести 66 фрез, 16 котлов, 5 сейфов и 50 шкафов. Вектор x* дает информацию и об использовании ресурсов при оптимальном плане производства. Материалы — сталь 20, сварочные электроды, а также трудовые ресурсы — используются полностью (так как sх7 = sх10 = sх12 = 0); сталь 3 (22,01 кг), твердый сплав (0,69 кг) и цинк (141,61 г) в избытке.
