Решение оптимизационной задачи линейного программирования

Преобразованиям подвергается  вся  симплекс-таблица,  включая  E-строку,  W-

строку и столбец  решений. Получаем новую симплекс-таблицу:

|БП   |X1   |X2    |X3   |X4   |X5   |X6   |X7   |X8   |X9   |X10  |БР   |

|E    |0    |-1,5  |-2   |0    |-4,5 |-2   |0    |0    |0,5  |0    |0    |

|-W   |0    |-1    |2    |0    |-3   |2    |0    |0    |2    |0    |0    |

|X7   |1    |1     |1    |0    |0    |0    |1    |0    |0    |0    |8    |

|X8   |-0,33|0,17  |0    |0    |1,5  |1    |0    |1    |-0,17|0    |8    |

|X4   |0,33 |-0,17 |0    |1    |-0,5 |0    |0    |0    |0,17 |0    |0    |

|X10  |0    |1     |-2   |0    |3    |-2   |0    |0    |-1   |1    |0    | 
 

                                             Таблица 3. Симплекс-таблица №2.

    Мы  получили  новое  решение  (Х7,Х8,Х4,Х10)=(8,8,0,0).   Это   решение

недопустимо, так  как  в  базисе  содержится  искусственная  переменная  Х10.

Выполим очередную  итерацию. По строке –W для включения  в   базис   выбираем

переменную  X5  (т.к. –3 –  максимальное  по  модулю  отрицательное  число).

Столбец X5 становится ведущим.  По  минимальному  симплексному  отношению  (

8/1,5=5,33;  0/3=0)  для   исключения  из  базиса  выбираем  переменную  Х10.

Ведущий  элемент  равен  3.  После  проведенных  пересчетов  получаем  новую

симплекс-таблицу: 
 
 

|БП   |X1   |X2    |X3   |X4   |X5   |X6   |X7   |X8   |X9   |X10  |БР   |

|E    |0    |0     |-5   |0    |0    |-5   |0    |0    |-1   |1,5  |0    |

|-W   |0    |0     |0    |0    |0    |0    |0    |0    |1    |1    |0    |

|X7   |1    |1     |1    |0    |0    |0    |1    |0    |0    |0    |8    |

|X8   |-0,33|-0,33 |1    |0    |0    |2    |0    |1    |0,33 |-0,5 |8    |

|X4   |0,33 |0     |-0,33|1    |0    |-0.33|0    |0    |0    |0,17 |0    |

|X5   |0    |0,33  |-0,67|0    |1    |-0,67|0    |0    |-0,33|0,33 |0    | 
 

                                             Таблица 4. Симплекс-таблица №3. 

                4.5. ВТОРОЙ ЭТАП ДВУХЭТАПНОГО СИМЛЕКС-МЕТОДА 

    Итак, как  видно из Таблицы 4, все  искусственные   переменные  вышли  из

базиса, искусственная  целевая  функция  обнулилась  –  значит,  первый  этап

двухэтапного  симплекс-метода   закончен,   найдено   начальное   допустимое

решение: (Х1,X2,X3,X4,X5,X6) = (0,0,0,0,0,0), целевая  функция  Е=0.  Теперь

переходим  к  реализации  второго  этапа:  вычеркиваем  из  таблицы   строку

искусственной целевой  функции и столбцы искусственных  переменных; над  новой

таблицей выполняем  обычные  процедуры  симплекс-метода,  а  именно:  ведущий

столбец определяется также, как и для первого этапа  двухэтапного  симплекс-

метода, единственное различие состоит в  том,  что  максимальный  по  модулю

отрицательный коэффициент  находим по Е-строке целевой функции. Расчет  ведем

до тех пор, пока в Е-строке не останется отрицательных  коэффициентов: 
 
 

|БП   |X1   |X2    |X3    |X4    |X5    |X6    |X7    |X8    |БР   |

|E    |0    |0     |-5    |0     |0     |-5    |0     |0     |0    |

|X7   |1    |1     |1     |0     |0     |0     |1     |0     |8    |

|X8   |-0,33|-0,33 |1     |0     |0     |2     |0     |1     |8    |

|X4   |0,33 |0     |-0,33 |1     |0     |-0,33 |0     |0     |0    |

|X5   |0    |0,33  |-0,67 |0     |1     |-0,67 |0     |0     |0    | 
 

                                             Таблица 5. Симплекс-таблица №4.

    Наше начальное  допустимое решение не является  оптимальным, так как в Е-

строке содержатся отрицательные коэффициенты. Определим  по  Е-строке  новую

переменную для  включения в базис. Это переменная X3, т.к. –5 –  максимальное

по модулю отрицательное  число (коэффициент Е-строки при  переменной X6  также

равен –5, поэтому  выбрали любую из этих переменных,  например  X3).  Столбец

X3 становится ведущим.  По  минимальному  симплексному  отношению  (  8/1=8;

8/1=8)  для  исключения  из  базиса  выбираем  переменную  Х7   (симплексное

отношение при переменной X8 также равно 8, поэтому  выбрали  любую  из  этих

переменных). Ведущий  элемент равен 1. После проведенных  пересчетов  получаем

новую симплекс-таблицу:

|БП   |X1   |X2    |X3    |X4    |X5    |X6    |X7    |X8    |БР   |

|E    |5    |5     |0     |0     |0     |-5    |5     |0     |40   |

|X3   |1    |1     |1     |0     |0     |0     |1     |0     |8    |

|X8   |-1,33|-1,33 |0     |0     |0     |2     |-1    |1     |0    |

|X4   |0,67 |0,33  |0     |1     |0     |-0,33 |0,33  |0     |2,67 |

|X5   |0,67 |1     |0     |0     |1     |-0,67 |0,67  |0     |5,33 | 
 

                                             Таблица 6. Симплекс-таблица №5.

    Итак, как  видно из таблицы, некоторые  из искомых переменных , а  именно

Х3, Х4 и Х5, начали расти, что привело и к росту  значения целевой функции  –

из нулевого значения она приняла значение 40. Это можно  объяснить  тем,  что

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

области допустимых решений,  причем  в  этой  соседней  точке  рост  целевой

функции максимален. Однако в Е-строке есть  еще  отрицательный  коэффициент,

поэтому продолжим  расчеты.

    Определим  по Е-строке новую  переменную  для  включения  в  базис.  Это

переменная X6,  т.к.  –5  –  максимальное  по  модулю  отрицательное  число.

Столбец X6 становится ведущим.  По  минимальному  симплексному  отношению  (

0/2=0) для исключения  из  базиса  выбираем  переменную  Х8.  Получаем  новую

симплекс-таблицу:

|БП   |X1   |X2    |X3    |X4    |X5    |X6    |X7    |X8    |БР   |

|E    |1,67 |1,67  |0     |0     |0     |0     |2,5   |2,5   |40   |

|X3   |1    |1     |1     |0     |0     |0     |1     |0     |8    |

|X6   |-0,67|-0,67 |0     |0     |0     |1     |-0,5  |0,5   |0    |

|X4   |0,44 |0,11  |0     |1     |0     |0     |0,17  |0,17  |2,67 |

|X5   |0,22 |0,55  |0     |0     |1     |0     |0,33  |0,33  |5,33 | 
 

                                             Таблица 7. Симплекс-таблица №6.

       Так  как  все  коэффициенты  E-строки  таблицы  7  положительные,  то

оптимальное решение  найдено. Оптимальный план состоит  в том, чтобы  токарный

станок работал  над деталями типа 3 8 часов за смену,  то  есть  всю  рабочую

смену, и не работал  над деталями типа 1 и 2  вообще.  Станок-автомат  должен

работать за смену 2,67 часа над деталями типа 1 и  5,33  часа  над  деталями

типа 2 и не должен работать над деталями типа 3. При  этом  за  смену  будет

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

40 комплектов. Ни  один из станков не будет  простаивать. 
 
 

                    5. АНАЛИЗ МОДЕЛИ НА ЧУВСТВИТЕЛЬНОСТЬ 

      В   окончательной  симплекс-таблице,  содержащей  оптимальное  решение,

содержится не только само оптимальное решение, но и  другая  информация.  На

основе   последней   симплекс-таблицы    решаются    задачи    анализа    на

чувствительность - определение влияния изменений  в  исходных  данных  задачи

на  оптимальное  решение.  Интерпретация  симплекс-таблицы   и   анализ   на

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

задачи. В нашем  случае мы имеем дело с задачей  о распределения  ресурсов,  а

именно ресурсов времени. 
 

                            5.1. СТАТУС РЕСУРСОВ 
 

      По  статусу  ресурсы  делятся   на  дефицитные  и  недефицитные.   Если

некоторый ресурс при  реализации оптимального  плана  расходуется  полностью,

он называется дефицитным, если не полностью - недефицитным.

      Статус  ресурсов определяется по значениям  остаточных переменных  Х7  и

Х8,  введенных  в  исходную  систему  ограничений  для   приведения   ее   к

стандартной форме. Эти переменные означают остатки  ресурсов  при  реализации

оптимального  плана.  Ни  одна  из  остаточных  переменных   не   входит   в

оптимальное  решение,  т.е.  их  значения  равны  нулю.  Это  означает,  что

токарный станок  и  станок-автомат  использовались  все  выделенное  для  их

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

ресурсами.  Увеличение  запасов  дефицитных  ресурсов  позволяет   увеличить

значение целевой  функции, а снижение  этих  запасов  приводит  к  уменьшению

целевой функции. 

                           5.2. ЦЕННОСТЬ РЕСУРСОВ 

    Ценность  ресурса - это величина увеличения  значения целевой функции   при

увеличении запасов  данного ресурса на единицу (или  соответственно  величина

уменьшения целевой  функции при снижении  запаса  ресурса).  Другое  название

этой величины - теневая (скрытая) цена. В симплекс-таблице,  соответствующей

оптимальному решению, теневые цены  содержатся  в  E-строке  и  представляют

собой  коэффициенты  при  остаточных  переменных,  соответствующим  остаткам

ресурсов. Таким образом, ценность времени работы токарного  станка  и станка-

автомата соответственно равна по 2,5  комплекта  деталей.  Другими  словами,

если запас времени  работы токарного станка увеличить (уменьшить) на  1  час,

то количество производимых комплектов  деталей  увеличится  (уменьшится)  на

2,5 единицы, и, аналогично, если увеличить (уменьшить) время  работы  станка-

автомата станка на 1 час, то количество комплектов  увеличится  (уменьшится)

на 2,5 комплекта. 
 

   5.3. АНАЛИЗ  НА ЧУВСТВИТЕЛЬНОСТЬ К ИЗМЕНЕНИЯМ  ПРАВЫХ ЧАСТЕЙ ОГРАНИЧЕНИЙ 
 

    Для анализа  решения на  чувствительность  к  изменению  запасов   времени

работы станков (без  изменения других исходных  данных  задачи)  используются

коэффициенты из столбцов остаточных переменных Х7 и  Х8  (соответственно  для

токарного станка и  станка-автомата) в последней симплекс-таблице.  Например,

если запас времени  работы токарного станка  изменился  на  d  часов  и  стал

равен 8+d  часов,  то  новое  оптимальное  решение  находится  по  следующим

формулам:

                        Х3 = 8 + 1*d

                        X6 = 0 – 0,5*d

                        X4 = 2,67 + 0,17*d

                        X5 = 5,33 + 0,33*d

                        E = 40 + 2,5*d

    При   составлении  этих  формул  использовали  коэффициенты  из  столбца

остаточной переменной Х7 в последней  симплекс-таблице.  По  содержательному

смыслу эти формулы  означают изменение времени работы  токарного  станка  или

станка-автомата  над  каждой  из  деталей  в  сутки  при  изменении   запаса