Xreferat.com » Рефераты по информатике и программированию » Симплекс метод решения задачи линейного программирования

Симплекс метод решения задачи линейного программирования

Задача №1 (.)


Найти F max = 9x1+ 10x2 + 16x3, при ограничениях:


Симплекс метод решения задачи линейного программирования


Запишем задачу в каноническом виде:


F=9x1+ 10x2 + 16x3 → max

Симплекс метод решения задачи линейного программирования


Заполним начальную таблицу:


Симплекс метод решения задачи линейного программирования


Таблица 0.



0 9 10 16 0 0 0

Отношение,

θ

i

Симплекс метод решения задачи линейного программирования

Базис

Симплекс метод решения задачи линейного программирования

Симплекс метод решения задачи линейного программирования

Симплекс метод решения задачи линейного программирования

Симплекс метод решения задачи линейного программирования

Симплекс метод решения задачи линейного программирования

Симплекс метод решения задачи линейного программирования

Симплекс метод решения задачи линейного программирования


1 0

Симплекс метод решения задачи линейного программирования

360 18 15 12 1 0 0 30
2 0

Симплекс метод решения задачи линейного программирования

192 6 4 8 0 1 0 24
3 0

Симплекс метод решения задачи линейного программирования

180 5 3 3 0 0 1 60

∆j 0 -9 -10 -16 0 0 0

Zj 0 0 0 0 0 0 0

Zj вычисляется по формуле Симплекс метод решения задачи линейного программирования

Оценки (∆j) вычисляются по формуле Симплекс метод решения задачи линейного программирования, где Симплекс метод решения задачи линейного программирования - коэффициент из первой строки таблицы.

Выбираем минимальную (отрицательную) оценку. Она определяет направляющий столбец.

Заполняем столбец «θ», по минимальному значению определяем направляющую строку.

На пересечение строки и столбца находится направляющий элемент.


Заполняем новую таблицу


Таблица 1.



0 9 10 16 0 0 0

Отношение,

θ

i

Симплекс метод решения задачи линейного программирования

Базис

Симплекс метод решения задачи линейного программирования

Симплекс метод решения задачи линейного программирования

Симплекс метод решения задачи линейного программирования

Симплекс метод решения задачи линейного программирования

Симплекс метод решения задачи линейного программирования

Симплекс метод решения задачи линейного программирования

Симплекс метод решения задачи линейного программирования


1 0

Симплекс метод решения задачи линейного программирования

72 9 9 0 1

Симплекс метод решения задачи линейного программирования

0 8
2 16

Симплекс метод решения задачи линейного программирования

24

Симплекс метод решения задачи линейного программирования

Симплекс метод решения задачи линейного программирования

1 0

Симплекс метод решения задачи линейного программирования

0 48
3 0

Симплекс метод решения задачи линейного программирования

108

Симплекс метод решения задачи линейного программирования

Симплекс метод решения задачи линейного программирования

0 0

-Симплекс метод решения задачи линейного программирования

1 72

∆j 384 3 -2 0 0 2 0

Zj 384 12 8 0 0 2 0

Изменяется базис в позиции направляющей строки. Базисным становится вектор, соответствующий направляющему столбцу, т. е. Симплекс метод решения задачи линейного программирования

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

Новые значения в направляющей строке получаем делением элементов этой строки на направляющий элемент.

Остальные элементы в небазисных столбцах и в столбце Симплекс метод решения задачи линейного программирования вычисляем по правилу треугольника.

Выбираем минимальную отрицательную оценку. Она определяет направляющий столбец.

Заполняем столбец «θ»

По минимальному значению определяем направляющую строку.

На пересечении направляющей строки и столбца находится направляющий элемент.

Заполнение второй таблицы осуществляется по аналогии с предыдущей.


Таблица 2.


0 9 10 16 0 0 0

Отношение,

θ

i

Симплекс метод решения задачи линейного программирования

Базис

Симплекс метод решения задачи линейного программирования

Симплекс метод решения задачи линейного программирования

Симплекс метод решения задачи линейного программирования

Симплекс метод решения задачи линейного программирования

Симплекс метод решения задачи линейного программирования

Симплекс метод решения задачи линейного программирования

Симплекс метод решения задачи линейного программирования


1 10

Симплекс метод решения задачи линейного программирования

8 1 1 0

Симплекс метод решения задачи линейного программирования

-Симплекс метод решения задачи линейного программирования

0 ______
2 16

Симплекс метод решения задачи линейного программирования

20

Симплекс метод решения задачи линейного программирования

0 1

-Симплекс метод решения задачи линейного программирования

Симплекс метод решения задачи линейного программирования

0 ______
3 0

Симплекс метод решения задачи линейного программирования

96

Симплекс метод решения задачи линейного программирования

0 0

Симплекс метод решения задачи линейного программирования

-Симплекс метод решения задачи линейного программирования

1 ______

∆j 400 5 0 0

Симплекс метод решения задачи линейного программирования

Симплекс метод решения задачи линейного программирования

0

Zj 400 14 10 16

Симплекс метод решения задачи линейного программирования

Симплекс метод решения задачи линейного программирования

0

Так как нет отрицательных оценок ∆j, значит выполняется признак оптимальности и не вводились искусственные переменные, то получено оптимальное решение.

Ответ:

Максимальное значение функции F max =400 достигается в точке с координатами:


Симплекс метод решения задачи линейного программирования=0

Симплекс метод решения задачи линейного программирования=8

Симплекс метод решения задачи линейного программирования=20

Симплекс метод решения задачи линейного программирования=0

Симплекс метод решения задачи линейного программирования=0

Симплекс метод решения задачи линейного программирования=96


Задача №2 (Метод Литтла)


Найти кратчайший путь в графе, заданном графически в виде чертежа, методом Литтла.


Симплекс метод решения задачи линейного программирования

Из чертежа запишем матрицу расстояний. (Расстояние от т.1 до т.2 равно:

Симплекс метод решения задачи линейного программирования , и т.д.)



1 2 3 4 5 6
1 18,87 49,48 51,86 80,51 97,42
2 18,87 32,06 34,48 65,15 84,01
3 49,48 32,06 31,76 61,19 83,20
4 51,86 34,48 31,76 32,14 53,15
5 80,51 65,15 61,19 32,14 22,14
6 97,42 84,01 83,20 53,15 22,14

Предположим что кратчайший путь будет следующим:


т.1→ т.2→ т.3→ т.4→ т.5→ т.6→т.1 и составит Симплекс метод решения задачи линейного программирования


Симплекс метод решения задачи линейного программирования


Решение: Первый этап.

Шаг 1. Приведем матрицу расстояний по строкам и столбцам

(в строке вычитаем из каждого элемента минимальный, затем в столбцах)



1 2 3 4 5 6
1 18,87 49,48 51,86 80,51 97,42 18,87
2 18,87 32,06 34,48 65,15 84,01 18,87
3 49,48 32,06 31,76 61,19 83,20 31,76
4 51,86 34,48 31,76 32,14 53,15 31,76
5 80,51 65,15 61,19 32,14 22,14 22,14
6 97,42 84,01 83,20 53,15 22,14 22,14


1 2 3 4 5 6
1 0 30,61 32,99 61,64 78,55
2 0 13,19 15,61 46,28 65,14
3 17,72 0,30 0 29,43 51,44
4 20,10 2,72 0 0,38 21,39
5 58,37 43,01 39,05 10,00 0
6 75,28 61,87 61,06 31,01 0

0 0 0 0 0 0


1 2 3 4 5 6
1 0 30,61 32,99 61,64 78,55
2 0 13,19 15,61 46,28 65,14
3 17,72 0,30 0 29,43 51,44
4 20,10 2,72 0 0,38 21,39
5 58,37 43,01 39,05 10,00 0
6 75,28 61,87 61,06 31,01 0

Шаг 2. Определим оценки нулевых клеток:


Симплекс метод решения задачи линейного программирования Симплекс метод решения задачи линейного программирования

Симплекс метод решения задачи линейного программирования Симплекс метод решения задачи линейного программирования

Симплекс метод решения задачи линейного программирования Симплекс метод решения задачи линейного программирования


Шаг 3. Вычеркиваем клетку с максимальной оценкой. Включаем данную клетку в путь обхода. (5 – 6)

Симплекс метод решения задачи линейного программирования


Шаг 4. Переписываем матрицу расстояний, накладывая запрет на одну из клеток для исключения преждевременного замыкания контура (в клетку 6-5 ставим ∞).



1 2 3 4 5
1 0 30,61 32,99 61,64
2 0 13,19 15,61 46,28
3 17,72 0,30 0 29,43
4 20,10 2,72 0 0,38
6 75,28 61,87 61,06 31,01

Далее повторяем шаги 1 – 4, пока не дойдем до одной клетки.


Второй этап.

Шаг 1. Приведем матрицу расстояний по строкам и столбцам.



1 2 3 4 5
1 0 30,61 32,99 61,64
2 0 13,19 15,61 46,28
3 17,72 0,30 0 29,43
4 20,10 2,72 0 0,38
6 75,28 61,87 61,06 31,01

0 0 0 0 0,38


1 2 3 4 5
1 0 30,61 32,99 61,26
2 0 13,19 15,61 45,90
3 17,72 0,30 0 29,05
4 20,10 2,72 0 0
6 75,28 61,87 61,06 31,01

Шаг 2. Определим оценки нулевых клеток:


Симплекс метод решения задачи линейного программирования Симплекс метод решения задачи линейного программирования

Симплекс метод решения задачи линейного программирования

Симплекс метод решения задачи линейного программирования Симплекс метод решения задачи линейного программированияСимплекс метод решения задачи линейного программирования


Шаг 3. Вычеркиваем клетку с максимальной оценкой. Включаем данную клетку в путь обхода. (1 – 2)


Симплекс метод решения задачи линейного программирования


Шаг 4. Переписываем матрицу расстояний, накладывая запрет на одну из клеток для исключения преждевременного замыкания контура (в клетку 2 – 1 ставим ∞).



1 3 4 5
2 13,19 15,61 45,90
3 17,72 0 29,05
4 20,10 0 0
6 75,28 61,06 31,01

Третий этап.

Шаг 1. Приведем матрицу расстояний по строкам и столбцам.


1 3 4 5
2 13,19 15,61 45,90
3 17,72 0 29,05
4 20,10 0 0
6 75,28 61,06 31,01

17,72 0 0 0


1 3 4 5
2 13,19 15,61 45,90 13,19
3 0 0 29,05 0
4 2,38 0 0 0
6 57,56 61,06 31,01 31,01


1 3 4 5
2 0 2,42 32,71
3 0 0 29,05
4 2,38 0 0
6 26,55 30,05 0

Шаг 2. Определим оценки нулевых клеток:


Симплекс метод решения задачи линейного программирования

Симплекс метод решения задачи линейного программирования Симплекс метод решения задачи линейного программирования

Симплекс метод решения задачи линейного программирования Симплекс метод решения задачи линейного программирования

Шаг 3. Вычеркиваем клетку с максимальной оценкой. Включаем данную клетку в путь обхода. (4 – 5)


Симплекс метод решения задачи линейного программирования


Шаг 4. Переписываем матрицу расстояний, накладывая запрет на одну из клеток для исключения преждевременного замыкания контура (в клетку 6 – 4 ставим ∞).



1 3 4
2 0 2,42
3 0 0
6 26,55 30,05

Четвертый этап.

Шаг 1. Приведем матрицу расстояний по строкам и столбцам.



1 3 4
2 0 2,42 0
3 0 0 0
6 26,55 30,05 26,55


1 3 4
2 0 2,42
3 0 0
6 0 3,50

Шаг 2. Определим оценки нулевых клеток:


Симплекс метод решения задачи линейного программирования


Шаг 3. Вычеркиваем клетку с максимальной оценкой. Включаем данную клетку в путь обхода. (3 – 4)


Симплекс метод решения задачи линейного программирования


Шаг 4. Переписываем матрицу расстояний, накладывая запрет на одну из клеток для исключения преждевременного замыкания контура (в клетку 6 – 3 ставим ∞).



1 3
2 0
6 0

Пятый этап.

Остались не задействованными связи 2 – 3 и 6 – 1.

В результате получаем следующую цепочку:


1→ 2→ 3 → 4→ 5→ 6 →1


Длина пути составляет:


L=18,87+32,06+31,76+32,14+22,14+97,42=234,39


это и есть кратчайший путь.


Симплекс метод решения задачи линейного программирования

Похожие рефераты: