Главная Случайная страница Контакты | Мы поможем в написании вашей работы! | ||
|
Алгоритм решения задач линейного программирования симплексным методом:
1. Привести задачу линейного программирования к каноническому виду.
2. Привести систему ограничений (1) к допустимому виду (4) и найти начальное базисное решение. Если начальное допустимое базисное решение отсутствует, то условия задачи противоречивы и оптимального решения нет.
3. Составить первую симплексную таблицу. Если система ограничений (1) приведена к допустимому виду (3), а целевая функция (2) к виду (5), то первая симплексная таблица примет вид ( - базисные переменные, - свободные члены):
- |
4. Предположим, что целевая функция (5) стремится к максимуму. Если задача линейного программирования на минимум , то ее можно свести к задаче на максимум путем умножения целевой функции на , то есть .В этом случае, если в последней строке первой симплексной таблицы (кроме числа ) все числа отрицательные, то есть все , то базисное решение является оптимальным и .
5. Пусть среди чисел имеется хотя бы одно положительное число, причем наибольшее из этих чисел находится в столбце , то есть это и пусть среди чисел этого столбца есть положительные числа. Для каждого такого числа составляем отношение . Из всех таких выражений выбираем наименьшее. Пусть оно соответствует строке (базисному неизвестному ), тогда - строка и - столбец – это разрешающие строка и столбец, а элемент - стоящий на их пересечении – разрешающий элемент.
6. Осуществим переход к новой таблице. Для этого разрешающую строку делим на , чтобы разрешающий элемент был = 1, а затем в -ом столбце с помощью -ой строки получаем нули, умножая строку на соответствующие числа и вычитая их из других строк таблицы. При этом старая базисная неизвестная станет свободной и заменится на новое базисное неизвестное . В результате будет осуществлен переход к новому базису .
7. С новой таблицей возвращаемся к выполнению пункта 4.
Пример 7. Решить симплексным методом задачу линейного программирования:
, (**), , .
Решение.
1. Приведем задачу к каноническому виду. Для этого введем балансовые переменные: (*).
2. Так как балансовые переменные введены с положительным знаком (знаки балансовых переменных совпадают со знаками свободных членов), то они могут быть выбраны в качестве базисных. То есть - базисные переменные, - свободные. Выразим базисные переменные через свободные: . Отсюда - начальное допустимое базисное решение. Целевая функция не зависит от базисных переменных, то есть уже выражена через свободные, следовательно - значение функции в начальном решении.
3. Составим начальную симплексную таблицу используя систему (*) и целевую функцию (**).
min |
Решение не является оптимальным, так как в последней строке есть положительные числа. Максимальное из них равно и соответствует столбцу (разрешающий столбец). Для каждого положительного числа столбца найдем оценку и внесем эти оценки в последний столбец первой симплексной таблицы. Среди оценок выберем минимальную, то есть . Строка соответствующая минимальной оценке будет разрешающей. Элемент, стоящий на пересечении разрешающего столбца и разрешающей строки является разрешающим, то есть - разрешающий.
4. Осуществим переход ко второй симплексной таблице.
Для этого разрешающую (первую) строку разделим на , чтобы разрешающий элемент был равен 1. Затем в разрешающем столбце необходимо получить все нули, кроме разрешающего элемента. При этом базисная переменная станет свободной, а - базисной. Для этого первую строку (после деления на ): вычтем из второй строки (),вычтем из третьей строки (), умножим на и вычтем из четвертой строки ().
1/3 | 5/3 | 1/3 | ||||||
2/3 | -2/3 | -1/3 | ||||||
5/3 | 7/3 | -1/3 | ||||||
-4 | -1 | -15 | min |
Решение не является оптимальным, так как в последней строке есть положительное число , соответствующее столбцу (разрешающий столбец). Для каждого положительного числа столбца найдем оценку и внесем эти оценки в последний столбец второй симплексной таблицы. Среди оценок выберем минимальную, то есть . Строка соответствующая минимальной оценке будет разрешающей. Элемент, стоящий на пересечении разрешающего столбца и разрешающей строки является разрешающим, то есть - разрешающий.
5. Осуществим переход к третьей симплексной таблице.
Для этого разрешающую (вторую) строку разделим на , чтобы разрешающий элемент был равен 1. Затем в разрешающем столбце необходимо получить все нули, кроме разрешающего элемента. При этом базисная переменная станет свободной, а - базисной. Для этого вторую строку (после деления на ): умножим на и вычтем из первой строки (); умножим на и вычтем из третьей строки (); вычтем из четвертой строки ().
1/2 | -1/2 | |||||||
-1 | -1/2 | 3/2 | ||||||
1/2 | -5/2 | |||||||
-3 | -1/2 | -3/2 | -18 | min |
Так как в последней строке нет положительных чисел, то из третьей симплексной таблицы - оптимальное решение, .
Дата публикования: 2015-02-18; Прочитано: 375 | Нарушение авторского права страницы | Мы поможем в написании вашей работы!