Главная Случайная страница Контакты | Мы поможем в написании вашей работы! | ||
|
q И т е р а ц и я 1.
В качестве начальной симплекс – таблицы возьмем таблицу, найденную в примере 6.7 и соответствующую допустимому базисному решению :
Таблица 6.7
Начальная симплекс - таблица
Базис | Переменные | Свободный член | Оценочное отношение | |
x 1 | x 2 | |||
x 3 x 4 x 5 | ¥ | |||
f (x) | -3 | -3 |
В последней строке таблицы есть два отрицательных элемента, , и столбец, соответствующий каждому из них можно считать опорным. Выберем, например, первый столбец (этот столбец отмечен стрелкой). Согласно теореме 6.9 существует допустимое базисное решение. Опорную строку найдем по правилу (6.29). В соответствии с пунктом 5 находим оценочные отношения: , т.е. это вторая строка. Опорный элемент обведен рамкой.
Будем формировать новую таблицу в соответствии с описанным алгоритмом
п.6 а,б п.6 в,г
x 4 | x 2 | x 4 | x 2 | |||||
x 3 | x 3 | -1 | ||||||
x 1 | x 1 | |||||||
x 5 | x 5 | |||||||
Свободные места последней таблицы заполним по «правилу прямоугольника». Например, число, стоящие в строке при x 3 и столбце при x 2 этой таблицы, равно 2∙2-1∙1 = 3. Для и т.д. В результате этих вычислений, а также пункта 6е (т.е. деления на опорный элемент) получим искомую симплекс – таблицу:
п.6д п.6е
x 4 | x 2 | x 4 | x 2 | |||||
х 3 | -1 | x 3 | -1/2 | 3/2 | ||||
х 1 | x 1 | 1/2 | 1/2 | |||||
х 5 | x 5 | |||||||
-3 | 3/2 | -3/2 |
Отметим, что в результате перехода к новому допустимому решению значение целевой функции уменьшилось с 0 до –12 (см. нижний элемент последнего столбца таблицы).
q И т е р а ц и я 2.
В качестве опорного (см. п. 6е) можно взять только второй столбец (). С учетом (6.29) находим опорную строку:
Таблица 6.8
Симплекс-таблица для угловой точки х 1
Базис | Переменные | Свободный член | Оценочное отношение | |
x 4 | x 2 | |||
x 3 x 1 x 5 | -1/2 1/2 | 3/2 1/2 | ||
f (x) | 3/2 | -3/2 |
, т.е. это первая строка. Опорный элемент обведен рамкой.
Преобразуем таблицу согласно алгоритму, получаем
x 4 | x 3 | x 4 | x 3 | x 4 | x 3 | ||||||||
x 2 | -1/2 | x 2 | -1/2 | x 2 | -1/3 | 2/3 | |||||||
x 1 | -1/2 | x 1 | -1/2 | 9/2 | x 1 | 2/3 | -1/3 | ||||||
x 5 | -1 | x 5 | 1/2 | -1 | 3/2 | x 5 | 1/3 | -2/3 | |||||
3/2 | 3/2 | 3/2 | 45/2 |
Таким образом, на данной итерации значение f (х) уменьшилось с –12 до –15.
q И т е р а ц и я 3.
Так как все элементы в последней строке таблицы неотрицательны, то, согласно теореме 6.9, базисное решение является точкой минимума в рассматриваемой задаче, т.е. х * = (3;2;0;0;1), f * = –15. Графическое решение задачи представлено на рис. 6.8, откуда видно, что х * = (3;2), f * = f (х *) = –15
Рис. 6.8. Графическое решение задачи 6.10
Дата публикования: 2015-01-23; Прочитано: 217 | Нарушение авторского права страницы | Мы поможем в написании вашей работы!