Главная Случайная страница Контакты | Мы поможем в написании вашей работы! | ||
|
Рассмотренный симплексный метод решения ЗЛП в предыдущем пункте можно свести к записи однотипно заполняемых таблиц. Осуществить это возможно, придерживаясь следующего алгоритма:
1. Привести задачу линейного программирования к каноническому виду.
2. Найти начальное опорное решение с базисом из единичных векторов и коэффициенты разложений векторов условий по базису опорного решения. Если опорное решение отсутствует, то задача не имеет решения в силу несовместности системы ограничений.
3. Вычислить оценки разложений векторов условий по базису опорного решения и заполнить симплексную таблицу.
4. Если выполняется признак единственности оптимального решения (для любого вектора условий, не входящего в базис, оценка отлична от нуля), то решение задачи заканчивается.
5. Если выполняется условие существования множества оптимальных решений (оценка хотя бы одного вектора условий, не входящего в базис, равна нулю), то путем простого перебора находят все оптимальные решения.
6. Если выполняются условия отсутствия оптимального решения вследствие неограниченности целевой функции (не имеет решения, если для какого-либо из векторов условий с оценкой, противоречащей признаку оптимальности, среди коэффициентов разложения по базису опорного решения нет положительного), то задача не имеет решения ввиду неограниченности целевой функции.
7. Если пункты 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 (X 1).
9 5 ↓4 3 2 0
Б | С б | А 0 | А 1 | А 2 | А 3 | А 4 | А 5 | А 6 | θ1 | θ3 |
←А 6 | -2 | |||||||||
А 4 | ||||||||||
А 5 | -4 | - | ||||||||
Δ к | -2 | -9 |
Начальное опорное решение не является оптимальным, так как оценки Δ1=-2, Δ3 = -9 для векторов А 1и А 3противоречат признаку оптимальности. Для оптимальности опорного решения в задаче на максимум требуется неотрицательность оценок для всех векторов условий.
По теореме об улучшении опорного решения, если в задаче на максимум хотя бы один вектор имеет отрицательную оценку, то можно найти новое опорное решение, на котором значение целевой функции будет больше.
Определим, введение какого из двух векторов приведет к большему приращению целевой функции. Приращения целевой функции найдем по формуле Δ Fk = -θ0 к Δ к. Вычислим значения параметра -θ0 к для первого и третьего столбцов по формуле θ0 к = , при хik >0, где к ― номер вектора, вводимого в базис; l - номер вектора, выводимого из базиса; хi0 ― координаты опорного решения; хik - коэффициент разложения вектора Ак по базису опорного решения. Получаем θ01 = 6 при l= 1 (где l — номер строки) и θ03 = 3 при l = 1. Находим приращение целевой функции при введении в базис первого вектора Δ F 1= -6·(-2) = 12 и третьего вектора Δ F 3= -3·(-9) = 27. Следовательно, для наиболее быстрого нахождения оптимального решения необходимо ввести в базис опорного решения вектор А 3вместо первого вектора базиса А 6, так как минимум параметра θ03 достигается в первой строке (l = 1).
Далее выполним преобразование с элементом х 13= 2, получим второе опорное решение Х 2=(0,0,3,21,42,0) с базисом Б 2= (A 3 , A 4, А 5)(следующая таблица). Это решение не является оптимальным, так как вектор А 2имеет отрицательную оценку Δ2 = -6. Для улучшения решения необходимо ввести вектор А 2в базис опорного решения.
Б | С б | А 0 | А 1 | А 2 | А 3 | А 4 | А 5 | А 6 | θ2 |
А 3 | ½ | -1 | ½ | - | |||||
←А 4 | ½ | -½ | |||||||
А 5 | -3 | - | |||||||
Δ к | 5/2 | -6 | 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 | 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).
Дата публикования: 2015-11-01; Прочитано: 486 | Нарушение авторского права страницы | Мы поможем в написании вашей работы!