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

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

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

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

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

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

Таблица 0.

9 10 16

Отношение,

θ

i Базис
1 360 18 15 12 1 30
2 192 6 4 8 1 24
3 180 5 3 3 1 60
∆j -9 -10 -16
Zj

Zj вычисляется по формуле

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

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

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

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

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

Таблица 1.

9 10 16

Отношение,

θ

i Базис
1 72 9 9 1 8
2 16 24 1 48
3 108 - 1 72
∆j 384 3 -2 2
Zj 384 12 8 2

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

Столбец становится базисным, то есть единичным.

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

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

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

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

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

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

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

Таблица 2.

9 10 16

Отношение,

θ

i Базис
1 10 8 1 1 - ______
2 16 20 1 - ______
3 96 - 1 ______
∆j 400 5
Zj 400 14 10 16

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

Ответ:

Максимальное значение функции Fmax =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 30,61 32,99 61,64 78,55
2 13,19 15,61 46,28 65,14
3 17,72 0,30 29,43 51,44
4 20,10 2,72 0,38 21,39
5 58,37 43,01 39,05 10,00
6 75,28 61,87 61,06 31,01

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

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

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

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

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

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

Второй этап.

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

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

1 2 3 4 5
1 30,61 32,99 61,26
2 13,19 15,61 45,90
3 17,72 0,30 29,05
4 20,10 2,72
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 29,05
4 20,10
6 75,28 61,06 31,01

Третий этап.

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

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

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

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

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


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

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

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

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

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

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

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

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

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

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


1 3
2
6

Пятый этап.

Остались не задействованными связи 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

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

еще рефераты
Еще работы по информатике, программированию