Решение задачи симплекс-методом

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

Имеющиеся уравнения условий преобразуем к виду:

а₁₁х₁ + а₁₂х₂ + а₁₃х₃ + а₁₄х₄ + а₁₅х₅ = b_1.

Для первого условия получаем: 1х₁ + 1х₂ + 0х₃ + 0х₄ + 0х₅ = 1

Для второго: (-1)х₁ + 0х₂ + 1х₃ + 1х₄ +0х₅ = 0

Для третьего: 0х₁ + 1х₂+ 1х₃ + 0х₄ + (-1)х₅ = 0

Для четвертого: 0х₁+ 0х₂ + 0х₃ + 1х₄ + 1х₅ = 1

Затем составляем матрицу коэффициентов, которая будет выглядеть таким образом:

Базисных переменных в базисе будет столько, сколько линейно-независимых уравнений. Поэтому мы находим ранг матрицы.

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

1) Ко второй строке прибавляем первую строку.

2) От третьей строки отнимаем вторую строку.

3) Третью строку делим на (-1).

4) От четвертой строки отнимаем третью строку.

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

Тогда матрица коэффициентов будет выглядеть таким образом:

Теперь мы можем начать составление симплекс-таблицы.

Первая интерация:

←

↑

Вторая интерация:

←

↑

Третья интерация:

Найдено оптимальное решение:
X = .

Мы видим, что кратчайший путь пролегает через узлы 1,2 и 4 по рёбрам 1 и 4.

Найдём кратчайший путь на сети, подставив значения переменных в функцию:
42*1 + 48*0 + 36*0 + 33*1 + 41*0 = 42+33 = 75.

Рис.3.Найденный кратчайший путь

Использованная литература

Ларин Р.М., Плясунов А.В., Пяткин А.В.. Методы оптимизации. Примеры и задачи: Учеб. Пособие / Новосиб. ун-т. Новосибирск, 2003. 115 с.

Гасс С.И.. Линейное программирование (методы и приложения) / М.: Гос. Изд-во физ- мат. лит-ры, 1961. 303 с.