Содержание
- 2. Алгоритм метода потенциалов состоит в следующем. После построения опорного плана все переменные транспортной задачи разбиваются на
- 3. Функция стоимости перевозок выражается через свободные переменные следующим образом здесь номер итерации Для нахождения коэффициентов каждому
- 4. Каждому пункту ставится величина - потенциал пункта Для каждой заполненной клетки составляется уравнение где - стоимость
- 5. Одному из этих неизвестных можно дать произвольное значение, и тогда неизвестных определяются однозначно. Далее для каждой
- 6. Если среди величин есть отрицательные, то значение целевой функции (5.8) может быть уменьшено путем перехода к
- 7. Заполняя выбранную клетку необходимо перераспределить объемы поставок, записанных в ряде других занятых клеток и связанных с
- 8. Циклом в таблице транспортной задачи, называется ломаная линия, вершины которой расположены в занятых клетках таблицы, а
- 9. Будем отмечать знаком « + » те вершины цикла, в которых перевозки необходимо увеличить, а знаком
- 10. Перенести какое-то количество единиц груза по означенному циклу, это значит увеличить перевозки, стоящие в положительных вершинах
- 11. Пример 5.8. Составить план перевозок грузов с наименьшей стоимостью от трех поставщиков соответственно в количествах 100,
- 13. 1. Определение исходного плана перевозов. Для составления исходного плана перевозок используем метод северо- западного угла. Общее
- 15. 2. Исследование базисного решения на оптимальность. 2.1. Вычислим потенциалы и Исходя из базисных переменных. Для их
- 16. Полагая, например, , найдем 2.2. Для каждой свободной клетки вычислим относительные оценки:
- 19. 3. Определение нового базисного решения. Минимальной разностью является для клетки (1,4). Отрицательная оценка показывает, что при
- 20. Одна из вершин цикла находится в незанятой клетке (1,4), которую отмечаем знаком «+». Все остальные вершины
- 21. Значение записываем в незанятую клетку. Далее двигаясь по означенному циклу, вычитаем из объемов перевозок, расположенных в
- 23. 4. Исследование базисного решения на оптимальность. 4.1. Вычислим потенциалы и исходя из базисных переменных
- 24. Полагая, например, , найдем 4.2. Для каждой свободной клетки вычислим относительные оценки:
- 26. Условие оптимальности плана перевозок не выполняется, так как одна из оценок отрицательна, поэтому построим замкнутый цикл
- 27. 5. Определение нового базисного решения. Построим цикл пересчета для свободной клетки (2,4), для которой не выполняется
- 28. Замечание. Так как одновременно в двух вершинах цикла (2,2) и (3,4) поставки становятся равными нулю, то
- 30. 6. Исследование базисного решения на оптимальность. 6.1. Вычислим потенциалы и исходя из базисных переменных
- 31. Полагая, например, , найдем 6.1. Для каждой свободной клетки вычислим относительные оценки:
- 33. Так как для всех свободных клеток таблицы неравенство выполняется, то полученное решение будет оптимальным. При таком
- 34. 5.6.3. Задачи с нарушенным балансом а) Транспортная задача с избытком запасов. Транспортную задачу такого типа можно
- 35. Стоимость перевозок между фиктивным пунктом назначения и пунктами отправления принимаются равными нулю. Пример 5.9. Решить транспортную
- 38. б)Транспортная задача с недостатком запасов. Транспортную задачу такого типа можно свести к закрытой модели, если ввести
- 39. Стоимость перевозок между фиктивным пунктом отправления и пунктами назначения принимаются равными нулю. Пример 5.10. Решить транспортную
- 42. Скачать презентацию