Линейное программирование

Подсчитаем число занятых клеток таблицы, их 7. Значение целевой функции для этого опорного плана равно:

F = 14*30 + 5*190 + 7*230 + 19*50 + 12*90 + 10*260 + 7*150 = 8660

 

 

2.2.3 Метод аппроксимации  Фогеля.

 

Решение

 

Таблица 12 – Метод решения аппроксимации Фогеля

	В1	В2	В3	В4	В5		1	2	3	4  4	5
А1	13	14	15	5(190)	9(30)	220	4	4	5	5	-
А2	7(230)	19	17	10	12(50)	280	3	5	5	-	-
А3	9	12(170)	10(260)	13	7(70)	500	2	2	3	3	3
	230	170	260	190	150
1	2	2	5	5	2
2	2	2	5	-	2
3	-	2	5	-	2
4	-	2	5	-	2
5	-	0	0	-	0

 

Используя метод Фогеля, построим первый опорный план транспортной задачи. Для каждой строки и столбца таблицы условий найдем разности между двумя минимальными тарифами, записанными в данной строе или столбце, и поместим их в соответствующем дополнительном столбце или строке. Данный метод состоит в следующем: 
1. на каждой итерации находят разности между двумя наименьшими тарифами во всех строках и столбцах, записывая их в дополнительные столбец и строку таблицы; 2. находят максимальную разность и заполняют клетку с минимальной стоимостью в строке (столбце), которой соответствует данная разность. В результате получен опорный план, который является допустимым, так как все грузы из баз вывезены, потребность магазинов удовлетворена, а план соответствует системе ограничений транспортной задачи. Подсчитаем число занятых клеток таблицы, их 7.

Значение целевой функции для этого опорного плана равно:

F= 5*190 + 9*30 + 7*230 + 12*50 + 12*170 + 10*260 + 7*70 = 8560 

2.2.4 Оптимизация  плана аппроксимации Фогеля методом  потенциалов.

 

Решение

 

Таблица 13 - Опорный план метода наименьших затрат

База	Магазин					Запас продукции
	В1	В2	В3	В4	В5
А1	13	14(30)	15	5(190)	19	220
А2	7(230)	19(50)	17	10	12	280
А3	9	12(90)	10(260)	13	7(150)	500
Спрос на продукцию	230	170	260	190	150

 

Проверим оптимальность опорного плана. Найдем предварительные потенциалы ui, vi. по занятым клеткам таблицы, в которых ui + vi = cij, полагая, что u1 = 0.

 
u1+v2 =14; 0+v2 =14; v2 =14 
u2+v2 =19; 14+u2 =19; u2 =5 
u2+v1 =7; 5+v1 =7; v1 =2 
u3+v2 =12; 14+u3 =12; u3 =-2 
u3+v3 =10; -2+v3 =10; v3 =12 
u3+v5 =7; -2+v5 =7; v5 =9 
u1+v4 =5; 0+v4 =5; v4 =5 

Таблица 14 Оптимизация методом потенциалов

База	Магазин					Запас продукции
	В1	В2	В3	В4	В5
А1	13	14(30)	15	5(190)	19	220
А2	7(230)	19(50) -	17	10	12 +	280
А3	9	12(90) +	10(260)	13	7(150) -	500
Спрос на продукцию	230	170	260	190	150

 

 

 

Опорный план не является оптимальным, так как существуют оценки свободных клеток, для которых ui+vi >cij (2;5): 5 + 9 > 12; ∆25 = 5 + 9 - 12 = 2. Выбираем максимальную оценку свободной клетки (2;5): 12. Для этого в перспективную клетку (2;5) поставим знак «+», а в остальных вершинах многоугольника чередующиеся знаки «-», «+», «-».

Цикл приведен в таблице (2,5; 2,2; 3,2; 3,5; ). Из грузов хij стоящих в минусовых клетках, выбираем наименьшее, т.е. у = min (2, 2) = 50. Прибавляем 50 к объемам грузов, стоящих в плюсовых клетках и вычитаем 50 из Хij, стоящих в минусовых клетках. В результате получим новый опорный план.

Проверим оптимальность опорного плана. Найдем предварительные потенциалы ui, vi. по занятым клеткам таблицы, в которых ui + vi = cij, полагая, что u1 = 0.

 
u1+v2 =14; 0+v2 =14; v2 =14 
u3+v2 =12; 14+u3 =12; u3 =-2 
u3+v3 =10; -2+v3 =10; v3 =12 
u3+v5 =7; -2+v5 =7; v5 =9 
u2+v5 =12; 9+u2 =12; u2 =3 
u2+v1 =7; 3+v1 =7; v1 =4 
u1+v4 =5; 0+v4 =5; v4 =5

 
Таблица 15 - Оптимальный план метода потенциалов

База	Магазин					Запас продукции
	В1	В2	В3	В4	В5
А1	13	14(30)	15	5(190)	19	220
А2	7(230)	19	17	10	12(50)	280
А3	9	12(140)	10(260)	13	7(100)	500
Спрос на продукцию	230	170	260	190	150

 

Опорный план является оптимальным, так все оценки свободных клеток удовлетворяют условию ui + vi <= cij. Минимальные затраты составят: 
F = 14*30 + 5*190 + 7*230 + 12*50 + 12*140 + 10*260 + 7*100 = 8560

 

 

 

 

 

 

 

 

ЗАКЛЮЧЕНИЕ

 

 

В результате проделанной курсовой работы, мной были рассмотрены основные подходы и методы решения транспортной задачи, которая является одной из наиболее распространенных задач линейного программирования, а так же методы составления опорных планов методами: северо-западного угла F = 12980, наименьшего элемента F = 8660, методом Фогеля F = 8560. Выполнил оптимизацию плана, который  получил методом наименьшего элемента F = 8560. В задаче линейно программирования составил план выпуска трансформаторов, обеспечивающий предприятию наибольшую прибыль.

  Решение данных задач  позволяет  разработать наиболее рациональные  пути и способы транспортирования  товаров, устранить чрезмерно дальние, встречные, повторные перевозки. Все  это позволяет сократить время  продвижения товаров, уменьшает  затраты предприятий и фирм, связанные  с осуществлением процессов снабжения  сырьем, материалами, топливом, оборудованием  и т.д.

 

СПИСОК ИСПОЛЬЗОВАННЫХ ИСТОЧНИКОВ

 

 

1. Бодров, В.И. Математические методы принятия решений / Т.Я. Лазарева,  Ю.Ф.Мартемьянов. – М. : Издательство ТГТУ, 2004. – 200с.

 2.Еремин, И. И., Введение в теорию линейного программирования /

Астафьев Н.Н., Еремин И.И. - М.; 1976 г. – 400с.

3. Карманов, В.Г. Математическое программирование./ В.Г. Карманов –М.: Наука, 1986.- 290с.

4. Крюков, Б.В. Вопросы линейного  программирования / Б.В. Крюков, Н.П. Хазяин // Линейное программирование. –М., 1976. –С. 11-22.

5. Линейное программирование, 11апреля 2004г. / [ЭЛЕКТРОННЫЙ РЕСУРС]http: // www.wikipedia.ru