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

Симплексные таблицы

Рассмотренный симплексный метод решения ЗЛП в предыдущем пункте можно свести к записи однотипно заполняемых таблиц. Осуществить это возможно, придерживаясь следующего алгоритма:

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

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

3. Вычислить оценки разложений векторов условий по базису опорного решения и заполнить симплексную таблицу.

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

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

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

7. Если пункты 4-6 алгоритма не выполняются, находят новое опорное решение с использованием условий нахождения оптимального решения.

Пример. Решить задачу табличным симплексным методом.

F(Х) = 9 х ₁ + 5 х ₂+4 х ₃ + 3 х ₄ + 2 х ₅ →max.

Решение. Приводим задачу к каноническому виду. Для этого в левую часть первого ограничения-неравенства типа «≤» вводим дополнительную переменную х ₆ с коэффициентом +1. В целевую функцию переменная х ₆ входит с коэффициентом 0 (т.е. не входит). Получаем

F(Х) = 9 х ₁ + 5 х ₂+4 х ₃ + 3 х ₄ + 2 х ₅ +0 х ₆→max.

Находим начальное опорное решение. Для этого свободные (неразрешенные) переменные приравниваем к нулю х ₁= х ₂= х ₃=0. Получаем опорное решение Х ₁= (0, 0, 0, 24, 30, 6) с единичным базисом Б ₁ = (А ₄ , А ₅, А ₆).

Вычисляем оценки разложений векторов условий по базису опорного решения, используя формулу (Δ _к = С_бХ_к-с_к, где С_б =(с ₁ ,с ₂ ,…,с_т) ― вектор коэффициентов целевой функции при базисных переменных; Х_к =(х _{1 к} , х _{2 к} ,…, х_тк)-вектор коэффициентов разложения вектора по базису опорного решения; с_к ― коэффициент целевой функции при переменной х_к):

Δ₁= С _б Х ₁ - с ₁= (0, 3, 2) · (1, 1, 2) - 9 = 0 + 3 + 4 - 9 = -2;

Δ₂ = С_бХ ₂ -с ₂ = (0, 3, 2) · (-2, 2, 1) - 5 = 0 + 6 + 2 - 5 = 3;

Δ₃ = С_бХ ₃- с ₃= (0, 3, 2) · (2, 1, -4) - 4 = 0 + 3 - 8 - 4 = -9;

Δ ₄ = С_бХ ₄- с ₄ = (0, 3, 2) · (0, 1, 0) - 3 = 0 + 3 + 0 - 3 = 0;

Δ ₅ = С_бХ₅ - с ₅ = (0, 3, 2) · (0, 0, 1) - 2 = 0 + 0 + 2 - 2 = 0;

Δ ₆ = С_бХ₆ - с ₆ = (0, 3, 2) ·(1, 0, 0) - 0 = 0 + 0 + 0 - 0 = 0.

Оценки векторов, входящих в базис, всегда равны нулю. Обычно эти вычисления проводятся устно. Опорное решение, коэффициенты разложений и оценки разложений векторов условий по базису опорного решения записываются в симплексную таблицу. Сверху над таблицей для удобства вычислений оценок записываются коэффициенты целевой функции. В первом столбце «Б» записываются векторы, входящие в базис опорного решения. Порядок записи этих векторов в симплексной таблице соответствует номерам разрешенных неизвестных в уравнениях-ограничениях. Во втором столбце таблицы «С _б» записываются коэффициенты целевой функции при базисных переменных в том же порядке. При правильном расположении коэффициентов целевой функции в столбце «С _б» оценки единичных векторов, входящих в базис, всегда равны нулю.

В последней строке таблицы с оценками Δ _к в столбце «А ₀» записывается значение целевой функции на опорном решении F (X ₁).

9 5 ↓4 3 2 0

Б	С б	А 0	А 1	А 2	А 3	А 4	А 5	А 6	θ1	θ3
←А 6				-2
А 4
А 5					-4					-
Δ к		-2		-9

Начальное опорное решение не является оптимальным, так как оценки Δ₁=-2, Δ₃ = -9 для векторов А ₁ и А ₃ противоречат признаку оптимальности. Для оптимальности опорного решения в задаче на максимум требуется неотрицательность оценок для всех векторов условий.

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

Определим, введение какого из двух векторов приведет к большему приращению целевой функции. Приращения целевой функции найдем по формуле Δ F_k = -θ_{0 к} Δ _к. Вычислим значения параметра -θ_{0 к} для первого и третьего столбцов по формуле θ_{0 к} =, при х_ik >0, где к ― номер вектора, вводимого в базис; l - номер вектора, выводимого из базиса; х_i0 ― координаты опорного решения; х_ik - коэффициент разложения вектора А_к по базису опорного решения. Получаем θ₀₁ = 6 при l= 1 (где l — номер строки) и θ₀₃ = 3 при l = 1. Находим приращение целевой функции при введении в базис первого вектора Δ F ₁ = -6·(-2) = 12 и третьего вектора Δ F ₃= -3·(-9) = 27. Следовательно, для наиболее быстрого нахождения оптимального решения необходимо ввести в базис опорного решения вектор А ₃ вместо первого вектора базиса А ₆, так как минимум параметра θ₀₃ достигается в первой строке (l = 1).

Далее выполним преобразование с элементом х ₁₃ = 2, получим второе опорное решение Х ₂=(0,0,3,21,42,0) с базисом Б ₂ = (A ₃ , A ₄, А ₅) (следующая таблица). Это решение не является оптимальным, так как вектор А ₂ имеет отрицательную оценку Δ₂ = -6. Для улучшения решения необходимо ввести вектор А ₂ в базис опорного решения.

Б	С б	А 0	А 1	А 2	А 3	А 4	А 5	А 6	θ2
А 3			½	-1				½	-
←А 4			½					-½
А 5				-3					-
Δ к		5/2	-6				9/2

Определим номер вектора, выводимого из базиса. Для этого вычислим параметр θ₀₂ для второго столбца, он равен 7 при l =2. Следовательно, из базиса выводим второй вектор базиса А ₄. Выполним преобразование с элементом х ₂₂ = 3, получим третье опорное решение Х ₃ = (0, 7, 10, 0, 63, 0) с базисом Б ₂ = (А ₃, А ₂, А ₅). Это единственное оптимальное решение, так как для всех векторов, не входящих в базис, оценки разложений по базису опорного решения положительны: Δ₁=7/2, Δ₄=2, Δ₆=7/2.

Б	С б	А 0	А 1	А 2	А 3	А 4	А 5	А 6
А 3			2/3			1/3		1/3
←А 2			1/6			1/3		-1/6
А 5			9/2					3/2
Δ к		7/2					7/2

Ответ: max F(X) = 201 при X ^* = (0, 7,10, 0, 63).

Задачи решить симплексным методом:

9. Кирпичный завод выпускает кирпичи двух марок (I и II). Для производства кирпича применяется глина трех видов (А, В и С). По месячному плану завод должен выпустить 10 усл. ед. кирпича марки I и 15 усл. ед. кирпича марки II. В таблице указаны расход различных видов глины для производств 1 усл. ед. кирпича каждой марки и месячный запас глины. Какова наибольшая прибыль, если известно, что от реализации 1 усл. ед. кирпича марки I завод получает прибыль, равную 4 ден. ед., а марки II — 7 ден. ед.?

Марка кирпича	Количество глины для производства 1 усл. ед. кирпича
А	В	С
I
II
Запасы глины, усл. ед.

10. Для производства стали определенной марки, в которую в качестве легирующих веществ должны входить химические элементы К, L, Р, можно закупать шихту двух видов (I и II). В таблице указано, сколько требуется каждого из этих элементов для производства 100 т стали (по технологии можно немного больше, но меньше — нельзя). Содержание этих элементов в каждой тонне шихты, а также стоимость 1 т шихты каждого вида также приведены в таблице.

Вид шихты	Стоимость 1 т шихты	Легирующие вещества
К	L	Р
I
II
Необходимое количество легирующих веществ

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

Ответы: 1. х ₁=1, х ₂=0, F _max =1; 2. х ₁=12, х ₂=6, F _max =84; 3. Задача не имеет решений, т.к. F не ограничена на области D сверху; 4. х ₁= х ₂=0, х ₃=10, F _max=10; 5. х ₁=0, х ₂=1, F _min =-1; 6. х ₁=2, х ₂=0, F _min=-4; 7. х ₁= х ₄= х ₅=0, х ₂=4, х ₃=5, х ₆=11, F _min=-11; 8. х ₁=3/2, х ₂=7/4, F _max=-1; 9. F _max=191 ден.ед.; 10. F _min= 14 ден.ед.

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