48942 (Симплекс метод решения задачи линейного программирования)
Описание файла
Документ из архива "Симплекс метод решения задачи линейного программирования", который расположен в категории "". Всё это находится в предмете "информатика" из 1 семестр, которые можно найти в файловом архиве . Не смотря на прямую связь этого архива с , его также можно найти и в других разделах. Архив можно найти в разделе "контрольные работы и аттестации", в предмете "информатика, программирование" в общих файлах.
Онлайн просмотр документа "48942"
Текст из документа "48942"
Задача №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. Определим оценки нулевых клеток: