Теория Принятия Решения

ГОСУДАРСТВЕННОЕ ОБЩЕОБРАЗОВАТЕЛЬНОЕ

УЧРЕЖДЕНИЕ  ВЫСШЕГО ПРОФЕССИОНАЛЬНОГО

ОБРАЗОВАНИЯ

«МОСКОВСКИЙ ГОСУДАРСТВЕННЫЙ ГОРНЫЙ

УНИВЕРСИТЕТ»

КАФЕДРА АСУ 
 
 
 
 
 
 
 
 

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

По дисциплине

«Теория принятия решений» 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

Выполнил: ст. гр. АС-В-08

                                                                                       Мамаков С.Р.

                                                                                                 Принял: доц., к.т.н.

                                                                                     Быков А.Ю. 
 
 
 
 
 
 
 
 

Москва 2011 год 
 
 
 

ОГЛАВЛЕНИЕ:

1.      Задание на курсовую работу…………………………………………………….-3-
2.       Задача линейного программирования…………………………………………-4-
1.       Физическая интерпретация задачи……………………………………………..-4-
2.       Краткое описание метода решения……………………………………………..-4-
1.     Понятие математического программирования…………………………………-4-
2.      Понятие линейного программирования. Виды задач ЗЛП………………….....-5-
3.      Постановка ЗЛП и исследования их структуры………………………………...-6-
1. Оптимальное распределение взаимозаменяемых ресурсов……………………-7-
2. Задача о смесях……………………………………………………………………-8-
3. Задача о раскрое материала………………………………………………………-9-
4.      Форма записи ЗЛП……………………………………………………………….-10-
5.      Решение записи ЗЛП симплекс методом……………………………………….-11-
3.       Блок схема алгоритма решения задачи…………………………………………-14-
4.       Решение задачи…………………………………………………………………..-15-
3.       Задача динамического программирования…………………………………….-17-
1.      Физическая интерпретация задачи……………………………………………...-17-
2.      Понятие динамического программирования…………………………………..-17-
3.      Решение…………………………………………………………………………...-19-

 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

ЗАДАНИЕ НА КУРСОВУЮ РАБОТУ 

5.37.  Задача  линейного программирования 

min Z=3x₁+x₂

-4x₁+x₂ ≤ 29

3x₁-x₂ ≤ 15

5x₁+x₂ ≥ 38

x_1,x₂ ≥ 0, целые. 
 
 

3.7.   Задача  динамического программирования 
 

  0          0         0        0

100       30       50      40

200       50       80      50

300       90       90     110

400      110     150    120

500      170     190    180

600      180     210    220 
 

1.17.    Решение задачи методом Гомари 

Z=4x₁+2x₂+5x₃+8x₄

x₁+2x₂+4x₃+8x₄ ≤ 24

3x₁+5x₂+x₃+      ≤ 12

6x₁+      +3x₃+x₄ ≤ 35

x_j ≥0 
 
 
 

                                                                                                         Выдал: доц., к.т.н.

                                                                                            Быков А.Ю. 

Получил: ст.гр. АС-В-08

                                                                                              Мамаков С.Р. 
 
 
 
 
 
 
 
 

ЗАДАЧА  ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ. 

1.Физическая  интерпретация задачи. 
 

При производстве двух видов изделий (x₁, x₂), указаны планы производства изделий (А₁, А₂, А₃), норма затраченного и общее количество сырья. Нужно определить оптимальный план производства изделий.

Таблица 1.1

   

2.   КРАТКОЕ ОПИСАНИЕ МЕТОДА РЕШЕНИЯ 

2.1    Понятие математического программирования 
 

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

       Наличие ограничений делает задачи математического программирования принципиально отличными от классических задач математического анализа по отысканию экстремальных значений функции. Методы математического анализа для поиска экстремума функции в задачах математического программирования оказываются непригодными.

       Для решения задач математического программирования разработаны и разрабатываются специальные методы и теории. Так как при решении этих задач приходится выполнять значительный объем вычислений, то при сравнительной оценке методов большое значение придается эффективности и удобству их реализации на ЭВМ.

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

   

     В  зависимости от свойств целевой функции и функции ограничений все задачи математического программирования делятся на два основных класса:

• Задачи линейного программирования;
• Задачи нелинейного программирования.

 

        Если целевая функция и функции ограничений – линейные функции, то

соответствующая задача поиска экстремума является задачей  линейного программирования. Если хотя бы одна из указанных функций нелинейна, то соответствующая задача поиска экстремума является задачей нелинейного программирования. 
 

1.2   Понятие линейного  программирования.  Виды задач линейного  программирования 
 

     Линейное программирование (ЛП) –  один из первых и наиболее  подробно изученных разделов  математического программирования. Именно линейное программирование явилось тем разделом, с которого и начала развиваться сама дисциплина «математическое программирование». Термин «программирование» в названии дисциплины ничего общего с термином «программирование (т.е. составление программы) для ЭВМ» не имеет, т.к. дисциплина «линейное программирование» возникло еще до того  времени, когда ЭВМ стали широко применяться для решения математических, инженерных, экономических и других задач.

      Термин «линейное программирование» возник в результате неточного перевода английского «linear programming». Одно из значений слова «programming» - составление планов, планирование. Следовательно, правильным переводом английского «linear programming» было бы не «линейное программирование», а «линейное планирование», что более точно отражают содержание дисциплины. Однако, термины линейное программирование, нелинейное программирование, математическое программирование и т.д. в нашей литературе стали общепринятыми и поэтому будут сохранены.

       И так, линейное программирование возникло после второй мировой войны и стало быстро развиваться, привлекая внимание математиков, экономистов, инженеров благодаря возможности широкого практического применения, а так же математической стройности.

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

       Линейное программирование применяется при решении экономических задач, в таких задачах как управление и планирование производства; в задачах определения оптимального размещения оборудования на морских судах, в цехах; задачах определения оптимального плана перевозок груза (транспортная задача); в задачах оптимального распределения кадров и т.д..

      Задача линейного  программирования  (ЛП), как уже ясно из сказанного выше, состоит в нахождении минимума (или максимума) линейной функции при линейных ограничениях.

    

  Общая форма  задачи имеет вид: найти min cx при условиях

a_λx – b_i  ≥ 0,  i ϵ I₁

     a_λx – b_i  = 0,  i ϵ I₂

     x_λ  ≥ 0,           j ϵ J₁,

где

     I₁ U I₂ = {1,…..,m}, I₁ U I₂ = Ø, J₁ ᴄ {1,……,n}, x= (x₁,….., x_n)^T,

          C= (c₁,……,c_n), a_i = (a_i1,……, a_in),  i=1,……m.

       Здесь и далее нам удобнее считать с и a_i вектор – строками, а х и

b = (b_i ,…..,b_m)^T – вектор столбцами.

       Наряду с общей формой широко  используются также каноническая  и стандартная формы. Как в  канонической так и в стандартной  форме 

                 J₁ ={1,……,n}, т.е. все переменные в любом допустимом решение задачи должны принимать неотрицательные значения (такие переменные принято называть неотрицательные в отличии от так называемых свободных переменных, на область значений которых подобные ограничение не накладывается). Отличие же между этими формами состоит в том, что в одном случае I₂ = 0, а в другом I₁ = 0.

         Задача ЛП в канонической форме:

w = cx – min                                     (2.1)

Ax = b                                               (2.2)

x ≥ 0                                                  (2.3)

     Задача ЛП в стандартной форме

w = cx – min                                    

Ax = b                                              

x ≥ 0                                             

         В обоих случаях А есть матрица размерности m х n, i-я строка которой совпадает с вектором а_i.

         Задача ЛП в общей форме  сводится (в определенном смысле) к задаче ЛП в канонической (стандартной) форме. Под этим  понимается существование общего  способа построения по исходной задаче новой задачи ЛП, любое оптимальное решение которой «легко» преобразуется в оптимальное решение исходной задачи и наоборот. (Фактически, связь между этими задачами оказывается еще более тесной). Тем самым мы получаем возможность, не теряя общности, заниматься задачами ЛП, представленных либо в канонической, либо в стандартной форме. Ввиду этого наши дальнейшие рассмотрения задач ЛП будут посвящены, главным образом, задачам в канонической форме. 
 
 
 
 
 
 
 
 
 
 
 

2.3    Постановка задач  линейного программирования  и исследование  их структуры. 

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

          Максимизировать F(x₁, x₂,…. x_n) при ограничениях

          g₁(x₁, x₂,…. x_n) ≤ b₁;

          g₂(x₁, x₂,…. x_n) ≤ b₂;

          ….   ….   ….   ….

          g_m(x₁, x₂,…. x_n) ≤ b_m;

          где f(x₁, x₂,…. x_n) – целевая функция, или критерий эффективности (например, прибыль от производства каких-либо видов продукции, стоимость перевозок и т.п.); X={ x₁,…. X_n} – варьируемые параметры; g₁(x), . , g_m(x) – функции которые задают ограничения на имеющиеся ресурсы.

        Среди разных разделов математического  программирования наиболее развитым  и законченным является линейное  программирование.

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

        Рассмотрим некоторые из них.

        Определение оптимального ассортимента. Имеются m видов ресурсов в количествах b₁, b₂, b_i,… b_m и n видов изделий. Задана матрица А=IIa_ijII, i=1,…,m,j=1,…n, где a_ij характеризует нормы расхода i-го ресурса на единицу j-го вида изделий. Эффективность производства j-го вида изделий характеризуется показателем Cj, удовлетворяющим условию линейности. Нужно определить такой план выпуска изделий (оптимальный ассортимент), при котором суммарный показатель эффективности будет наибольший.

         Обозначим количество единиц k-го вида изделий, выпускаемых предприятием, через x_k, k=1…k. Тогда математическая модель этой задачи будет иметь такой вид:

                             Максимизировать                                (3.1)

                               При ограничениях                          (3.2)

         Кроме ограничений на ресурсы  (3.2) в эту модель можно ввести  дополнительные ограничения на  планируемый уровень выпуска продукции x_j  ≥ x_j0,

x_i : x_j : x_k = b_i : b_j : b_k для всех i,j,k и т.д. 
 
 
 
 
 
 
 
 
 
 

2.3.1.    Оптимальное распределение  взаимозаменяемых  ресурсов.

Имеются m видов взаимозаменяемых ресурсов a₁, a₂, ….,a_m, используемых при выполнении n различных работ (задач). Объемы работ, которые должны быть выполнены составляют b₁, b₂, ….,b_i, b_n, единиц. Заданы числа λ_ij, указывающие, сколько единиц j-й работы можно получить из единицы i-го ресурса, а так же

 C_ij – затраты на производство j-й работы из единицы i-го ресурса. Требуется распределить ресурсы по работам таким образом, чтобы суммарная эффективность выполненных работ была максимальной ( или суммарные затраты – минимальными ).

         Данная задача называется общей  распределительной задачей. Количество  единиц i-го ресурса, которое выделено на выполнение работ j-го вида, обозначим через x_ij.

         Математическая модель рассматриваемой  задачи такова

             Минимизировать                                                             (3.3)

              при ограничениях

                                                                                    (3.4)

                                                                                                  (3.5)

          Ограничение (3.4) означает, что план всех работ должен быть выполнен полностью, а (3.5) означает, что ресурсы должны быть израсходованы целиком.

           Примером  этой задачи может  быть задача о распределении  самолетов по авиалиниям. 

2.3.2.    Задача о смесях. 

           Имеется р – компонентов, при  сочетании которых в разных  пропорциях получают разные смеси.  Каждый компонент а следовательно  и смесь, содержит q веществ. Количество k-го вещества k=1,2,…,q, входящее в состав единицы i-го компонента и в состав единицы смеси, обозначим через  а_ik и a_k соответственно.

           Предположим что a_k зависит от a_ik линейно, то есть если смесь состоит из х₁ единиц первого компонента х₂ единиц второго компонента и т.д., то

            Задано р-величин С_i характеризующих стоимость, массу или калорийность единицы i-го компонента, и q величин b_k, указывающих минимально необходимое процентное содержание k-го вещества в смеси. Обозначим через х₁,х₂,….,х_р значение компонента р-го вида, входящего в состав смеси.

            
 
 
 
 
 

 Математическая  модель этой задачи имеет такой  вид:

минимизировать                                                                     (3.6)

при ограничении

                                                                   (3.7)

         Ограничения (3.7) означает, что процентное  содержание k-го веществав единицы смеси должно быть не меньше b_k.

         К этой же модели принадлежит  так же задача определения  оптимального рациона кормления скота. 

 

2.3.3.    Задача о раскрое материалов. 

           Пусть поступает в раскрой  m различных материалов. Требуется изготовить из них k разных комплектующих изделий (комплектов) в количествах, пропорциональных величинам b₁,b₂,….,b_k (условия комплектности). Пусть каждую единицу j-го материала j=1,….,m можно раскроить n различными способами, так что при использовании i-го способа раскроя, i=1,…,n получим a_ij едениц k-го изделия. Нужно определить такой план раскроя материалов, обеспечивающий максимальное количество комплектов, если имеющийся запас j-го материала составляет a_j единиц.

           Обозначим через х_ij количество единиц j-го материала, раскраиваемых i-ым способом, а через х – общее количество изготавливаемых комплектов.

           Математическая модель задачи имеет такой вид:

           максимизировать х                                                 (3.8)

           при условиях   

                                                                                 (3.9)

                                                               (3.10)

            Условие (3.9) означает ограничение на запас j-го материала, а (3.10) – условие комплектности.

            Оптимальные балансовые модели. Рассмотрим n отраслевую балансовую модель с постоянными технологическими коэффициентами, задаваемыми матрицей затрат А= , где a_ij затраты продуктов i-ой отрасли на производство единицы продукции j-ой отрасли. Производственные мощности i-ой  отрасли ограничивают ее валовой выпуск величиной d_i, и пусть цена конечного продукта    i-ой  отрасли составляет c_i единиц.

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

           Обозначим вектор валовой продукции  всех отраслей через x=[x1,..,xn], а вектор конечного продукта y=[y1,..,yn]. Тогда y_i – объем продукции i-й отрасли, идущего на накопление.

           Между векторами x и y существует следующая связь:

           x=Ax+y,

           где Ax – продукт, расходуемый на потребление. Отсюда

           y=x[E-A], x= [E-A]^-1y

           Математическая модель этой задачи имеет вид:

           максимизировать с^Ту

           при условиях

           x=[E-A]^-1y<d, y>0;

           Кроме того в этой задаче  можно дополнительно использовать  такие, например, ограничения на  конечные продукты:

           а) y1;y2;….;yn=b1;b2;…;bn – условие комплектности;

           б)  - условие ограниченности выпуска конечного продукта.

         

2.4.    Форма записи ЗЛП. 

            Задачу линейного программирования можно сформулировать так:

максимизировать                           (3.11)

при условиях

                                                (3.12;3.13) 
 

         Ограничения 3.13 называют условиями  неотрицательности переменных. В  рассматриваемом случае все ограничения  имеют вид неравенств.

         
 
 
 
 
 
 
 
 
 

 Иногда они  могут быть смешанными, то есть неравенства и равенства:

                                            (3.14) 
 

   Если все ограничения задачи ЛП имеют вид строгих равенств

            

                                                             (3.15)

то данная форма  записи называется канонической.

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

    максимизировать   с^Тх                                                              (3.16)

    при  ограничениях                                                         (3.17)

    где А – матрица ограничений с размером ( m x n); b^m*1 – вектор – столбец свободных членов;x^n*1 – вектор переменных; с=[c1.c2……cn] – вектор (строка) коэффициентов целевой функции.

           В векторной форме ограничения  (3.14) записывают так:

                                                                (3.18)

           Допустимым множеством решения  задачи 3,11-3,13 называется множество  R(х) всех векторов х, удовлетворяющих условиям (3.12) и (3.13)

           Множество R(х) представляет собой выпуклое многогранное множество или выпуклый многогранник.

           Решение х₀ называется оптимальным, если оно удовлетворяет условию

с^Тх₀> с^Тх,  для всех x принадлежащих R(x).

           Поскольку поиск min (fx) эквивалентен поиску ax[-f(x)], то задачу ЛП всегда можно свести к эквивалентной задаче максимизации. 
 
 
 
 
 
 

         
 

2.5.    Решение задач линейного программирования симплекс-методом. 

             Симплекс метод, известный так же под названием метода последовательного улучшения плана, впервые разработал Г.Данциг в 1947г. Этот метод позволяет переходить от одного допустимого базисного решения к другому, причем так, что значения целевой функции непрерывно возрастают. В результате оптимальное решение находят за конечное  число шагов.

             Алгоритмы симплекс метода так  же позволяю установить является  ли задача ЛП разрешимой.

             Запишем ограничения задачи ЛП  в таком виде:

Пусть А1,…..,А_m – множество линейно независимых векторов.

Тогда уравнение 

                      (4.1)

определяет базисное решение х1,х2,….,х_m

           Предположим что это решение допустимо, то есть . Базис {A₁,A_m} образует m мерное пространство, а потому каждый из векторов A_m+1,..,A_m+n единственным образом выражается через базис. Если А не входит в базис, то