транспортная задача — копия. Задача. Математическая модель транспортной задачи
 Скачать 25.74 Kb.
|
1 2 Транспортная задача. Математическая модель транспортной задачи: F = ∑∑cijxij, (1) при условиях: ∑xij = ai, i = 1,2,…, m, (2) ∑xij = bj, j = 1,2,…, n, (3) xij ≥ 0 Запишем экономико-математическую модель для нашей задачи. Переменные: x11 – количество груза из 1-го склада к 1-у потребителю. x12 – количество груза из 1-го склада к 2-у потребителю. x13 – количество груза из 1-го склада к 3-у потребителю. x21 – количество груза из 2-го склада к 1-у потребителю. x22 – количество груза из 2-го склада к 2-у потребителю. x23 – количество груза из 2-го склада к 3-у потребителю. x31 – количество груза из 3-го склада к 1-у потребителю. x32 – количество груза из 3-го склада к 2-у потребителю. x33 – количество груза из 3-го склада к 3-у потребителю. Ограничения по запасам: x11 + x12 + x13 ≤ 90 (для 1 базы) x21 + x22 + x23 ≤ 400 (для 2 базы) x31 + x32 + x33 ≤ 110 (для 3 базы) Ограничения по потребностям: x11 + x21 + x31 = 140 (для 1-го потребителя.) x12 + x22 + x32 = 300 (для 2-го потребителя.) x13 + x23 + x33 = 160 (для 3-го потребителя.) Целевая функция: 2x11 + 5x12 + 2x13 + 4x21 + 1x22 + 5x23 + 3x31 + 6x32 + 8x33 → min С целью составления двойственной задачи переменные xij в условии (2) заменим на u1, u2, ui,.., um, а переменные xij в условия (3) на v1, v2, vj,.., vn. Поскольку каждая переменная xij входит в условия (2,3) и целевую функцию (1) по одному разу, то двойственную задачу по отношению к прямой транспортной задаче можно сформулировать следующим образом. Требуется найти не отрицательные числа ui (при i = 1,2,…,m) и vj (при j = 1,2,..,n), обращающие в максимум целевую функцию: G = ∑aiui + ∑bjvj при условии: ui + vj ≤ cij, i = 1,2,..,m; j = 1,2,..,n (4) В систему условий (4) будет mxn неравенств. По теории двойственности для оптимальных планов прямой и двойственной задачи для всех i,j должно быть: ui + vj ≤ cij, если xij = 0, ui + vj = cij, если xij ≥ 0, Эти условия являются необходимыми и достаточными признаками оптимальности плана транспортной задачи. Числа ui , vj называются потенциалами. Причем число ui называется потенциалом поставщика, а число vj – потенциалом потребителя. По первой теореме двойственности в оптимальном решении значения целевых функций прямой и двойственных задач совпадают: F = G. Математическая модель двойственной задачи: U – переменные для складов, поставщиков; V - переменные для магазинов, потребителей. U1 + V1≤2 U1 + V2≤5 U1 + V3≤2 U2 + V1≤4 U2 + V2≤1 U2 + V3≤5 U3 + V1≤3 U3 + V2≤6 U3 + V3≤8 G(y)=140U1 + 300U2 + 160U3 + 90V1 + 400V2 + 110V3 → max Стоимость доставки единицы груза из каждого пункта отправления в соответствующие пункты назначения задана матрицей тарифов
Проверим необходимое и достаточное условие разрешимости задачи. ∑a = 90 + 400 + 110 = 600 ∑b = 140 + 300 + 160 = 600 Условие баланса соблюдается. Запасы равны потребностям. Следовательно, модель транспортной задачи является закрытой. Занесем исходные данные в распределительную таблицу.
1 2 |