Решение задач линейного программирования в Excel

Разработчик доц., к.ф.-м.н. Манита Л.А.

 

 

 

Московский  институт электроники и математики НИУ ВШЭ

 

 

 

 

 

 

Отчет

студентов группы ПИ-31

 

 

 

 

 

 

 

 

Самоходкина Александра Сергеевича

Содыль Наталии Евгеньевны

 

по курсовой работе

 

«Решение задач  линейного программирования в Excel»

 

 

 

Вариант 123

 

 

 

 

 

 

 

 

 

 

 

Москва 2013

Требуется определить план перевозки кирпича строительным полигонам, обеспечивающий минимальную  стоимость перевозки. На строительном полигоне имеются пять кирпичных завода, объем производства, которых в сутки равен 600, 600, 500, 650 и 600 т. Заводы удовлетворяют потребности семи строительных объектов соответственно в количестве 250, 450, 300, 450, 300, 200, 450 т. Оставшийся кирпич отправляют по ж/д в другие районы. Кирпич на строительные объекты доставляется автотранспортом. Стоимость перевозки 1 т. кирпича автотранспортом удовлетворяет условию С=25+4(s-1), где s-расстояние от завода до объекта.

 

 

Изменится ли решение  если запретить перевозку с первого  завода на второй и третий объекты?

 

1.Математическая постановка задачи.

Переменными (неизвестными) транспортной задачи являются x_ij , i=1,2,...,m j=1,2,...,n — объемы перевозок от i-го поставщика каждому j-му потребителю. 
Эти переменные могут быть записаны в виде матрицы перевозок:

Так как произведение C_ij*X_ij определяет затраты на перевозку груза от i-го поставщика j-му потребителю, то суммарные затраты на перевозку всех грузов равны:

По условию задачи требуется обеспечить минимум суммарных  затрат. 
Система ограничений задачи состоит из двух групп уравнений. 
Первая группа из m уравнений описывает тот факт, что запасы всех m поставщиков вывозятся полностью и имеет вид: 

Вторая группа из n уравнений  выражает требование удовлетворить  запросы всех n потребителей полностью и имеет вид:

Учитывая условие неотрицательности  объемов перевозок математическая модель выглядит следующим образом:

, где m=5, n=7

2. Решение задачи с  помощью Excel

Введем данные на рабочем листе. Воспользуемся средством поиска решений. Сохраним найденные отчеты и решение.

Рис. 1: решение в задаче

Оптимальное решение  задачи(рис.1). Минимальная стоимость  перевозок составляет 159600 у.е.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Отчеты к  задаче

1)Отчет по  результатам

2)Отчет по  устойчивости

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

3)Отчет по  пределам

 

 

 

 

 

3.Анализ решений

Из 1-го склада необходимо груз направить в 4-й магазин (400), в 6-й магазин (200) 
Из 2-го склада необходимо груз направить в 2-й магазин (450), в 3-й магазин (100), в 4-й магазин (50) 
Из 3-го склада необходимо весь груз направить в 7-й магазин 
Из 4-го склада необходимо груз направить в 3-й магазин (200), в 5-й магазин (300) 
Из 5-го склада необходимо груз направить в 1-й магазин (250), в 7-й магазин (350) 
На 3-ом складе остался невостребованным груз в количестве 400 ед.

Оптимальный план является вырожденным, так как базисная переменная x₃₈=0. 
На 4-ом складе остался невостребованным груз в количестве 150 ед. 
Оптимальный план является вырожденным, так как базисная переменная x₄₈=0. 
Задача имеет множество оптимальных планов, поскольку оценка для (1;3) равна 0.

4.Двойственная  задача линейного программирования

Математическая модель транспортной задачи:  
F = ∑∑c_ijx_ij,    (1)  
при условиях:  
∑x_ij = a_i,  i = 1,2,…, m,   (2)  
∑x_ij = b_j,  j = 1,2,…, n,   (3)  
С целью составления двойственной задачи переменные x_ij в условии (2) заменим на u₁, u₂, u_i,.., u_m, а переменные x_ij в условия (3) на v₁, v₂, v_j,.., v_n.  
Поскольку каждая переменная x_ij входит в условия (2,3) и целевую функцию (1) по одному разу, то двойственную задачу по отношению к прямой транспортной задаче можно сформулировать следующим образом.  
Требуется найти не отрицательные числа u_i (при i  = 1,2,…,m) и v_j (при j = 1,2,..,n), обращающие в максимум целевую функцию  
G = ∑a_iu_i + ∑b_jv_j  
при условии  
u_i + v_j ≤ c_ij, i = 1,2,..,m; j = 1,2,..,n где m=5 n=7  (4)  
В систему условий (4) будет mxn неравенств. По теории двойственности для оптимальных планов прямой и двойственной задачи для всех i,j должно быть:  
u_i + v_j ≤ c_ij, если x_ij = 0,  
u_i + v_j = c_ij, если x_ij ≥ 0,  
Эти условия являются необходимыми и достаточными признаками оптимальности плана транспортной задачи.  
Числа u_i , v_j называются потенциалами. Причем число u_i называется потенциалом поставщика, а число v_j – потенциалом потребителя.  
По первой теореме двойственности в оптимальном решении значения целевых функций прямой и двойственных задач совпадают: F = G.