Задача №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
это и есть кратчайшийпуть.
/>