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

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

5.6.4 Выполнение теоремы об оценке

В условиях задачи сказано, что недельный рацион должен содержать не менее 4, но не более 6 г кальция; не менее 110 г белка; не более 25 г клетчатки; и этой смеси должно быть ровно 500 г. Предположим, что эти величины могут меняться. Чтобы узнать, на сколько при этом изменится оптимальная стоимость рациона, в соответствии с третьей теоремой двойственности надо воспользоваться теневыми ценами y_1-5, которые соответствуют ограничениям прямой задачи. Но для этого вначале следует провести анализ устойчивости теневых цен.

Обозначим изменение минимального содержания кальция _∆b₁;  максимального - ∆b₂; минимального содержания белка - _∆b₃; максимального содержания клетчатки - _∆b₄, а массы смеси – _∆b₅ (все эти величины измеряются в граммах). Теперь в таблице 17 вместо свободных членов (b₁, b₂; b₃; b₄; b₅) следует подставить свободные члены (b₁ + ∆b₁, b₂ + ∆b₂; b₃ + ∆b₃; b₄ + ∆b₄; b₅ + ∆b₅), т.е. (4 + ∆b₁, 6 + ∆b₂; 44 + ∆b₃; 25 + ∆b₄; 0,5 + ∆b₅). 

Однако, если мы просто заполним диапазон ячеек электронной таблицы D3:D7 этими выражениями, программа Microsoft Excel не сможет осуществить никаких вычислений над ними, поскольку эти ячейки станут текстовыми. Чтобы избежать этого, вставим перед столбцом Е еще пять столбцов. Теперь столбец свободных членов будет занимать 6 столбцов электронной таблицы (D, E, F, G, H, I). В столбце E запишем коэффициент, который будет умножен на _∆b₁, в столбце F – коэффициент при _∆b₂, и т.д., в столбце I – коэффициент при _∆b₅, а в D – то слагаемое в выражении для свободного члена, которое ни на что не умножается (т.е. прежнее значение свободного члена). Результат представлен в таблице 22. 

Теперь новые значения свободных членов, т.е. новый столбец B, записанный в диапазоне D3:I7 электронной таблицы, необходимо подвергнуть тем же линейным преобразованиям, которым подвергались ограничения прямой задачи в таблицах 17-19. Для этого нужно выделить диапазон ячеек D8:D37 и скопировать его на диапазон Е8:I 37. В результате этого новые столбцы симплексных таблиц будут пересчитаны по тем же формулам, что и столбец D. Результаты вычислений приведены в последней строке таблицы 22 и в таблице 23. Заголовки столбцов в таблице 23 отредактированы.

Таблица 22 – Подготовка исходной симплексной таблицы к проведению анализа устойчивости двойственных оценок

Из таблицы 23 видно, что во второй симплексной таблице теперь базисная искусственная переменная у₁ = 3,511 + _∆b₁ - 0,011_∆b₃ (см. строку 10 электронной таблицы); а не

3,511, как в таблице 17. Базисная переменная x₅ = 5,511 + ∆b₂ - 0,011∆b₃ (см. строку 11 электронной таблицы); а не 5,511, как в таблице 17, и т.д. 

Оптимальный план прямой задачи примет вид Х^* = (0,011 - 0,011∆b₃ + ∆b₅; 0,489 + + 0,011∆b₃; 0; 0,711 - ∆b₁ - 4,211∆b₃ + 380∆b₅; 1,289 + ∆b₂ + 4,211∆b₃ - 380∆b₅; 0; 15,222 -

- 0,022∆b₃ + ∆b₄), оптимум будет равен 7,378 + 0,122∆b₃ + 4∆b₅. 

Таблица 23 – Анализ устойчивости двойственных оценок

Полученный ответ будет иметь смысл лишь в том случае, если значения всех переменных будут неотрицательны (т.е. последняя таблица будет допустимой). Поэтому необходимо проверить знак базисных переменных x₁,  x₅,  х₂,  x₇,  х₄; т.е. определить, при каких изменениях свободных членов они будут неотрицательны. Составим систему неравенств:

0,011 - 0,011∆b₃ + ∆b₅ ≥ 0

0,489 + 0,011∆b₃ ≥ 0

0,711 - ∆b₁ - 4,211∆b₃ + 380∆b₅ ≥ 0

1,289 + ∆b₂ + 4,211∆b₃ - 380∆b₅ ≥ 0

15,222 - 0,022∆b₃ + ∆b₄ ≥ 0

Чтобы решить эту систему, вначале предположим, что меняется только минимальное содержание кальция, т.е. первый свободный член. Тогда ∆b₂  = ∆b₃  = ∆b₄ = ∆b₅ = 0, и система примет вид:

0,011 ≥ 0

0,489 ≥ 0

0,711 - ∆b₁ ≥ 0

1,289 ≥ 0

15,222 ≥ 0

Отсюда _∆b₁ ≤ 0,711. В первоначальном варианте исходных данных b₁ = = 4. Следовательно, двойственная оценка y₁ = 0 будет устойчивой лишь при норме мини-

мального содержания кальция от любого значения