Описание данных модели
В связи со снижением объема производства инструмента и оснастки для основных цехов в инструментальном цехе оказалось частично незадействованным технологическое оборудование, образовались остатки материала. Отдел маркетинга предоставил список продукции, которую можно было бы реализовать через магазины Первомайского района. Из всего списка руководством цеха были выбраны изделия, изготовление которых не требовало дополнительных затрат на переоснащение производства и приобретение сырья. Это: котел отопительный, сейф для охотничьего оружия, шкаф для спецодежды рабочих. В таблице 2 сведены данные по свободным ресурсам цеха на март 2009 года, а также нормы расхода на каждый вид продукции. В таблице 3 представлена прибыль от реализации каждого изделия.
Таблица 2. Нормы расхода материалов на изготовление продукции
| Вид ресурса | Наименование изделий | Общее количество ресурса | ||
| Котел | Сейф | Шкаф | ||
| Сталь 20, кг | 2,2 | 3,5 | 0,4 | |
| Сталь 3, кг | ||||
| Электроды, кг | 1,2 | 0,9 | 0,2 | |
| Источник: данные взяты из [3]. |
Таблица 3 Прибыль от реализации изделий, руб
| Наименование изделий | ||||
| Котел | Сейф | Шкаф | ||
| Цена | ||||
| Себестоимость | ||||
| Прибыль | ||||
| Источники: строка 1 взята из [6], строка 2 взята из [2], строка 3 получена вычитанием строки 2 из строки 1. |
Требуется составить план производства, обеспечивающий максимальную прибыль.
Построение математической модели
Моделью операции является следующая задача линейного программирования:
(а1)
при
(а2)
(а3)
(а4)
(а5)
Целевая функция (а1) описывает суммарную прибыль цеха при плане х. х1, х2, х3, - количество изготавливаемых котлов, сейфов и шкафов соответственно. Правые части ограничений-неравенств (а2) - (а4) соответствуют объемам ресурсов, имеющихся в распоряжении цеха, (а5) - естественное условие неотрицательности переменных.
Решение задачи
Приведем данную задачу к канонической форме:
(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):
Оптимальный базис b образован столбцами переменных 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. Исходные данные
----------------------------------------------------------: 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. Первая симплекс-таблица
-----------------------------------------------------------------------: Kursrab Iteration No: 1
x1 x2 x3 sx4 sx5 sx6 Solution
----------------------------------------------------------------------- -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
x1 x2 x3 sx4 sx5 sx6 Solution
----------------------------------------------------------------------- 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. Третья симплекс-таблица
-----------------------------------------------------------------------: Kursrab Iteration No: 3
x1 x2 x3 sx4 sx5 sx6 Solution
----------------------------------------------------------------------- 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
x1 x2 x3 sx4 sx5 sx6 Solution
----------------------------------------------------------------------- 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. Оптимальное решение
-----------------------------------------------------------------: Kursrab Final iteration No: 4
Objective value (max) = 9779.3818
---------------------------------------------------------------- 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
----------------------------------------------------------------
ЗАКЛЮЧЕНИЕ
В данной курсовой работе я изучил теоретические основы линейного программирования, построил математическую модель плана производства дополнительной продукции. Симплекс-методом решена задача ЛП и получен оптимальный план производства. Необходимо заметить, что результаты не зависят от того, каким способом решена задача, “вручную” или с помощью компьютерной программы.
Результаты, полученные в данной работе, были применены при планировании производства в инструментальном цехе.
ЛИТЕРАТУРА
1. Ашманов С. А.,. Линейное программирование: Учебное пособие для вузов по спец. "Прикл. математика". - М.: Наука, 1981. - 304 с.
2. Калькуляция себестоимости изготовления продукции в инструментальном цехе НЭРЗ. Инженер по ОиНТ Василькова Ю. Ф.
. Нормы расхода материалов на изготовление продукции в инструментальном цехе. Отдел главного технолога НЭРЗ.
. Паспорт предприятия, филиала ОАО РЖД “Новосибирский электровозоремонтный завод” за 2001 год.
. Раков В. А. Локомотивы отечественных железных дорог 1956-1975 года. М., 1999. - 192 с.
. Справка о ценах на изделия в магазинах Первомайского района. Отдел маркетинга НЭРЗ. 18.02.2009 г.
. Справочник нормировщика машиностроителя в 4-х томах. Том II. Техническое нормирование станочных работ. Под редакцией Е. И. Стружестраха. МАШГИЗ, Москва 1961 г, 892 с.
. Справочник нормировщика машиностроителя в 4-х томах. Том III. Нормирование литейных, кузнечных, штамповочных, сварочных, лакокрасочных работ, металлопокрытий и деревообработки. Под редакцией Р. И. Хисина. МАШГИЗ, Москва 1962 г, 672 с.
. Хуторецкий А. Б. Модели исследования операций: введение в предмет, нелинейное программирование, выпуклое программирование, линейное программирование: [учебник для вузов], Новосибирск: Изд-во СО РАН, 2006.- 267 с.