Контрольное задание по дисциплине
«Методы оптимальных решений»
Задача 1
Поставить задачу линейного программирования и найти оптимальное решение в ситуации: «Грузоперевозчик покупает автомобили. Бюджет покупки – 150 д.е. Цена 3-тонного автомобиля составляет 4 д.е., 5-тонного – 5 д.е. Возможности грузоперевозчика по техническому обслуживанию автомобилей – не более 20 единиц 3-тонных автомобилей сразу и не более 18 единиц 5-тонных. Сколько и каких автомобилей купить для обеспечения максимальной суммарной грузоподъемности автопарка».
Решение:
Обозначим за х1 – количество закупаемых 3-тонников, х2 – количество закупаемых 53-тонников.
Целевая функция – суммарная грузоподъемность автопарка:
Ограничения:
Решим задачу графическим методом.
Смещаем линию уровня до крайнего положения в выделенной области:
Из рисунка видно, что точка максимума – точка А:
4×1+5×2=150
x2=18
Откуда:
x1 = 15, x2 = 18
F(X) = 3*15 + 5*18 = 135
Ответ: Следует закупать 15 ед. 3-тонников и 18 ед. 5-тонников. При этом будем максимальная грузоподъемность автопарка в 135 тонн.
Задача 2
Для прямой задачи линейного программирования составить двойственную. Найти оптимальные решения задач.
Решение:
Канонический вид ограничений:
-1×1-2×2 + 1×3-1×4 + 0x5 = 1
2×1-1×2 + 2×3 + 0x4 + 1×5 = 4
Введем искусственные переменные:
F(X) = 12×1 — Mx6 → max
-1×1-2×2 + 1×3-1×4 + 0x5 + 1×6 = 1
2×1-1×2 + 2×3 + 0x4 + 1×5 + 0x6 = 4
Решаем задачу симплекс методом
Опорный план оптимален:
x1 = 0.5, x2 = 0, x3 = 1.5
F(X) = 12*0.5 = 6
Двойственная задача
Z=-y1+4y2 → min
y1 ≥ 0
y2 ≥ 0
y1+2y2≥12
2y1-y2≥0
-y1+2y2≥0
Найдем решение двойственной задачи из решения прямой задачи:
Y = C*A-1 =
Оптимальный план двойственной задачи:
y1 = 6, y2 = 3
Z(Y) = -1*6+4*3 = 6
Задача 3
Составить математическую модель, найти оптимальный план перевозок и оптимальные издержки в транспортной задаче, заданной таблицами.
Транспортные издержки на маршруте на единицу груза.
Решение:
Задача закрытая, поскольку:
∑a = 90 + 400 + 110 = 600
∑b = 140 + 300 + 160 = 600
Математическая модель:
Целевая функция:
F = ∑∑cijxij=2×11 + 5×12 + 2×13 + 4×21 + 1×22 + 5×23 + 3×31 + 6×32 + 8×33 → min
Ограничения:
x11 + x12 + x13 = 90
x21 + x22 + x23 =400
x31 + x32 + x33 = 110
x11 + x21 + x31 = 140
x12 + x22 + x32 = 300
x13 + x23 + x33 = 160
Значение целевой функции для этого опорного плана равно:
F(x) = 2*90 + 1*300 + 5*100 + 3*50 + 8*60 = 1610
Метод потенциалов:
u1 = 0 u1 = 0 u1 = 0.
u1 + v1 = 2 0 + v1 = 2 v1 = 2
u3 + v1 = 3 2 + u3 = 3 u3 = 1
u3 + v3 = 8 1 + v3 = 8 v3 = 7
u2 + v3 = 5 7 + u2 = 5 u2 = -2
u2 + v2 = 1 -2 + v2 = 1 v2 = 3
Считаем оценки свободных клеток:
∆ cij= cij – (ui + vj )
опорный план не является оптимальным.
В клетку (1;3) добавляем поставку в 60 ед. груза по циклу:
1,3 → 1,1 → 3,1 → 3,3.
Ответ:
Оптимальный план:
Оптимальные издержки: 1280 руб.
Задача 4.
Составить математическую модель, найти оптимальный план перевозок и оптимальные издержки в транспортной задаче, заданной таблицами.
Решение:
Задача отрытая, поскольку:
∑a = 100 + 200 + 70 = 370
∑b = 190 + 120 + 10 = 320
Введем фиктивную потребность с потребностью 370-320=50.
Занесем исходные данные в распределительную таблицу.
190 120 10 50
100 4 2 1 0
200 1 5 3 0
70 1 2 6 0
Математическая модель:
Целевая функция:
F = ∑∑cijxij = 4×11 + 2×12 + 1×13 + 0x14 + 1×21 + 5×22 + 3×23 + 0x24 + 1×31 + 2×32 + 6×33 + 0x34 → min
Ограничения:
x11 + x12 + x13 + x14 = 100
x21 + x22 + x23 + x24 = 200
x31 + x32 + x33 + x34 = 70
x11 + x21 + x31 = 190
x12 + x22 + x32 = 120
x13 + x23 + x33 = 10
x14 + x24 + x34 = 50
xij ≥ 0
Метод минимальной стоимости:
190 120 10 50
100 4 2
90 1
10 0
200 1
190 5 3 0
10
70 1 2
30 6 0
40
F(x) = 2*90 + 1*10 + 1*190 + 0*10 + 2*30 + 0*40 = 440
Метод потенциалов:
u1 = 0 u1 = 0 u1 = 0.
u1 + v2 = 2 0 + v2 = 2 v2 = 2
u3 + v2 = 2 2 + u3 = 2 u3 = 0
u3 + v4 = 0 0 + v4 = 0 v4 = 0
u2 + v4 = 0 0 + u2 = 0 u2 = 0
u2 + v1 = 1 0 + v1 = 1 v1 = 1
u1 + v3 = 1 0 + v3 = 1 v3 = 1
Считаем оценки свободных клеток:
Опорный план является оптимальным:
F(Х) = 2*90 + 1*10 + 1*190 + 0*10 + 2*30 + 0*40 = 440
Ответ:
Оптимальный план:
Оптимальные издержки: 440 руб.