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

          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 единственным образом выражается через базис. Если А не входит в базис, то