Теорема. (о дополняющей нежесткости )

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

Условия (1), (2) называются условиями дополняющей  нежесткости. Из них следует если какое-либо ограничение одной из задач ее оптимальным планом обращается в строгое неравенство, то соответствующая компонента оптимального плана двойственной задачи должна равняться нулю если же какая-либо компонента оптимального плана одной из задач положительна, то соответствующее ограничение в двойственной задаче ее оптимальным планом должно обращаться в строгое равенство.

     Экономически  это означает, что если по некоторому оптимальному плану  производства расход i -го ресурса строго меньше его запаса , то в оптимальном плане соответствующая двойственная оценка единицы этого ресурса равна нулю. Если же в некотором оптимальном плане оценок его i -я компонента строго больше нуля, то в оптимальном плане производства расход соответствующего ресурса равен его запасу. Отсюда следует вывод двойственные оценки могут служить мерой дефицитности ресурсов. Дефицитный ресурс (полностью используемый по оптимальному плану производства) имеет положительную оценку, а ресурс избыточный (используемый не полностью) имеет нулевую оценку.

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

 
 
 
 
 
 
 
 

2. ПРАКТИЧЕСКАЯ  ГЛАВА.

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

На  предприятии имеется возможность  выпускать n видов продукции П_j ( ). При её изготовлении используются ресурсы Р₁, Р₂ и Р₃. Размеры допустимых затрат ресурсов ограничены соответственно величинам b₁, b₂ и b₃. Расход i-го ( ) вида ресурса, который идёт на изготовление единицы продукции j-го вида составляет a_ij единиц. Цена единицы продукции j-го вида равна с_j ден. ед. Требуется симплексным методом найти план выпуска продукции по видам с учётом имеющихся ограниченных ресурсов, который обеспечивал бы предприятию максимальный доход. Необходимые числовые данные приведены в таблице.

 
 
 

Решение: 

Представим исходные данные в виде таблицы (матрицы планирования: табл.1). 
 

Таблица 1.

 

Условные обозначения:

Хj – количество j-го вида продукции (j = 1, 4), которую планирует выпускать предприятие, ед.

Сj – доход, который будет получен при выпуске каждой единицы продукции j-го вида (j = 1,4) денеж. ед.

bi – запасы сырья i-го  вида (I = 1,3), ед.

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

2.2 Составим математическую модель задачи.

Доход, который  может получить предприятие, составит:

Z = 11Х₁ + 6Х₂ + 9Х₃ + 6Х₄         max

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

2Х₁ + 2Х₂ + 3Х₃ ≤ 20

3Х₁ + Х₂ + Х₃ + 2Х₄ ≤ 37

            Х₂ + Х₃ + Х₄  ≤ 30

Хj  ≤ 0 (j= 1,4)  

3.   Каноническая форма записи условий задачи:

система неравенств переводится в систему уравнений путем введения в каждое неравенство слева от знака дополнительной неотрицательной переменной.

      В целевую функцию балансовые переменные также вводят с коэффициентом Cj = 0, (j = 5,7).

      Экономический смысл балансовых переменных заключается в том, что они равны остаткам неиспользованных ресурсов. На размер дохода эти остатки не влияют, поэтому Cj = 0.

      В канонической форме задача имеет  вид:

Z = 11Х₁ + 6Х₂ + 9Х₃ + 6Х₄ + 0 х Х₅ + 0 х Х₆ + 0 хХ₇         max

2Х₁ + 2Х₂ + 3Х₃  +  Х₅ = 20

3Х₁ + Х₂ + Х₃ + 2Х₄  + Х₆ = 37

 Х₂ + Х₃ + 4Х₄  + Х₇ = 30

Хj  ≥ 0 (j= 1,7)  

2.4 Система ограничений в векторной форме:

А₁Х₁ + А₂Х₂ +А₃Х₃ + А₄Х₄ + А₅Х₅ + А₆Х₆ + А₇Х₇ = Ао, где: 

 

Единичные вектора А₅, А₆, А₇ берем в качестве базиса первоначального опорного плана, который будет следующим:

Хо = (0; 0; 0; 0; 20; 37; 30) 

Переменные  Х₅, Х_6, Х₇ – это базисные неизвестные.

Свободные неизвестные Х₁, Х₂, Х₃, Х₄ приравниваем к нулю. Тогда значение целевой функции в опорном плане равно:

Z(Хо) = 11х 0 + 6 х 0 + 9 х 0 + 6 х 0 + 0 х 20 + 0 х 37 + 0 х 30 = 0 

2.5 Составление симплексной таблицы (табл. 2).

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

I-я итерация.

      Оценочная (индексная) строка заполняется по формулам:

          п

Ñо = å Сб х Ао = 0 х 20 + 0 х 37 + 0 х 30 = 0

          j=1

Ñj = Zj – Cj =  å Аj х Cбi – Cj;

Ñ₁ = (0 х 2 + 0 х 3 + 0 х 0) – 11 = -11

Ñ₂ = (0 х 2 + 0 х 1 + 0 х 1) – 6 = - 6

Ñ₃ = (0 х 3 + 0 х 1 + 0 х 1) – 9 = - 9

………………………………..

Ñ₇ = (0 х 0 + 0 х 0 + 0 х 1) – 0 = 0 
 
 
 
 

  Таблица 2.

 

В оценочной  строке (I-я итерация) все оценки - отрицательные числа. Для задач, решаемых на максимум целевой функции, план считается оптимальным, если все оценки оценочной строки – положительные числа. Следовательно, опорный план – неоптимальный. Из отрицательных оценок выбирается максимальная по модулю:

ê- 11 ½>½ - 9½>½- 6½® ½- 11½= max

Столбец А₁, в котором находится эта оценка, будет разрешаемым столбцом.

Находим минимальное симплексное отношение. Симплексное отношение – это  отношение элементов столбца  Ао к соответствующим элементам  разрешающего столбца. Не берутся во внимание отношение к отрицательным компонентам вектора и к нулю (на ноль делить нельзя).

Q –  min   Ао   = min  20  ; 37  = min (10; 12,3) = 10

                А₁                2     3 

Так как  минимум соответствует  Q₁₁, то данный элемент будет разрешающим

( Q₁₁ = 2), а вся первая строка – разрешающей. В базис вводится переменная Х₁ (столбец А₁) вместо переменной Х₅ (столбец А₅).

Вся первая строка делится на   Q₁₁ = 2. Остальные элементы таблицы, включая строку (m+1) пересчитывают по формулам исключения (правилу четырехугольника).

Заполняем новую таблицу (II-я итерация).

Перерасчет  элементов разрешающего столбца (результаты вносим в столбец А5):

1: 2 = 0,5;  - (3 : 2) = - 1,5;  0 : 2 = 0;  - ((-11) : 2) = 5,5

      Перерасчет  элементов разрешающей строки:

20: 2 = 10;  2 : 2 = 1;  3 : 2 = 1,5;  0 : 2 = 0; 0 : 2 = 0; 0 : 2 = 0; 

      Для остальных элементов таблицы:

37 –  20 х 3 = 7;   30 – 20 х 0  = 30;   1 – 3 х 2 = - 2;   1 – 0 х 2  = 1;

             2                         2                              2                       2 

- 6 –  (-11) х 2 = 5;    1 -  3 х 3 = - 3,5;   1 – 0 х 3 = 1;   - 9 – (-11) х 3 = 7,5;

              2                             2                           2                        2