3. Переход к «нехудшему» опорному плану.

Дата: 2025-06-02; Просмотры: 9

Оценка:

0.00 из 5.00 — оценок

Скачиваний: 0

Скачать

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

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

Симплекс-метод, впервые разработал Г.Данциг в 1947 г, данный метод известен также под названием метода последовательного улучшения плана. Его суть заключается в последовательном переборе угловых точек области допустимых решений, а алгоритмы позволяют установить, является ли данная ЗЛП разрешимой.

Для того чтобы построить опорный план ЗЛП при помощи симплексного метода, необходимо привести ЗЛП к предпочтительному виду (задача должна иметь канонический вид и в каждом ограничении системы должна быть переменная, входящая в него с коэффициентом 1 и с коэффициентом 0 во все остальные ограничения, именно эти переменные выбирают в качестве базиса).

Привести ЗЛП к предпочтительному виду можно следующими методами:

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

Например:

max Z = 2x₁ + 3x₂ – x₃

Можно свести к виду:

max Z = 2x₁ + 3x₂ – x₃

х₁ и х₂ – базисные переменные, х₃ – свободная.

Опорный план следующий: Х^* = (11,5; 14; 0)

2. Добавлением балансовых переменных (х _t), удовлетворяющих описанному выше условию (+ условию неотрицательности) и входящих в целевую функцию с коэффициентом 0. Данное правило используется для задач, содержащих в системе ограничений неравенства типа «≤». При этом, вводимые в систему ограничений переменные, принимаются в качестве базисных.

Например:

max Z = x₁ – x₂

Предпочтительный вид будет следующий:

max Z = x₁ – x₂ + 0∙x₃ + 0∙x₄

х₃ и х₄ – базисные переменные, х₁ и х₂ – свободные.

Опорный план следующий: Х^* = (0; 0| 5; 4)

Вертикальная черта отделяет исходные переменные задачи от введенных.

3. Сведением к М-задаче. А именно, необходимо ввести искусственный базис (v_s): переменные, удовлетворяющих описанному выше условию (+ условию неотрицательности) и входящих в целевую функцию с коэффициентом ±М, где М – очень большое число, знак «+» при решении задачи на min, знак «-» при решении задачи на max. Данное правило используется для задач, содержащих в системе ограничений неравенства типа «≥».

Например:

max Z = x₁ – x₂

Предпочтительный вид будет следующий:

max Z = x₁ – x₂ – M∙v₁ – M∙v₂

v₁ и v₂ – базисные переменные, х₁ и х₂ – свободные.

Опорный план следующий: Х^* = (0; 0| 5; 4)

M-задачу по другому называют задачей с искусственным базисом.

При решении М-задачи симплекс-методом используют следующие теоремы:

1. Если в оптимальном плане Х^* = (х₁, х₂, ..., х _n| v₁, v₂, ..., v_m) M-задачи все искусственные переменные равны 0, т.е. v_S = 0, то план Х^* = (х₁, х₂, ..., х _n) является оптимальным планом исходной задачи.

2. Если в оптимальном плане М-задачи хотя бы одна из искусственных переменных отлична от нуля, то исходная задача не имеет допустимых планов, т.е. ее условия несовместны.

Построение оптимального плана симплекс методом происходит в 3 этапа:

1. Построение начального опорного плана;

2. Проверка плана на оптимальность;

3. Переход к «нехудшему» опорному плану.

1. Построение начального опорного плана

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

max(min) Z=c₁x₁+ c₂x₂+…+ c_nx_n

X= (x_1, x_2, … x_n) (1)

Известно, что оптимальное решение (если оно существует) достигается в одной из опорных точек (вершин ОДР), где по крайней мере k = n – m из переменных не равны 0. Выберем некоторые k переменных в качестве свободных и выразим остальные m базисных переменных.

Пусть базисными являются x₁, x₂, …, x_m. Тогда свободными являются x_m+1, x_m+2, …, x_n. Выразим базисные переменные, через свободные:

(2)

Если положить все свободные переменные x_m+1, x_m+2, …, x_n равными 0, получим:

… ;

Это решение может быть допустимым или недопустимым. Оно будет допустимым, если все свободные члены … неотрицательны. Предположим, что это условие выполнено, тогда полученное решение является опорным планом. Т.о. опорным планом называется любое допустимое решение ЗЛП.

2. Проверка плана на оптимальность

Выполним некоторые преобразования: Пусть исходная ЗЛП имеет канонический вид (1). Подставим выражения базисных переменных (2) в целевую функцию. Получим:

Введем обозначения:

где

– вектор коэффициентов целевой функции;

– вектор-столбец свободных членов;

– вектор-столбец коэффициентов при переменных х_j.

Таким образом задача исходная задача преобразуется в следующую:

X= (x_1, x_2, … x_n)

(3)

Такую задачу можно записать в виде симплексной таблицы:

В симплексной таблице

- Последнюю строку в таблице называют индексной строкой (или строкой целевой функции);

- Число – значение целевой функции для начального опорного плана;

- Числа – называют индексными оценками свободных переменных.

Теорема (признак оптимальности опорного плана):

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

Пример:

Некоторое предприятие выпускает столы и стулья. На изготовление одного стула стоимостью 1 у.д.е. требуется 1 куб.м сосны и 1 куб.м дуба, а для производства стола стоимостью 4 у.д.е. требуется 2 куб.м сосны. На складе имеется 100 куб.м сосны и 40 куб.м дуба.

Решение:

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

Составляем симплексную таблицу (х₃ и х₄ - базисные):

X= (0; 0| 100; 40)

План не оптимальный так как есть индексные оценки отрицательные.

Переход к не худшему плану.

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

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

Для того, чтобы определить индексную строку необходимо найти для каждой строки наименьшее симплексное отношение: , где j₀ – разрешающий столбец.

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