Автор статьи
Валерия
Эксперт по сдаче вступительных испытаний в ВУЗах
Задача 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 руб.
О сайте
Ссылка на первоисточник:
http://vniivega.nichost.ru/index.htm
Поделитесь в соцсетях: