Методичка по курсовым и лабораторным работам (1085639), страница 11
Текст из файла (страница 11)
Шаг 3. Преобразовать симплекс-таблицу по описанному ранее алгоритму и перейти к шагу 2.
Замечания:
1. Если на шаге 2 возникает ситуация б), т.е. существует коэффициент pj < 0, причем не все aij ? 0, и среди коэффициентов pj есть несколько, удовлетворяющих этим условиям, то в качестве номера разрешающего столбца можно взять любой из таких номеров, например, тот, для которого значение pj минимально.
2. Если при выборе номера разрешающей строки окажется, что минимум в выражении (3.25) достигается сразу для нескольких номеров, то в качестве номера разрешающей строки можно взять любой, например, наименьший. При этом в новом решении соответствующие базисные переменные обратятся в нуль, и мы получим вырожденное допустимое базисное решение.
В примере 3.6. оптимальное решение найдено за один шаг, т.к. все pj > 0.
Пример 3.7.
Вернемся к задаче из примера 3.5:
f(x1, x2, x3, x4 ) = –x1– 2x2 ® min
x1 + x2 + x3 = 2,
x1 – x2 + x4 = 1,
x1, x2, x3, x4 ? 0.
В примере 3.6 исходная симплекс-таблица
| x1 x2 | ||
| x3 x4 | 1 1 1 –1 | 2 1 |
| –1 –2 | 0 |
была преобразована в следующую симплекс-таблицу:
| x1 x3 | ||
| x2 x4 | 2 1 2 1 | 2 3 |
| 1 2 | 4 |
Анализ этой таблицы показывает, что все pj > 0 (p1 = 1, p2 = 2). Следовательно, решение найдено: x1 = 0, x2 = 2, x3 = 0, x4 = 3; x* = (0, 2, 0, 3), f* = f(x*) = –4.
Пример 3.8
Решить симплекс-методом следующую ЗЛП:
f(x1, x2, x3, x4, x5) = 2x1+ x2 + 3x3+ x4 + x5 – 9 ® max,
2x1 + x2 + x3 – x5 = 3,
x1 + 2x2 + x4 + x5 = 2,
x1, x2, x3, x4, x5 ? 0.
Перейдем от задачи поиска максимума к задаче поиска минимума:
f(x1, x2, x3, x4, x5) = –2x1– x2 – 3x3– x4 – x5 + 9 ® min, (3.33)
2x1 + x2 + x3 – x5 = 3, (3.34)
x1 + 2x2 + x4 + x5 = 2, (3.35)
x1, x2, x3, x4, x5 ? 0.
Из ограничений (3.34) и (3.35) следует, что переменные x3 и x4 можно взять в качестве базисных, а переменные x1, x2, x5 – в качестве свободных. Выразим базисные переменные через свободные:
x3 = 3 – 2x1 – x2 + x5, (3.36)
x4 = 2 – x1 – 2x2 – x5. (3.37)
Подставим (3.36) и (3.37) в (3. 33) и выразим целевую функцию через свободные переменные:
f = –2x1– x2 – 3x3– x4 – x5 + 9 = –2x1– x2 – 3(3 – 2x1 – x2 + x5) – (2 – x1 – 2x2 – x5) – x5 + 9 = 5x1 + 4x2 – 5x5 – 2.
Итак, мы свели нашу ЗЛП следующей канонической задаче:
5x1 + 4x2 – 5x5 – 2 ® min,
2x1 + x2 + x3 – x5 = 3,
x1 + 2x2 + x4 + x5 = 2,
x1, x2, x3, x4, x5 ? 0.
Применим к этой задаче алгоритм симплекс-метода (алгоритм 3.2).
Шаг 1. Составим исходную симплекс-таблицу для допустимого базисного решения (0, 0, 3, 2, 0):
| x1 x2 x5 | ||
| x3 x4 | 2 1 –1 1 2 1 | 3 2 |
| 5 4 –5 | 2 |
3.4. Метод искусственного базиса
Мы рассматривали решение ЗЛП симплекс-методом, задавая вначале допустимое базисное решение и соответствующую ему симплекс-таблицу. Однако, далеко не всегда можно сразу найти начальное допустимое базисное решение. Для нахождения такого начального решения используется метод искусственного базиса.
Рассмотрим задачу линейного программирования в следующем виде:
f(x1, x2, …, xn) ® min,
a11x1+ … + a1mxm + a1,m+1xm+1 +…+ a1nxn = b1,
………………………………………………… (3.38)
am1x1+ … + ammxm+ am,m+1xm+1 +…+ amnxn = bm.
x1, x2, …, xn ? 0.
Будем считать, что все свободные члены b1, b2, …, bm ? 0. Если это не так, умножим соответствующее равенство на –1. Введем дополнительные переменные xn+1, x n+2, …, x n+m ? 0 и рассмотрим вспомогательную задачу линейного программирования:
= xn+1 + x n+2 + …+ x n+m ® min,
a11x1+ … + a1mxm + a1,m+1xm+1 +…+ a1nxn + xn+1 = b1,
………………………………………………………... (3.39)
am1x1+ … + ammxm+ am,m+1xm+1 +…+ amnxn + x n+m = bm.
x1, x2, …, xn+m ? 0.
Одной из допустимых базисных точек этой задачи является точка 
= (0, …, 0, b1, …, bm). Можно поэтому решить задачу (3.39) симплекс-методом. Начальная симплекс-таблица составляется для допустимого базисного решения = (0, …, 0, b1, …, bm). Базисные переменные xn+1, x n+2, …, x n+m определяются через свободные переменные x1, x2, …, xn следующим образом:
xn+1 = b1 – (a11x1+ … + a1mxm + a1,m+1xm+1 +…+ a1nxn)
………………………………………………………... (3.40)
x n+m = bm – (am1x1+ … + ammxm+ am,m+1xm+1 +…+ amnxn)
Выражения (3.40) подставляются в выражение для целевой функции = xn+1 + x n+2 + …+ x n+m. При решении задачи (3.38) симплекс-методом дополнительные переменные xn+1, x n+2, …, x n+m, которые являются базисными, постепенно переводятся в свободные. При этом значение целевой функции становится равным нулю. Если это условие не выполняется, то задача не имеет решения. Если же решение существует, то полученная симплекс-таблица определяет допустимое базисное решение.
Для дальнейшего решения задачи (3.38) симплекс-методом необходимо заменить в полученной таблице последнюю строку на строку коэффициентов целевой функции.
Пример 3.9.
Решить следующую ЗЛП:
f(x) = 4x1 + x2 ® min,
3x1 + x2 = 3,
4x1 + 3x2 – x3 = 6,
x1 + 2x2 + x4 = 4
x1, x2, x3, x4 ? 0.
В третьем уравнении переменную x4 можно взять в качестве базисной, а в первом и втором уравнении таких переменных нет. В эти уравнения введем дополнительные переменные x5, x6. Получим следующую ЗЛП:
= x5 + x6 ® min,
3x1 + x2 + x5 = 3,
4x1 + 3x2 – x3 + x6 = 6,
x1 + 2x2 + x4 = 4
x1, x2, x3, x4, x5, x6 ? 0.
Базисные переменные x4, x5, x6 определяются через свободные переменные x1, x2, x3 следующим образом:
x5 = 3 – (3x1 + x2),
x6 = 6 – (4x1 + 3x2 – x3) ,
x4 = 4 – (x1 + 2x2).
Подставим эти равенства в выражение для целевой функции = x5 + x6:
= 9 –7x1 – 4x2 + x3.
Получим начальную симплекс-таблицу:
| x1 x2 x3 | ||
| x5 x6 x4 | 3 1 0 4 3 –1 1 2 0 | 3 6 4 |
| –7 –4 1 | –9 |
Найдем последовательность симплекс-таблиц для первого этапа решения исходной ЗЛП – нахождения допустимого базисного решения.
| x5 x2 x3 | ||
| x1 x6 x4 | 1/3 1/3 0 –4/3 5/3 –1 –1/3 5/3 0 | 1 2 3 |
| 7/3 –5/3 1 | –2 |
Дополнительная переменная x5 стала свободной, поэтому ее можно исключить из таблицы:
| x2 x3 | ||
| x1 x6 x4 | 1/3 0 5/3 –1 5/3 0 | 1 2 3 |
| –5/3 1 | –2 |
Делаем аналогичные преобразования с новой таблицей:
| x6 x3 | ||
| x1 x2 x4 | –1/5 1/5 3/5 –3/5 –1 1 | 3/5 6/5 1 |
| 1 0 | 0 |
Дополнительную переменную x6 можно исключить из таблицы:
| x3 | ||
| x1 x2 x4 | 1/5 –3/5 1 | 3/5 6/5 1 |
| 0 | 0 |
Так как строка целевой функции не содержит отрицательных переменных и значение целевой функции равно нулю, то основная задача имеет допустимое решение. Переходим ко второму этапу – поиску оптимального решения исходной задачи.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
