ЭММ. Вариант 5. Задача 1 Графический метод решения задач линейногопрограммирования. Составить математическую модель по условию задачи
 Скачать 171.28 Kb.
|
|
Применяя теорему двойственности, получим решение двойственной задачи по известному решению исходной задачи. Найдем решение двойственной задачи у* воспользовавшись второй теоремой двойственности и известным оптимальным планом х*. Поскольку x1>0, 1-е ограничение в двойственной задаче будет равенством. Поскольку x2>0, 2-е ограничение в двойственной задаче будет равенством. Таким образом, решение двойственной задачи сводится к решению уравнений при следующих условиях: y3 = 0 y1+y2+y3 = 40 4y1+y2+y3 = 60 200y1+80y2+140y3 → min или y1+y2 = 40 4y1+y2 = 60 200y1+80y2+140y3 → min Обоснование эффективности оптимального плана. При подстановке оптимальных двойственных оценок в систему ограничений двойственной задачи получим: 1*62/3 + 1*331/3 + 1*0 = 40 = 40 4*62/3 + 1*331/3 + 1*0 = 60 = 60 3*62/3 + 2*331/3 + 2*0 = 862/3 > 80 1-ое ограничение двойственной задачи выполняется как равенство. Это означает, что 1-й продукт экономически выгодно производить (убытки от производства этого вида продукции отсутствуют), а его использование предусмотрено оптимальным планом прямой задачи (x1>0). 2-ое ограничение двойственной задачи выполняется как равенство. Это означает, что 2-й продукт экономически выгодно производить (убытки от производства этого вида продукции отсутствуют), а его использование предусмотрено оптимальным планом прямой задачи (x2>0). 3-ое ограничение выполняется как строгое неравенство, т.е. продукцию 3-го вида производить экономически не выгодно. И действительно в оптимальном плане прямой задачи x3 = 0. При этом разница между ценами (862/3 - 80 = 62/3) показывает величину изменения целевой функции F(x) при введении дополнительной единицы xi. Задача 3 Транспортная задача В m заводах имеется однородный груз продукции в количествах m а1 ,а2 ,...., аm . Этот груз нужно перевести n потребителям, потребности которых равны n b1 ,b2 ,..., bn . Стоимость перевозки единицы груза из i – го завода j – ому потребителю равна сij (таблица 3). Требуется составить план перевозки груза с заводов потребителям, при котором суммарные расходы на перевозку будут минимальными.
Решение: Исходная таблица:
Транспортная задача имеет закрытый тип, так как суммарный запас груза равен суммарным потребностям. Находим опорный план по правилу минимального элемента: Введем некоторые обозначения: Ai* - излишек нераспределенного груза от поставщика Ai Bj* - недостача в поставке груза потребителю Bj Находим незанятую клетку с минимальным тарифом: (1,2). Помещаем туда меньшее из чисел A1*=500 и B2*=400 Находим незанятую клетку с минимальным тарифом: (3,4). Помещаем туда меньшее из чисел A3*=800 и B4*=350 Находим незанятую клетку с минимальным тарифом: (1,3). Помещаем туда меньшее из чисел A1*=100 и B3*=750 Находим незанятую клетку с минимальным тарифом: (2,3). Помещаем туда меньшее из чисел A2*=700 и B3*=650 Находим незанятую клетку с минимальным тарифом: (3,1). Помещаем туда меньшее из чисел A3*=450 и B1*=500 Находим незанятую клетку с минимальным тарифом: (2,1). Помещаем туда меньшее из чисел A2*=50 и B1*=50
Целевая функция F=8750 Решаем задачу методом потенциалов: Примем некоторые обозначения: i - индекс строки; j - индекс столбца; m - количество поставщиков; n - количество потребителей. Этап 1 Полагая потенциал U1=0, определяем остальные потенциалы из соотношения Ui+Vj=Ci,j(i=1..m, j=1..n), просматривая все занятые клетки. Потенциалы Ui: U1=0 V2=C1,2-U1= 2 V3=C1,3-U1= 3 U2=C2,3-V3=3 V1=C2,1-U2= 4 U3=C3,1-V1=2 V4=C3,4-U3= 0 Определяем значения оценок Si,j=Ci,j-(Ui+Vj) для всех свободных клеток: S1,1 = c1,1 - (u1 + v1) = 1. S1,4 = c1,4 - (u1 + v4) = 4. S2,2 = c2,2 - (u2 + v2) = 3. S2,4 = c2,4 - (u2 + v4) = 2. S3,2 = c3,2 - (u3 + v2) = 5. S3,3 = c3,3 - (u3 + v3) = 2. Так как все оценки Si,j>=0, то полученный план является оптимальным. Транспортная задача решена.
| ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||