В индексной строке в n-ом столбце нулевое значение. Что это означает?

По какому методу пересчитываются симплекс-таблицы?

Используется правило прямоугольника (метод жордановских преобразований).

Обязательно ли каждый раз выбирать максимальное значение из индексной строки?

Можно не выбирать, но это может привести к зацикливанию алгоритма.

В индексной строке в n-ом столбце нулевое значение. Что это означает?

Нулевые значения должны соответствовать переменным, вошедшим в базис. Если в индексной строке симплексной таблицы оптимального плана находится нуль, принадлежащий свободной переменной, не вошедшей в базис, а в столбце, содержащем этот нуль, имеется хотя бы один положительный элемент, то задача имеет множество оптимальных планов.

Свободную переменную, соответствующую указанному столбцу, можно внести в базис, выполнив соответствующие этапы алгоритма. В результате будет получен второй оптимальный план с другим набором базисных переменных.

Составим двойственную задачу к прямой задаче.

Решение двойственной задачи дает оптимальную систему оценок ресурсов.

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

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

Левая часть ограничений определяет стоимость ресурсов в теневых (альтернативных) ценах, затраченных на x_j.

1.2y₁+y₂≥1000

1.6y₁+2y₂≥1500

132y₁+14y₂ → min

y₁ ≥ 0

y₂ ≥ 0

Переменные y_j называются допустимым решением двойственной задачи. Переменные y_j называются оптимальными, если они допустимые и на них целевая функция достигает минимальное значения.

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

Из первой теоремы двойственности следует, что Y = C*A^-1.

Составим матрицу A из компонентов векторов, входящих в оптимальный базис.

Определив обратную матрицу D = А^-1 через алгебраические дополнения, получим:

Как видно из последнего плана симплексной таблицы, обратная матрица A^-1 расположена в столбцах дополнительных переменных.

Тогда Y = C*A^-1 =

Оптимальный план двойственной задачи равен:

y₁ = 0

y₂ = 1000

Z(Y) = 132*0+14*1000 = 14000

Критерий оптимальности полученного решения. Если существуют такие допустимые решения X и Y прямой и двойственной задач, для которых выполняется равенство целевых функций F(x) = Z(y), то эти решения X и Y являются оптимальными решениями прямой и двойственной задач соответственно.

Определение дефицитных и недефицитных (избыточных) ресурсов. Вторая теорема двойственности.

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

1.2*14 + 1.6*0 = 16.8 < 132

1*14 + 2*0 = 14 = 14

1-ое ограничение выполняется как строгое неравенство, т.е. ресурс 1-го вида израсходован не полностью. Значит, этот ресурс не является дефицитным и его оценка в оптимальном плане y₁ = 0.

Неиспользованный экономический резерв ресурса 1 составляет 115.2 (132-16.8).

Этот резерв не может быть использован в оптимальном плане, но указывает на возможность изменений в объекте моделирования (например, резерв ресурса можно продать или сдать в аренду).

2-ое ограничение прямой задачи выполняется как равенство. Это означает, что 2-ый ресурс полностью используется в оптимальном плане, является дефицитным и его оценка согласно второй теореме двойственности отлична от нуля (y₂>0).

Таким образом, отличную от нуля двойственные оценки имеют лишь те виды ресурсов, которые полностью используются в оптимальном плане. Поэтому двойственные оценки определяют дефицитность ресурсов.

Обоснование эффективности оптимального плана.

При подстановке оптимальных двойственных оценок в систему ограничений двойственной задачи получим:

1.2*0 + 1*1000 = 1000 = 1000

1.6*0 + 2*1000 = 2000 > 1500

Анализ устойчивости оптимального плана.

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

Чувствительность решения к изменению коэффициентов целевой функции.

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

Пусть каждое значение параметра целевой функции изменится на ∆ с_i. Найдем интервалы, при которых будет экономически выгодно использование ресурсов.

Допустимые диапазоны изменения коэффициентов в целевой функции определятся из соотношений:

1-ый параметр целевой функции может изменяться в пределах:

∆c₁^- = min [y_k/d_1k] для d_1k>0.

∆c₁⁺ = |max [y_k/d_1k]| для d_1k<0.

Таким образом, 1-параметр может быть уменьшен на 1000 или увеличен на 0

Интервал изменения равен:

(c₁ - ∆c₁^-; c₁ + ∆c₁⁺)

[1000-1000; 1000+0] = [0;1000]

Если значение c₁ будет лежать в данном интервале, то оптимальный план не изменится.

Чувствительность решения к изменению запасов сырья.

Из теоремы об оценках известно, что колебание величины b_i приводит к увеличению или уменьшению f(X).

Оно определяется величиной y_i в случае, когда при изменении величин b_i значения переменных у_i в оптимальном плане соответствующей двойственной задачи остаются неизменными.

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

Найдем интервалы устойчивости ресурсов.

Нижняя граница для: ∆b^-₁

∆b^-₁ = min[x_k/d_k1] для d_k1>0.

Таким образом, 1-ый запас может быть уменьшен на 115.2

1-ый вид ресурса в оптимальном плане недоиспользован, является недефицитным. Увеличение данного ресурса приведет лишь к росту его остатка. При этом структурных изменений в оптимальном плане не будет, так как двойственная оценка y₁ = 0. Другими словами, верхняя граница b⁺₁ = +∞

Интервал изменения равен:

(b₁ - ∆b₁^-; ∞)

[132-115.2; +∞] = [16.8;+∞]

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

∆b₂^- = min [x_k/d_k2] для d_k2>0.

∆b₂⁺ = |max [x_k/d_k2]| для d_k2<0.

Таким образом, 2-ый запас может быть уменьшен на 14 или увеличен на 96

Интервал изменения равен:

(b₂ - ∆b₂^-; b₂ + ∆b₂⁺)

[14-14; 14+96] = [0;110]

В оптимальный план не вошла основная переменная x₁, т.е. ее не выгодно использовать. Определим максимально возможное значение в рамках полученных двойственных оценок:

x₁ может изменяться в пределах:

0 ≤ ∆b₁ ≤ 14

[132-14; 132] = [118;132]

1-ое ограничение двойственной задачи выполняется как равенство. Это означает, что 1-ый ресурс экономически выгодно использовать, а его использование предусмотрено оптимальным планом прямой задачи (x₁>0).

2-ое ограничение выполняется как строгое неравенство, т.е. ресурс 2-го вида использовать экономически не выгодно. И действительно в оптимальном плане прямой задачи x₂ = 0.

Поскольку теневая (альтернативная) цена больше рыночной цены этого продукта, то выгоднее продать ресурсы по рыночным ценам.

При этом разница между ценами (2000 - 1500 = 500) показывает величину изменения целевой функции F(x) при введении дополнительной единицы x_i.

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

Величина двойственной оценки показывает, на сколько возрастает значение целевой функции F(x) при увеличении дефицитного ресурса на единицу.

Решение было получено и оформлено с помощью сервиса:

Двойственная задача линейного программирования

Вместе с этой задачей решают также:

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

Симплекс-метод

Двойственный симплекс-метод

Метод Гомори

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

Copyright © Semestr.RU