Содержание
- 2. Обозначим xij груз, перевозимый от i-го поставщика к j-му потребителю, сij – стоимость перевозки единицы груза.
- 3. Составим модель задачи
- 4. Модель закрытая, т.е. суммарные потребности равны суммарным затратам. Теорема Любая транспортная задача, у которой суммарный объем
- 5. Построение первоначального опорного плана Система ограничений ТЗ содержит m x n неизвестных и m+n уравнений.
- 6. Если сложить почленно уравнения подсистемы (1) и отдельно подсистемы (2) то получим два одинаковых уравнения. Следовательно
- 7. Если условия задачи представлены в матрице планирования, то клетки, в которых находятся отличные от нуля перевозки
- 8. Опорность плана при записи в виде таблицы означает его ацикличность , т.е. в таблице нельзя построить
- 9. Всякий план ТЗ содержащий более m+n-1 занятых клеток не является опорным, т.к. ему соответствует линейно зависимая
- 10. Построение циклов начинают с какой-либо занятой клетки и переходят по столбцу (или строке) к другой занятой
- 11. Существует несколько методов построения первоначального опорного плана.
- 12. Метод северо-западного угла Пусть условия ТЗ заданы таблицей.
- 13. Начинаем с первого потребителя В1 и первого поставщика А1. Сравниваем a1=100 и b1=200, a1 Запасы первого
- 14. Потребности В1 неудовлетворенны на 200-100=100 ед. Сравниваем этот остаток с запасами А2: 100
- 15. У А2 осталось 150 ед. груза. Отдаем их В2. Потребности В2 =200, Записываем 150 в клетку
- 16. Потребности В2 не удовлетворены на 50 ед. Берем их у А3 и переходим к В3 и
- 17. Начиная движение от занятой клетки А1В1 вернуться в нее, двигаясь только по занятым клеткам невозможно. Следовательно
- 18. Метод минимальной стоимости. Суть метода в том, что из всей таблицы стоимостей выбирают наименьшую и в
- 19. Пусть условия ТЗ заданы таблицей
- 20. Выбираем наименьшую стоимость, она помещена в клетке А1В4, т.к. а1=b4=100, то 100 помещаем в А1В4 и
- 21. Наименьшей является стоимость в А2В1 и А3В5. В А2В1 200 В А3В5 200
- 22. В таблице снова выбираем наименьшую стоимость и продолжим пока все запасы не будут распределены X=(x14=100, x21=200,
- 23. Метод двойного предпочтения. Если таблица большая, то перебор элементов сложен и используют этот метод. В каждом
- 24. Пусть условия ТЗ заданы таблицей
- 25. Отметим клетки c минимальной стоимостью по строкам
- 26. Отметим клетки c минимальной стоимостью по столбцам
- 27. Сначала заполним клетки А2В1, А1В4 А3В5 а затем А4В2
- 28. Далее заполним клетки по минимальной стоимости А2В3, А4В3 , А4В5 Получился вырожденный опорный план. Z=100·1+200·2+50·10+200·2+200·8+50·12+50·13=4250ед.
- 29. С помощью рассмотренных методов можно получить вырожденный или невырожденный опорный план. Оптимальный план можно найти с
- 30. Метод потенциалов Теорема Если план X* транспортной задачи является оптимальным, то ему соответствует система из m+n
- 31. Доказательство Транспортную задачу можно рассматривать как двойственную некоторой исходной задаче линейного программирования
- 32. Пусть каждому ограничению вида в исходной задаче соответствует переменная Ui (i=1,2,..m), а каждому ограничению вида переменная
- 33. План X* является оптимальным планом двойственной задачи, поэтому план Y*=(U*I, V*j) является оптимальным планом исходной задачи
- 34. На основании свойств двойственных задач получаем: ограничения исходной задачи, соответствующие положительным переменным оптимального плана двойственной задачи,
- 35. Из теоремы следует, что для того, чтобы опорный план был оптимальным, необходимо выполнение следующих условий: Для
- 36. Если хотя бы одна незанятая клетка не удовлетворяет этому условию, то план не оптимален и его
- 37. Построение системы потенциалов. Используем условие Систему потенциалов можно построить только для невырожденного плана. Он должен содержать
- 38. Пусть известен потенциал Ui тогда Если известен потенциал Vj тогда
- 39. В таблице выбираем строку с наибольшим количеством занятых клеток (А4) и полагаем U4=0. В А4 три
- 40. Определим эти потенциалы V2= C42-U4=8-0=8 V3= C43-U4=12-0=12 V5= C45-U4=13-0=13 C помощью U4 нельзя определить больше никакой
- 41. Поочередно просматриваем столбцы В2 В3 В5 , для которых потенциалы определены. В столбце В2 две занятые
- 42. Переходим к В5. В нем одна занятая клетка А3В5 , которая связывает V5 c неизвестным U3=C32-V5=2-13=-11
- 43. Построение системы потенциалов прервалось. Потенциалы U1 и V4 остались неопределенными, поскольку план вырожденный. Добавляем фиктивно занятую
- 44. Система потенциалов построена, уберем знаки подчеркивания и проверим правильность системы. Для этого проверяем для всех занятых
- 45. Проверка выполнения условия оптимальности для незанятых клеток План будет оптимальным, если для всех незанятых клеток выполняется
- 46. Для строки А1: -9 Для строки А2 : для А2В3 11> 10 или 11-10=1, 1 записываем
- 47. Выбор клетки, в которую следует послать перевозку Загрузке подлежит клетка соответствующая max[(Ui+Vj)-Cij] Таким образом, выбираем max(1;6;1)=6
- 48. Построение цикла и определение величины перераспределения груза В таблице m+n-1 занятых клеток, поэтому имеется единственный цикл,
- 49. Находим Q0=min xij, где xij – перевозки, стоящие в вершинах цикла со знаком “-”. Q0=min(50;50;0)=0. Следовательно,
- 50. Новый опорный план проверяется на оптимальность Строится новая система потенциалов Клетка А2В4 стала занятой и для
- 51. Проверяется выполнение условий оптимальности для каждой незанятой клетки. Значение V4 уменьшилось на 6 и в В4
- 52. Находим max(2;3;1;1)=3. А1В5 подлежит загрузке, отмечаем ее + и определяем цикл перераспределения. Q0=min(50;50;100)=50. По циклу 50
- 53. План улучшился на 150 единиц стоимости (произведение груза перемещенного в свободную клетку на величину (Ui+Vj)-Cij .
- 54. В полученном опорном плане изменяем систему потенциалов. Условию оптимальности не удовлетворяют 2 клетки А1В3 и А2В3,
- 55. Строим цикл перераспределения. Q0=min (50;0;100)=0. Нулевую перевозку перемещаем в А1В3 и получаем новый опорный план.
- 56. Вносим изменения в систему потенциалов
- 57. План оптимальный, его стоимость равна 4150 единиц.
- 58. Открытая(несбалансированная) модель транспортной задачи Возможны два случая открытой модели: Суммарные запасы превышают суммарные потребности Суммарные потребности
- 61. Открытая модель решается приведением к закрытой модели. В случае 1 вводится фиктивный потребитель Bn+1, потребности которого
- 62. Пример
- 64. При составлении первого опорного плана методом минимальной стоимости или двойного предпочтения необходимо наименьшую стоимость выбирать только
- 65. Ответ
- 67. Скачать презентацию