Полная версия

Главная arrow Туризм arrow Основы функционирования систем сервиса

  • Увеличить шрифт
  • Уменьшить шрифт


<<   СОДЕРЖАНИЕ ПОСМОТРЕТЬ ОРИГИНАЛ   >>

Примеры решения задач ЛП симплекс-методом

Рассмотрим конкретный пример [44]. Максимизировать

/= *i - *2

при ограничениях:

Приведем задачу к стандартному виду В матричной записи эти уравнения имеют вид

Число вариантов решений можно рассчитать по формуле п/(пт)т. При /я = 3 и я = 5 получим 5!/(5 — 3)!3! = 10 вариантов. Из них пять лежат в ОДР. В табл. 8.1 даны варианты и соответствующие решения.

Таблица 8.1. Варианты решения

Вариант

А

В

С

D

Е

X,

0

0

0,66

3

2

*2

1

5

4,66

0

0

*3

8

0

0

7

8

*4

0

8

8

1

0

*5

5

1

0

0

2

Очевидным решением, находящимся в ОДР, будет решение, при котором все свободные переменные равны нулю. Их должно быть две. При Х — 0 и х2 0 получаем х4 — 2, т.е. имеет место недопустимое значение. Если принять Xj = 0 их3 = 0, то, как следует из табл. 8.1, х2 5, х4 = 8, xs = 1, т.е. начальный вектор переменных запишется в виде

что соответствует варианту В в табл. 8.1.

Значение целевой функции равно/= Xj — х2 0 — 5 = —5.

Запишем расширенную матрицу (8.2), дополнив ее нижней строкой с переменными:

Переставим столбцы матрицы так, чтобы переменные х{ и х3, которые мы приравняли к нулю, были справа — в конце строки переменных:

Преобразуем левую верхнюю подматрицу к единичной: Обратная матрица для матрицы В имеет вид

Умножая первые три строки расширенной матрицы на В-1, получим

что соответствует преобразованию исходной системы уравнений (8.12) к системе

Добавим к полученной матрице нижнюю строку с элементами ЦФ для соответствующих переменных:

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

Полностью расширенная матрица, представляющая собой симплекс-таблицу рассматриваемой задачи, имеет вид

Таким образом, имеем

В таблице есть с, < 0 и Fyi > 0. Выберем 4-й столбец, в’котором с,- < 0 и имеет наибольшее абсолютное значение.

В качестве опорного элемента надо выбрать такой, у которого коэффициент bn/Fnt наименьший. Это элемент 1,5 в 3-й строке, так как

Поделим элементы 3-й строки на 1,5:

Используем новую 3-ю строку для получения нулевых элементов в других строках 4-го столбца:

Таким образом, получен новый базисный столбец таблицы: свободная переменная стала базисной, а базисная — свободной. Переставим столбцы местами и получим новую таблицу:

Как видно, в 5-м столбце таблицы есть с, < 0 и > 0. В качестве опорного выберем элемент 1-й строки 0,66, так как 4,66 / 0,66 = 7 < 8/1 = 8. Поделим элементы 1 -й строки на 0,66 и используем ее для получения нулевых элементов в других строках:

Переставим 1-й и 5-й столбцы местами и получим новую таблицу:

Так как все коэффициенты с, > 0, процесс должен быть остановлен. Решение для переменных х, их2будетх! = 3,х2 = 0 и /=х, — х2 = 3 — 0 = 3. Так как в целевую функцию входят только переменные х{ и х2, то ОДР можно изобразить на плоскости (рис. 8.1). Оптимальное решение соответствует точке D. Согласно табл. 8.1 и правому столбцу симплекс-таблицы, х3 = 7, х4 = 1, х5 = 0.

При оптимизации с использованием симплекс-алгоритма движение начиналось из точки В многоугольника в точку С и завершилось в точке D. Рассмотрим задачу минимизации [44]. Найти минимум f=xl — Зх2 + х3 при следующих ограничениях: Графическое решение задачи (8.12)

Рис. 8.1. Графическое решение задачи (8.12)

Преобразовав задачу к стандартной форме, получим следующую расширенную матрицу

Для получения допустимого решения необходимо приравнять свободные переменные нулю. Будем использовать в качестве базисных переменные, соответствующие столбцам, содержащим только единичные элементы. Так как 5-й столбец содержит во 2-й строке значение — 1, вместо него будем использовать 3-й столбец. Для получения остальных нулевых значений в 3-м столбце используем 2-ю строку. В результате получим

В данном примере не осуществляется умножение первых трех строк на обратную матрицу, а используется метод исключения Гаусса—Жордана. Не будем также переставлять столбцы, а запишем симплекс-таблицу в виде

Далее необходимо выполнить соответствующие операции, чтобы коэффициенты целевой функции были нулевыми для единичных столбцов:

Интересующий нас случай, когда с, > 0 и FJx > 0, соответствует элементу 4 во 2-м столбце. Вычислим отношения Ь./Кх для всех j и выберем среди них минимальное. Это элемент 1 во 2-й строке, который выберем в качестве ведущего. Используем 2-ю строку для получения остальных нулевых элементов во 2-м столбце. В результате получим

Так как в нижней строке для свободной переменной 5-го столбца есть положительное число 3, процесс надо продолжить. Ведущим элементом будет число 2 в 4-й строке. Использование этой строки для получения в ней 1 и нулевых элементов в других элементах этого столбца дает

Теперь положительные коэффициенты в нижней строке отсутствуют и процесс можно считать завершенным. Минимальное значение целевой функции равно —10,5 при

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

КОНТРОЛЬНЫЕ ВОПРОСЫ

  • 1. Сформулируйте идею симплекс-метода и симплекс-алгоритма.
  • 2. Как по стандартной задаче Л П образовать симплекс-таблицу?
  • 3. Объясните последовательность действий при максимизации (минимизации) целевой функции.
  • 4. Из каких соображений выбирается коэффициент целевой функции при задаче максимизации (минимизации)?
  • 5. Что такое ведущий элемент симплекс-таблицы? Из каких соображений он выбирается при задаче максимизации (минимизации)?
 
<<   СОДЕРЖАНИЕ ПОСМОТРЕТЬ ОРИГИНАЛ   >>