Информатика -продвинутый курс




СИМПЛЕКС-МЕТОД - часть 4


Затем, используя действия, аналогичные указанным в пп. 3 - 5 алгоритма симплекс-метода, совершаем преобразования исходной таблицы до тех пор, пока не получим неотрицательное базисное решение.

Пример 2. Найти исходное неотрицательное базисное решение системы ограничений

Так как условие неотрицательности свободных членов соблюдается, приступим к преобразованиям исходной системы, записывая результаты в таблицу. Согласно алгоритму просматриваем первый столбец. В этом столбце имеется единственный положительный элемент a31. Делим на 8,654 все коэффициенты и свободный член третьей строки, после чего умножаем каждый коэффициент на 8,704 и складываем с соответствующими коэффициентами второй строки. Первая строка преобразований не требует, так как коэффициент при неизвестном x1 равен нулю. В результате получаем

0,00000

0,00000

1,00000

-5,87100

 0,68512

-0,77756

6,54300

17,46384

0,97677

-9,99600

 8,57990

 0,89808

 7,61800

-3,19062

 0,62769

0,86400

9,79929

1,11584

Продолжая просматривать второй столбец и совершая аналогичные преобразования, имеем

0,00000

0,00000

1,00000

0,00000

1,00000

0,00000

156,19554

25,49013

20,79687

63,52761

12,52318

10,63560

-19,72328

-4,65701

-2,99341

84,83688

14,30299

12,24727

И, наконец, на третьем шаге находим исходный базис. Его образуют неизвестные x1, x2,

x3. Неизвестные x4, х5

являются свободными:

0,00000

0,00000

1,00000

0,00000

1,00000

0,00000

1,00000

0,00000

0,00000

0,40672

2,15588

2,17713

-0,12627

-1,43829

-0,36733

0,54315

0,45815

0,95155

При решении задачи линейного программирования целесообразно использование компьютера. В этом случае можно составить программу, решающую задачу. Учитывая, что программирование довольно трудоемко, можно посоветовать воспользоваться для оформления результатов расчетов табличным процессором.Кроме того, если получившаяся модель задачи слишком громоздка, можно воспользоваться математическими пакетами, которые позволяют получить решение задачи линейного программирования. И, наконец, еще один возможный вариант применения компьютеров - комбинирование всех вышеуказанных способов.




Содержание  Назад  Вперед