Задача линейного программирования (симплекс-метод)

Все вычисления 5 этапа производятся - в таблице Гаусса.

6. этап. Записываем опорное решение.

2.2 Переход от найденного опорного решения к лучшему опорному решению (II часть симплекса).

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

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

Правило подсчета оценочной строки

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

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

После составления симплекс-таблицы  освобождаются от ненужных оценок. При решении задачи на максимум ненужными  являются отрицательные оценки, а  при решении задачи на минимум  ненужными будут положительные  оценки.

От ненужных оценок освобождаются  с помощью преобразований Жордана-Гаусса по специальному правилу, которое гарантирует, что свободные члены не изменят  своих положительных знаков и  число ненужных оценок не увеличится.

Правило выбора ведущего элемента

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

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

2. Ведущая строка выбирается  по наименьшему положительному  отношению свободных членов (3 столбец)  и соответствующим коэффициентам  ведущего столбца.

3. Ведущий элемент выбирается  на пересечении ведущего столбца и ведущей строки.

Используя данное правило выбора ведущего элемента, производят шаги методом  Жордана - Гаусса до тех пop, пока не освободятся от всех ненужных оценок или установят неограниченность целевой функции.

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

х₁, х₂≥0

Z(x)=2x₁+5x₂→max

Решение.

1 этап не нужен, так как модель уже есть.

2 этап. Приводим задачу к каноническому виду. Для этого в ограничения-неравенства вводим неотрицательные балансовые переменные х₃, х₄, х₅. Балансовые переменные входят в целевую функцию Z(x) с нулевыми коэффициентами, в результате получим:

x_j≥0,

Z(x)=2x₁+5x₂+0 x₃+0x₄+0 x₅→max

3-й  этап не нужен, т.к. балансовые переменные одновременно являются базисными.

4-й  этап не выполняем, т.к. все свободные члены положительны.

5-й  этап не нужен, т.к. не делали 4-й этап.

6-й  этап. Записываем начальное опорное решение:

_опор={0,0,40,31,50}.

II часть симплекса.

 

 

Нет отрицательной  оценки

 

По последней симплекс-таблице  записываем оптимальное решение. Для  этого базисные переменные, указанные  в первом столбце, приравниваем к  числам, стоящим в столбце «план». Все остальные переменные являются свободными, они приравниваются к  нулю. Окончательно оптимальное решение  имеет вид: ={5,7,0,0,11}, при этом максимальное значение целевой функции Z_max=45.

2.3 Метод искусственного базиса

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

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

Исходная  задача

x_j≥0, ; b_i≥0,

Расширенная задача