Математическое моделирование

     x₂₁ + x₂₂ + … + x_2n £ Т   

          _{…………………………………….}

     x_m1 + x_m2 + … + x_mn £  Т 

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

     a₁₁x₁₁ + a₂₁x₂₁ + … + a_m1x_m1 = b₁

     a₁₂x₁₂ + a₂₂x₂₂ + … + a_m2x_m2 = b₂   (8)      x_ij³0,   i =1,m;   j = 1,n.

          _{…………………………………………..}

     a_1mx_1m + a_2mx_2m + … + a_mnx_mn = b_n 

Затраты на производство всей продукции выразятся функцией:

f = с₁₁x₁₁ + с₁₂x₁₂ + … +с_mnx_mn = ååс_ijх_ij. (9).

Найти такое решение Х = (х₁, х₂, …, х_mn), удовлетворяющее условиям (6), (7), (8), при котором функция (9) принимает минимальное значение. 

2.4.   Транспортная задача. 

      Пусть имеется m пунктов отправления А₁, А₂, …, А_m, в которых сосредоточены запасы однородного товара (ресурса), в количествах соответственно а₁, а₂, …, а_m (а_i, i  = 1,m). И n пунктов назначения (или потребления) этого товара B₁, B₂, …, B_n, которые хотят получить этот товар в количествах соответственно b₁, b₂, …, b_n (b_j, j = 1, n). Известны затраты на перевозку одной единицы товара из i-того пункта отправления в каждый j-тый пункт назначения c_ij - стоимость перевозки единицы товара.

      Требуется составить такой план перевозок, чтобы:

- все  грузы из всех пунктов отправления  были вывезены;

- заявки  всех пунктов назначения были  бы удовлетворены;

- суммарные  затраты на перевозку были  бы минимальны.

Решение:   Обозначим x_ij – количество товаров, отправленных от i-ого производителя к j-ому потребителю. Общая стоимость всех перевозок запишется следующей функцией:

f = c₁₁x₁₁ + c₁₂x₁₂ + … +c_mnx_mn =åå c_ijx_ij. (10).

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

          _n

      åx_ij £  a_i, i = 1, m;

       ^j=1

      _m

     å x_ij ³ b_j, j = 1, n.

      ⁱ⁼¹

      Если  предположить, что общий объём  поставляемых товаров равен общему объёму потребления, то есть имеет место  следующее равенство: 

                                                                                            _{m              n}            

  å a_i = å b_j  ,

                                                                                                                                          ^{i=1           j=1} 

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

Необходимо  минимизировать функцию (10) при следующих  условиях:  

                                                                                                                             _n   

      å x_ij = a_i, i = 1, m;

           ^j=1

      _m

     å x_ij = b_j, j = 1, n;

     ⁱ⁼¹

     x_ij ³ 0. 
 

§ 3. Общая постановка задачи линейного  программирования. 

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

      Дана  система m линейных уравнений и неравенств с n неизвестными:

      a₁₁x₁ + a₁₂x₂ + … + a_1nx_n £ b_1,

     a₂₁x₁ + a₂₂x₂ + … + a_2nx_n £ b_2,   

          _{…………………………………………..}

       a_k1x₁ + a_k2x₂ + … + a_knx_n £ b_{k  ,}

         a_k+1,1x₁ + a_k+1,2x₂ + … + a_k+1,nx_n = b_k+1, 

          _{…………………………………………..}

     a_m1x₁ + a_m2x₂ + … + a_mnx_n = b_m.

        x_j ³ 0, j = 1, n.  

и линейная целевая функция:

(2)   F = с₁x₁ + с₂x₂ + … +с_nx_n

      Необходимо  найти такое решение системы (1) Х = (х₁, х₂, …, х_n), при котором линейная функция (2) принимает максимальное (минимальное) значение. Система (1) называется системой ограничений и в общей форме включает в себя как равенства, так и неравенства. Функция (2) называется линейной функцией, линейной формой, целевой функцией или функцией цели. Она может стремиться как к максимуму, так и к минимуму.

      Более коротко ЗЛП в общей форме  можно представить в виде:

                                              _n

                       F = å c_jx_j  ® max (min),  при следующих условиях:

                             ^j=1

        _n   

      å a_ijx_j   £ b_i, (i = 1, k)

      ^{j =1}

       _n

      å a_ijx_j = b_i, (i = k+1, m)

      ^{j =1}

     x_j ³ 0, (j = 1, n)  

      Вектор  Х = (х₁, х₂, …, х_n), удовлетворяющий системе ограничений (1) называется допустимым решением (или планом) ЗЛП.

      Оптимальным решением (оптимальным планом) ЗЛП  называется решение Х* = (х₁^*, х₂^*, …, х_n^*), удовлетворяющее (1), при котором линейная функция (2) принимает оптимальное значение (максимум или минимум).

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

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

      Разнообразие форм ЗЛП затрудняет исследование их общих особенностей и создание общих методов для их решения. Поэтому необходимо знать способ сведения любой ЗЛП к наиболее простой и удобной для исследования форме – канонической.

      Любую форму ЗЛП можно  привести к канонической форме. Рассмотрим, как это делается:

1) Переход от минимизации к максимизации.

      В исходной задаче целевая функция  F = с₁x₁ + с₂x₂ + …+ с_nx_n ® min. Умножим целевую функцию на (-1), получим

                                                                          - F = - с₁x₁ - с₂x₂ - … - с_nx_n ® max.

2) Обращение неравенства в равенство.

      Если  имеется неравенство типа a_i1x₁ + a_i2x₂ + … + a_inx_n £ b_i, то его заменим двумя эквивалентными условиями, введя новую неотрицательную переменную x_n+1 ³ 0:

      a_i1x₁ + a_i2x₂ + … + a_inx_n + x_n+1 = b_i

     x_n+1³ 0

      Если  имеем неравенство типа a_i1x₁ + a_i2x₂ + … + a_inx_n ³ bi, то его заменяем уравнением, введя новую неотрицательную переменную x_n+1 ³ 0 со знаком ”- ”:

      a_i1x₁ + a_i2x₂ + … + a_inx_n - x_n+1 = b_i

     x_n+1 ³ 0

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

3) Переход от переменных, не имеющих ограничений, к неотрицательным переменным.

      Предположим, нет ограничений на переменную x_i. Тогда делаем замену переменной x_i = x_i’- x_i” и добавим два ограничения x_i’³ 0 и  x_i” ³ 0.