Методы принятия управленческих решений

Опорный план является оптимальным, так  все оценки свободных клеток удовлетворяют  условию u_i + v_i<= c_ij.

Минимальные затраты составят:

S = 9*15 + 3*65 + 4*15 + 7*45 + 4*65 + 7*15 + 4*20  = 1150

 

Поиск третьего опорного плана.

1. Используя метод Фогеля, построим  первый опорный план транспортной  задачи. Для каждой строки и  столбца таблицы условий найдем  разности между двумя минимальными  тарифами, записанными в данной  строе или столбце, и поместим их в соответствующем дополнительном столбце или строке.

Данный метод состоит в следующем:

1. на каждом шагу  находят  разности между двумя наименьшими  тарифами во всех строках и  столбцах, записывая их в дополнительные  столбец и строку таблицы;

2. находят максимальную разность и заполняют клетку с минимальной стоимостью в строке (столбце), которой соответствует данная разность.

3. Построим таблицу:

 

 

 

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

2. Подсчитаем число  занятых клеток таблицы, их 7, а  должно быть m + n - 1 = 7. Следовательно,  опорный план является невырожденным.

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

Этап II. Улучшение  опорного плана.

Проверим оптимальность  опорного плана. Найдем предварительные потенциалыu_i, v_i. по занятым клеткам таблицы, в которых u_i + v_i = c_ij, полагая, что u₁ = 0.

Опорный план является оптимальным, так все оценки свободных клеток удовлетворяют условию u_i + v_i<= c_ij.

Минимальные затраты  составят:

S = 9*15 + 3*65 + 4*15 + 7*45 + 4*65 + 7*15 + 4*20 = 1150

 

 

Задание  2

В предыдущих исходных данных заменить А4 = 60

 

Решение

1.Метод северо-западного угла.

Поиск первого  опорного плана.

Проверим необходимое  и достаточное условие разрешимости задачи.

∑a = 95 + 45 + 65 + 60 = 265

∑b = 75 + 85 + 65 + 15 = 240

 

Как видно, суммарная  потребность груза в пунктах  назначения превышает запасы груза  на базах. Следовательно, модель исходной транспортной задачи является открытой. Чтобы получить закрытую модель, введем дополнительную (фиктивную) базу с запасом груза, равным 25(265-240). Тарифы перевозки единицы груза из базы во все магазины полагаем равны нулю.

Занесем исходные данные в распределительную таблицу.

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

2. Подсчитаем число  занятых клеток таблицы, их 8, а  должно быть m + n - 1 = 8. Следовательно,  опорный план является невырожденным.

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

 

Этап II. Улучшение  опорного плана.

Проверим оптимальность  опорного плана. Найдем предварительные потенциалыu_i, v_i. по занятым клеткам таблицы, в которых u_i + v_i = c_ij, полагая, что u₁ = 0.

Опорный план не является оптимальным, так как существуют оценки свободных клеток, для которых u_i + v_i>c_ij

Выбираем максимальную оценку свободной клетки (1;4): 4

Для этого в перспективную  клетку (1;4) поставим знак «+», а в  остальных вершинах многоугольника чередующиеся знаки «-», «+», «-».

Из грузов х_ij стоящих в минусовых клетках, выбираем наименьшее, т.е. у = min (4, 4) = 15. Прибавляем 15 к объемам грузов, стоящих в плюсовых клетках и вычитаем 15 из Х_ij, стоящих в минусовых клетках. В результате получим новый опорный план.

Проверим оптимальность  опорного плана. Найдем предварительные потенциалыu_i, v_i. по занятым клеткам таблицы, в которых u_i + v_i = c_ij, полагая, что u₁ = 0.

Опорный план не является оптимальным, так как существуют оценки свободных клеток, для которых u_i + v_i>c_ij

Выбираем максимальную оценку свободной клетки (1;3): 3

Для этого в перспективную  клетку (1;3) поставим знак «+», а в остальных вершинах многоугольника чередующиеся знаки «-», «+», «-».

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

Проверим оптимальность  опорного плана. Найдем предварительные потенциалыu_i, v_i. по занятым клеткам таблицы, в которых u_i + v_i = c_ij, полагая, что u₁ = 0.

Опорный план не является оптимальным, так как существуют оценки свободных клеток, для которых u_i + v_i>c_ij

Выбираем максимальную оценку свободной клетки (2;1): 7

Для этого в перспективную  клетку (2;1) поставим знак «+», а в  остальных вершинах многоугольника чередующиеся знаки «-», «+», «-».

Из грузов х_ij стоящих в минусовых клетках, выбираем наименьшее, т.е. у = min (3, 3) = 25. Прибавляем 25 к объемам грузов, стоящих в плюсовых клетках и вычитаем 25 из Х_ij, стоящих в минусовых клетках. В результате получим новый опорный план.

Проверим оптимальность опорного плана. Найдем предварительные потенциалыu_i, v_i. по занятым клеткам таблицы, в которых u_i + v_i = c_ij, полагая, что u₁ = 0.

Опорный план не является оптимальным, так как существуют оценки свободных клеток, для которых u_i + v_i>c_ij

Выбираем максимальную оценку свободной клетки (4;2): 4

Для этого в перспективную  клетку (4;2) поставим знак «+», а в  остальных вершинах многоугольника чередующиеся знаки «-», «+», «-».

Из грузов х_ij стоящих в минусовых клетках, выбираем наименьшее, т.е. у = min (2, 2) = 20. Прибавляем 20 к объемам грузов, стоящих в плюсовых клетках и вычитаем 20 из Х_ij, стоящих в минусовых клетках. В результате получим новый опорный план.

Проверим оптимальность  опорного плана. Найдем предварительные потенциалыu_i, v_i. по занятым клеткам таблицы, в которых u_i + v_i = c_ij, полагая, что u₁ = 0.

Опорный план не является оптимальным, так как существуют оценки свободных клеток, для которых u_i + v_i>c_ij

Выбираем максимальную оценку свободной клетки (4;1): 7

Для этого в перспективную клетку (4;1) поставим знак «+», а в остальных вершинах многоугольника чередующиеся знаки «-», «+», «-».

Из грузов х_ij стоящих в минусовых клетках, выбираем наименьшее, т.е. у = min (4, 3) = 15. Прибавляем 15 к объемам грузов, стоящих в плюсовых клетках и вычитаем 15 из Х_ij, стоящих в минусовых клетках. В результате получим новый опорный план.

Проверим оптимальность  опорного плана. Найдем предварительные потенциалыu_i, v_i. по занятым клеткам таблицы, в которых u_i + v_i = c_ij, полагая, что u₁ = 0.

Опорный план не является оптимальным, так как существуют оценки свободных клеток, для которых u_i + v_i>c_ij

Выбираем максимальную оценку свободной клетки (1;5): 0

Для этого в перспективную  клетку (1;5) поставим знак «+», а в  остальных вершинах многоугольника чередующиеся знаки «-», «+», «-».

Из грузов х_ij стоящих в минусовых клетках, выбираем наименьшее, т.е. у = min (1, 1) = 15. Прибавляем 15 к объемам грузов, стоящих в плюсовых клетках и вычитаем 15 из Х_ij, стоящих в минусовых клетках. В результате получим новый опорный план.

Проверим оптимальность  опорного плана. Найдем предварительные потенциалыu_i, v_i. по занятым клеткам таблицы, в которых u_i + v_i = c_ij, полагая, что u₁ = 0.

 

Опорный план является оптимальным, так все оценки свободных клеток удовлетворяют условию u_i + v_i<= c_ij.

Минимальные затраты  составят:

S = 3*65 + 4*15 + 0*15 + 7*45 + 4*65 + 7*30 + 4*20 + 0*10 = 1120

 

 

Поиск первого  опорного плана.

1. Используя метод  наименьшей стоимости, построим  первый опорный план транспортной  задачи.

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

2. Подсчитаем число  занятых клеток таблицы, их 8, а  должно быть m + n - 1 = 8. Следовательно, опорный план является невырожденным.

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

Этап II. Улучшение  опорного плана.

Проверим оптимальность  опорного плана. Найдем предварительные потенциалыu_i, v_i. по занятым клеткам таблицы, в которых u_i + v_i = c_ij, полагая, что u₁ = 0.

 

Опорный план является оптимальным, так все оценки свободных клеток удовлетворяют условию u_i + v_i<= c_ij.

Минимальные затраты  составят:

S = 3*65 + 4*15 + 0*15 + 7*45 + 4*65 + 7*30 + 4*20 + 0*10 = 1120

 

Поиск третьего опорного плана.

1. Используя метод  Фогеля, построим первый опорный  план транспортной задачи. Для  каждой строки и столбца таблицы  условий найдем разности между  двумя минимальными тарифами, записанными  в данной строе или столбце,  и поместим их в соответствующем дополнительном столбце или строке.

Данный метод состоит  в следующем:

1. на каждой шагу  находят разности между двумя  наименьшими тарифами во всех  строках и столбцах, записывая  их в дополнительные столбец  и строку таблицы;

2. находят максимальную разность и заполняют клетку с минимальной стоимостью в строке (столбце), которой соответствует данная разность.

3. Построим таблицу:

 

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

2. Подсчитаем число  занятых клеток таблицы, их 8, а  должно быть m + n - 1 = 8. Следовательно,  опорный план является невырожденным.

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

Этап II. Улучшение  опорного плана.

Проверим оптимальность  опорного плана. Найдем предварительные потенциалыu_i, v_i. по занятым клеткам таблицы, в которых u_i + v_i = c_ij, полагая, что u₁ = 0.

Опорный план является оптимальным, так все оценки свободных клеток удовлетворяют условию u_i + v_i<= c_ij.

Минимальные затраты  составят:

S = 3*65 + 4*15 + 0*15 + 7*45 + 4*65 + 7*30 + 4*20 + 0*10 = 1120

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Заключение

 

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