Линейная производственная задача

ГОСУДАРСТВЕННЫЙ   УНИВЕРСИТЕТ   УПРАВЛЕНИЯ

Кафедра прикладной математики

КУРСОВАЯ РАБОТА

по дисциплине «Прикладная математика»

Выполнил                              Набиев Р.Р.

Институт                                            ИНиМЭ

Отделение                              дневное

Курс                                            II

Группа                                            2

Руководитель                                Курочккин А. П.

Дата сдачи на проверку 30.05.02.

Дата защиты                  

Оценка                             

Подпись руководителя 

Москва – 2002

СОДЕРЖАНИЕ.

ЛИНЕЙНАЯ ПРОИЗВОДСТВЕННАЯ ЗАДАЧА.

СОСТАВЛЕНИЕ МОДЕЛИ НОВОЙ ПРОИЗВОДСTВЕННОЙ ПРОГРАММЫ С УЧЁТОМ ПРОПОРЦИЙ.

ФОРМУЛИРОВКА ДВОЙСТВЕННОЙ ЛИНЕЙНОЙ ЗАДАЧИ И ЕЁ РЕШЕНИЕ  ДВОЙСТВЕННЫМ СИМПЛЕКСНЫМ МЕТОДОМ.

“РАСШИВКА УЗКИХ МЕСТ“ ПРОИЗВОДСТВА. ФОРМУЛИРОВКА И СОСТАВЛЕНИЕ МАТЕМАТИЧЕСКОЙ МОДЕЛИ.

ТРАНСПОРТНАЯ ЗАДАЧА.

МЕТОД ВЕТВЕЙ И ГРАНИЦ.

РЕШЕНИЕ  ЗАДАЧИ  РАСПРЕДЕЛЕНИЯ  КАПВЛОЖЕНИЙ  МЕТОДОМ  ДИНАМИЧЕСКОГО ПРОГРАММИРОВАНИЯ.

ТЕОРИЯ МАТРИЧНЫХ ИГР.

ЛИНЕЙНАЯ ПРОИЗВОДСТВЕННАЯ ЗАДАЧА.

Вариант № 15.

Формулировка линейной производственной задачи:

Фирмой «Балтика » выпускает 4 вида продукции:

х1 - Пиво безалкогольное,

х2 – Пиво классичечкое,

х3 – Пиво крепкое,

х4 – Пиво темное.

При этом фирма располагает 3 видами ресурсов:

162 т. – пшеницы,

134 т. – солод,

148 т. - хмель

Требуется составить такой план выпуска изделий х1, х2, х3, х4 , при котором мы уложимся в имеющиеся ресурсы и суммарная прибыль от реализации изготовленных по плану изделий будет максимальна.

Это – задача оптимизации и для ее решения необходимо создать математическую модель

А - матрица удельных затрат;

В - вектор объёмов ресурсов;

С - вектор удельной прибыли.

а11                а12                 а13                 а14                               в1

А =                 а21                а22                 а23                 а24 ;                  В=              в2      ;

         а31                а32                а33                а34               в3

С = (с1, с2, с3, с4).

           В индивидуальном задании матрицы компактно записаны в виде:

        3  0  2  5                                                         162

А =  3  6  0  3                                           В = 134

        2  4  3  1                                                           148

С=(24, 20, 31, 10 ) .

Х - вектор объёмов выпуска продукции (производственная программа).

Х = (х1, х2, х3, х4) – 4 вида изделий.

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

найти Х = (х1, х2, х3, х4) такие, что

(1)   z(x1, x2, x3, x4) = c1x1 + c2x2 + c3x3 + c4x4  max, где z- функция прибыли;

(2)                  a11x1+a12x2+a13x3+a14x4 < в1                                                     

                      а21х1+а22х2+а23х3+а34х4 < в2 ;

          а31х1+а32х2+а33х3+а34х4 < в3

(3)  xi 0 , i=1,4 .

(1) - целевая функция;

                     (2) - линейные ограничения задачи (ограничения по ресурсам);

                     (3) - условие не отрицательности задачи .

Подставив соответствующие значения , имеем:

(1)  z=24x1+20x2+31x3+10х4max

(2)               3x1         + 2x3 + 5x4   162

                    3x1  + 6x2         + 3x4    134

          2x1 + 4x2+3x3 +   x4    148

(3)         xi   0, i=1...4.

(1)-(3)- математическая модель линейной производственной задачи.

Целевая функция (1) и условие не отрицательности (3) остаются без изменений. В линейные ограничения по ресурсам вводятся дополнительные выравнивающие переменные х5, х6, х7.,которые также являются базисными.

            х5 - остаток 1-го ресурса;

            х6 - остаток 2-го ресурса;

            х7 - остаток 3-го ресурса.

Неравенство (2) следует заменить уравнениями. Получим задачу линейного программирования в каноническом виде:

(1)  z=24x1+20x2+31x3+10х4max

(2)               3x1         + 2x3 + 5x4  = 162

                    3x1  + 6x2         + 3x4   = 134

          2x1 + 4x2+3x3 +   x4   = 148

(3)         xi   0, i=1...4.

(1)-(3)-задача линейного программирования .

РЕШЕНИЕ ЗАДАЧИ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ СИМПЛЕКСНЫМ МЕТОДОМ .

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

Подставив соответствующие значения из (1) и (3), имеем :