Отыскание опорного и оптимального решения ЗЛП с использованием табличного алгоритма с заменой базисных переменных

Алгоритм составления симплексных таблиц (СТ), рассмотрим на примере решения задачи отыскания max.

Пример 2.6

Линейная функция:

F=2x₁+3x₂→max

Система ограничений

x₁+3x₂≤18

2x₁+x₂≤16

x₂≤5

3x₁≤21

x₁, x₂≥0

1. Приведем эту систему к каноническому виду, введя дополнительные переменные х₃, х₄, х₅, х₆:

х₁+3х₂+х₃=18

2х₁+х₂+х ₄=16

х₂+х₅=5

3х₁+х₆=21

Целевую функцию представим в виде:

F-2x₁-3x₂=0;

2. Заполняем первую симплексную таблицу: в ней х₃, х₄, х₅, х₆ – основные переменные (базис). Последняя строка называется оценочной.

Таблица №1.

←разрешающая строка

↑

разрешающий столбец

3. Проверяем выполнение критерия функции на max – первый опорный план не оптимальный, так как в F коэффициенты при x₁ и x₂ < 0

4. Выбираем наибольший по модулю отрицательный коэффициент F, который определяет разрешающий столбец.(второй столбец)

5. Делим свободные члены на коэффициенты разрешающего столбца, определяем оценочные отношения. И выбираем строку в качестве разрешающей, где это отношение минимальное min {6,16,5,∞}=5. На пересечении разрешающего столбца и разрешающей строки находиться разрешающий элемент a₂₃ = 1.

Для построения таблицы №2 в качестве основной переменной мы выбираем х₂, так как она образует разрешающей столбец таблице 1.

Переход к новому плану осуществляется пересчетом симплексной таблице (СТ) методом Жордана Гаусса.

Таблица №2.

← разрешающая строка

↑

разрешающий столбец

Построение 2^ой таблицы:

1)Заменим переменные в базисе с х₅ на х_2.

2)Делим элементы разрешающей строки х₅ (табл.1) на разрешающий элемент, результаты занесем в строку х_2, но в таблицу №2.

3)В остальных клетках разрешающегося столбца (табл.1) записываем 0.

4)Остальные клетки заполняем по правилу прямоугольника:

	НЭ=СТЭ-(А´В)/РЭ

НЭ- новый элемент.

СТЭ- старый элемент.

РЭ- разрешающий элемент.

А,В- эл-ты старого плана, образующие прямоугольник со старым эл-том и разрешающим элементом.

СТЭ А

В РЭ

b₁=18-(3х5)/1=3

а₁₁=1-(3х0)/1=1

b₂=16-(1х5)/1=11 и т.д.

Критерии оптимальности опять не выполнен, так как F имеет коэффициент -2<0

- наибольший отрицательный по модулю коэффициент |-2| определяет разрешающий столбец x₁

- min (3;11/2;∞;7)=3. Следовательно, 1^ая строка разрешающая а₁₁ - разрешающий элемент.

Таблица №3

← разрешающая строка

↑

разрешающий столбец

В таблице 3 критерий оптимальности вновь не выполнен. Разрешающий столбец x₅, разрешающая строка x₄, разрешающий элемент 5.

1)х₁ вместо х_3.

2)В строке х₁ делим все на 1.

Таблица №4

Базис	Свободный член	Переменные	Оценочные отношения
х1	х2	х3	х4	х5	х6
х1				-1/5	3/5
Х5				-2/5	1/5
х2				2/5	-1/5
х6				3/5	-9/5
F				4/5	3/5

Новая СТ№4 – критерий оптимальности выполнен – оптимальное базисное решение X(6,4,0,0,1,3)

F=24 =max

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

Прибыль принимает максимальное значение F_max=24 при реализации 6 единиц продукции P₁ (x₁=6) и 4 единиц продукции P₂(x₄=4). Дополнительные переменные x₃, x₄, x₅, x₆ показывают остатки ресурсов каждого вида. При оптимальном плане производства x₃=x₄=0, то есть остатки ресурсов S₃ и S₄ равны 0, а остатки ресурсов S₅ и S₆ равны соответственно 1 и 3 единицам.

Дата добавления: 2014-01-06