Задачи по "Линейному программированию"
Автор: Пинф Pinf • Сентябрь 20, 2022 • Задача • 280 Слов (2 Страниц) • 114 Просмотры
[pic 1]
Решим задачу методом Гомори.
Для этого сначала решаем задачу симплекс-методом
[pic 2]
Строим таблицу
[pic 3]
[pic 4]
[pic 5]
[pic 6]
[pic 7]
[pic 8]
----------------------
Итерация 1:
Ведущий столбец: 3
Ведущая строка: 3
----------------------
Итерация 2:
Ведущий столбец: 2
Ведущая строка: 2
----------------------
Итерация 3:
Ведущий столбец: 5
Ведущая строка: 1
----------------------
Итерация 4:
Ведущий столбец: 1
Ведущая строка: 2
----------------------
Среди значений коэффициентов целевой функции нет положительных. Поэтому задача решена!
x1 = 2
x2 = 0
x3 = 1
x4 = 0
x5 = 5
Значение целевой функции: Fmin = -2
Теперь используем метод Гомори.
[pic 9]
[pic 10]
[pic 11]
[pic 12]
[pic 13]
[pic 14]
[pic 15]
[pic 16]
[pic 17]
[pic 18]
----------------------------
Итерация 1:
Ведущий столбец: 4
Ведущая строка: 6
----------------------------
Итерация 2:
Ведущий столбец: 1
Ведущая строка: 5
----------------------------
Итерация 3:
Ведущий столбец: 2
Ведущая строка: 4
----------------------------
Итерация 4:
Ведущий столбец: 5
Ведущая строка: 4
----------------------------
Итерация 5:
Ведущий столбец: 10
Ведущая строка: 2
----------------------------
Итерация 6:
Ведущий столбец: 11
Ведущая строка: 3
----------------------------
Среди значений коэффициентов целевой функции нет отрицательных. Поэтому найдено оптимальное решение.
x1 = 12/5
x2 = 0
x3 = 0
x4 = 1/5
x5 = 28/5
Так как исходной задачей был поиск минимума, оптимальное решение есть свободный член строки F, взятый с противоположным знаком.
Значение целевой функции: Fmin = -11/5
Получившееся оптимальное решение нецелочисленное. Среди свободных членов находим переменную с максимальным дробным числом:
...