- •Введение
- •1. Общая задача линейного программирования
- •Задачи для самостоятельного решения:
- •2. Графический метод решения задач линейного программирования
- •2.1. Задача с двумя переменными
- •2.2. Графический метод решения задач линейного программирования с п переменными
- •Задачи для самостоятельного решения:
- •3. Симплексный метод решения задач линейного программирования
- •3.1. Симплекс-метод
- •3.2. Симплексные таблицы
- •Задачи для самостоятельного решения:
- •4. Теория двойственности
- •4.1. Виды математических моделей двойственных задач
- •4.2. Первая теорема двойственности
- •4.3. Вторая теорема двойственности
- •Задачи для самостоятельного решения
- •5. Транспортная задача линейного программирования
- •5.1. Формулировка транспортной задачи
- •5.2. Алгоритм решения транспортной задачи методом потенциалов
- •Задачи для самостоятельного решения
- •Список рекомендуемой литературы:
3.2. Симплексные таблицы
Рассмотренный симплексный метод решения ЗЛП в предыдущем пункте можно свести к записи однотипно заполняемых таблиц. Осуществить это возможно, придерживаясь следующего алгоритма:
Привести задачу линейного программирования к каноническому виду.
Найти начальное опорное решение с базисом из единичных векторов и коэффициенты разложений векторов условий по базису опорного решения. Если опорное решение отсутствует, то задача не имеет решения в силу несовместности системы ограничений.
Вычислить оценки разложений векторов условий по базису опорного решения и заполнить симплексную таблицу.
Если выполняется признак единственности оптимального решения (для любого вектора условий, не входящего в базис, оценка отлична от нуля), то решение задачи заканчивается.
Если выполняется условие существования множества оптимальных решений (оценка хотя бы одного вектора условий, не входящего в базис, равна нулю), то путем простого перебора находят все оптимальные решения.
Если выполняются условия отсутствия оптимального решения вследствие неограниченности целевой функции (не имеет решения, если для какого-либо из векторов условий с оценкой, противоречащей признаку оптимальности, среди коэффициентов разложения по базису опорного решения нет положительного), то задача не имеет решения ввиду неограниченности целевой функции.
Если пункты 4-6 алгоритма не выполняются, находят новое опорное решение с использованием условий нахождения оптимального решения.
Пример. Решить задачу табличным симплексным методом.
F(Х) = 9х1+5х2+4х3 +3х4 +2х5 →max.
Решение. Приводим задачу к каноническому виду. Для этого в левую часть первого ограничения-неравенства типа «≤» вводим дополнительную переменную х6 с коэффициентом +1. В целевую функцию переменная х6 входит с коэффициентом 0 (т.е. не входит). Получаем
F(Х) = 9х1 +5х2+4х3 +3х4 +2х5 +0 х6→max.
Находим начальное опорное решение. Для этого свободные (неразрешенные) переменные приравниваем к нулю х1=х2=х3=0. Получаем опорное решение Х1= (0, 0, 0, 24, 30, 6) с единичным базисом Б1 = (А4 , А5, А6).
Вычисляем оценки разложений векторов условий по базису опорного решения, используя формулу (Δк=СбХк-ск, где Сб=(с1,с2,…,ст)- вектор коэффициентов целевой функции при базисных переменных; Хк=(х1к, х2к,…, хтк)-вектор коэффициентов разложения вектора по базису опорного решения; ск -коэффициент целевой функции при переменной хк):
Δ1= СбХ1 - с1= (0, 3, 2) · (1, 1, 2) - 9 = 0 + 3 + 4 - 9 = -2;
Δ2 = СбХ2 -с2= (0, 3, 2) · (-2, 2, 1) - 5 = 0 + 6 + 2 - 5 = 3;
Δ3 = СбХ3- с3= (0, 3, 2) · (2, 1, -4) - 4 = 0 + 3 - 8 - 4 = -9;
Δ 4 = СбХ4- с4 = (0, 3, 2) · (0, 1, 0) - 3 = 0 + 3 + 0 - 3 = 0;
Δ 5 = СбХ5 - с5 = (0, 3, 2) · (0, 0, 1) - 2 = 0 + 0 + 2 - 2 = 0;
Δ 6 = СбХ6 - с6 = (0, 3, 2) ·(1, 0, 0) - 0 = 0 + 0 + 0 - 0 = 0.
Оценки векторов, входящих в базис, всегда равны нулю. Опорное решение, коэффициенты разложений и оценки разложений векторов условий по базису опорного решения записываются в симплексную таблицу. Сверху над таблицей для удобства вычислений оценок записываются коэффициенты целевой функции. В первом столбце «Б» записываются векторы, входящие в базис опорного решения. Порядок записи этих векторов в симплексной таблице соответствует номерам разрешенных неизвестных в уравнениях-ограничениях. Во втором столбце таблицы «Сб» записываются коэффициенты целевой функции при базисных переменных в том же порядке. При правильном расположении коэффициентов целевой функции в столбце «Сб» оценки единичных векторов, входящих в базис, равны нулю.
В последней строке таблицы с оценками Δк в столбце «А0» записывается значение целевой функции на опорном решении F(X1).
9 5 ↓4 3 2 0
Б |
Сб |
А0 |
А1 |
А2 |
А3 |
А4 |
А5 |
А6 |
θ1 |
θ3 |
←А6 |
0 |
6 |
1 |
-2 |
2 |
0 |
0 |
1 |
6 |
3 |
А4 |
3 |
24 |
1 |
2 |
1 |
1 |
0 |
0 |
24 |
24 |
А5 |
2 |
30 |
2 |
1 |
-4 |
0 |
1 |
0 |
15 |
- |
Δ к |
132 |
-2 |
3 |
-9 |
0 |
0 |
0 |
|
Начальное опорное решение не является оптимальным, так как оценки Δ1=-2, Δ3=-9 для векторов А1 и А3 противоречат признаку оптимальности.
Определим, введение какого из двух векторов приведет к большему приращению целевой функции. Приращения целевой функции найдем по формуле ΔFk=-θ0к Δ к. Вычислим значения параметра -θ0к для первого и третьего столбцов по формуле θ0к= , при хik>0, где к -номер вектора, вводимого в базис; l- номер вектора, выводимого из базиса; хi0-координаты опорного решения; хik-коэффициент разложения вектора Ак по базису опорного решения. Получаем θ01=6 при l=1 (где l— номер строки) и θ03=3 при l=1. Находим приращение целевой функции при введении в базис первого вектора ΔF1=-6·(-2)=12 и третьего вектора ΔF3=-3·(-9)=27. Следовательно, для наиболее быстрого нахождения оптимального решения необходимо ввести в базис опорного решения вектор А3 вместо первого вектора базиса А6, так как минимум параметра θ03 достигается в первой строке (l = 1).
Далее выполним преобразование с элементом х13=2, получим второе опорное решение Х2=(0,0,3,21,42,0) с базисом Б2=(A3,A4,А5) (следующая таблица). Это решение не является оптимальным, так как вектор А2 имеет отрицательную оценку Δ2=-6. Для улучшения решения необходимо ввести вектор А2 в базис опорного решения.
-
Б
Сб
А0
А1
А2
А3
А4
А5
А6
θ2
А3
4
3
½
-1
1
0
0
½
-
←А4
3
21
½
3
0
1
0
-½
7
А5
2
42
4
-3
0
0
1
2
-
Δ к
159
5/2
-6
0
0
0
9/2
Определим номер вектора, выводимого из базиса. Для этого вычислим параметр θ02 для второго столбца, он равен 7 при l=2. Следовательно, из базиса выводим второй вектор базиса А4. Выполним преобразование с элементом х22=3, получим третье опорное решение Х3 = (0,7,10,0,63,0) с базисом Б2=(А3,А2,А5). Это единственное оптимальное решение, так как для всех векторов, не входящих в базис, оценки разложений по базису опорного решения положительны: Δ1=7/2, Δ4=2, Δ6=7/2.
-
Б
Сб
А0
А1
А2
А3
А4
А5
А6
А3
4
10
2/3
0
1
1/3
0
1/3
←А2
5
7
1/6
1
0
1/3
0
-1/6
А5
2
63
9/2
0
0
1
1
3/2
Δ к
201
7/2
0
0
2
0
7/2
Ответ: Fmax = 201 при X * = (0, 7,10, 0, 63).