Курсовая работа: Решение задач линейного программирования в среде Maple
По
заполненной симплекс таблице определяем решение, соответствующее этой (нулевой)
итерации. Свободные переменные равны 0. Базисные переменные и значение функции
находим из таблицы. Они представлены в столбце «значение». Отметим, что
значение функции цели берём с противоположенным знаком. Итак, x° = (0,0,0,5,12,8) f° = 0.
В
оценочной строке имеются положительные числа. Значит, решение можно улучшить.
Выбираем наибольшее из положительных чисел. Если таких чисел несколько – берём
любое из них. Соответствующий столбец называют ведущим. По ведущему столбу и
столбцу «значения» определяем оценку для каждой строки. Число из столбца «значение»
делим на строку. По условию задачи это положительное число. Объявляем ведущей
строку ту, оценка у которой наименьшее положительное число.
В
первой таблице ведущая строка и столбец выделен цветом. На их пересечении
находится ведущий элемент. В нашем случае это 3.
Переходим
к первой итерации. Её суть состоит в том, чтобы свободную x3 сделать базисной, а базисную
переменную x4 - свободной. В таблице
выполняем преобразования аналогичные элементарным строчным преобразования
аналогичные элементарным строчным преобразованиям в методе Гаусса при решении
системы линейных уравнений. В результате преобразований получим:
x1 |
x2 |
x3 |
x4 |
x5 |
x6 |
значения |
базис |
оценка |
1 |
1/3 |
1 |
1/3 |
0 |
0 |
5/3 |
x3 |
5 |
1 |
8/3 |
0 |
-4/3 |
1 |
0 |
16/3 |
x5 |
2 |
0 |
1/3 |
0 |
-2/3 |
0 |
1 |
14/3 |
x6 |
14 |
-2 |
5/3 |
0 |
-4/3 |
0 |
0 |
-20/3 |
- f |
|
Из таблицы находим базисные переменные и значение функции x¹= (0,0,5/3,0,16/3,14/3) f¹ = 20/3. Этот результат можно
проверить. Полученные результаты должны удовлетворять функции цели в
канонической (стандартной) задаче линейного програмирования. В оценочной строке
имеются положительные числа. Значит, решение можно улучшить. Аналогично строим
следующую таблицу:
x1 |
x2 |
x3 |
x4 |
x5 |
x6 |
значения |
базис |
оценка |
5/8 |
0 |
1 |
1/2 |
-1/8 |
0 |
1 |
x3 |
- |
3/8 |
1 |
0 |
-1/2 |
3/8 |
0 |
2 |
x2 |
- |
-1/8 |
0 |
0 |
-1/2 |
-1/8 |
1 |
4 |
x6 |
- |
-21/8 |
0 |
0 |
-1/2 |
-5/8 |
0 |
-10 |
- f |
|
В оценочной строке данной таблицы все элементы не положительны. Это и означает,
что симплекс метод завершён. Результат последней итерации даёт ответ на
поставленную задачу.
Страницы: 1, 2, 3, 4, 5, 6 |