Составители:
Рубрика:
34
В условии (1.32) записано, что суммарный объем поставки продукции всем n
потребителям от конкретного поставщика i должен быть равен количеству продукции,
предназначенной к поставке от этого i-го поставщика, т.е. его мощности.
В системе уравнений (1.33) отражено условие полного удовлетворения спроса
потребителей: суммарный объем поставки продукции от всех m поставщиков
конкретному j-му потребителю должен быть равен емкости (спросу) этого потребителя.
В ограничительных условиях транспортной задачи (1.28), (1.29) содержится m+n
уравнений с m×n неизвестными, причем одно из уравнений является следствием
остальных в силу условия
∑ ∑
= =
=
m
i
n
j
ji
ba
1 1
.
Следовательно, в системе (1.28), (1.29) линейно независимых уравнений будет m+n-
1 (это называют рангом системы - r), и каждый опорный план (программа) должен
содержать не более чем m+n-1 положительных перевозок.
Если число положительных перевозок х
ij
равно m+n-1, то такой опорный план
(программа) оказывается невырожденным. В случае, когда часть базисных компонент
(перевозок) плана нули, то такой план является вырожденным.
Для каждого невырожденного опорного плана в матрице перевозок X=(x
ij
) должно
быть m+n-1 заполненных числами x
ij
клеток. Остальные клетки остаются пустыми.
Заполненные в матрице перевозок клетки называются базисными, не заполненные -
свободными.
Транспортные задачи могут решаться с помощью симплексного метода. Однако
лучше всего их решать специально разработанными методами, которые менее громоздки
и сравнительно просты. Наиболее распространенными методами решения транспортных
задач являются: распределительный метод, метод потенциалов, метод
дифференциальных рент и венгерский метод. Существуют и другие методы.
Основные методы решения транспортных и нетранспортных задач, приводимых к
типу транспортных, будут рассмотрены на числовых примерах ниже в соответствующих
главах книги.
1.5. Постановка задачи динамического программирования
Динамическое программирование представляет собой вычислительный метод
решения некоторых типов задач нелинейного программирования, а также некоторых задач
линейного программирования с требованием целочисленности аргументов. Основателем
динамического программирования является американский математик Р.Беллман.
Введенный им термин "динамическое программирование" возник в результате изучения
задач, в которых были существенные изменения во времени. Однако этот метод может
быть использован в задачах, где время вообще не фигурирует.
При применении метода динамического программирования весь оптимизируемый
процесс естественно или искусственно подразделяется на ряд этапов или шагов.
Не существует единой схемы подхода к решению различных типов задач
оптимизации методом динамического программирования. В каждом типе задачи
осуществляется специфика подхода для ее решения. Однако общим для этого метода
является следующее. Оптимизация целевой функции производится постепенно, шаг за
шагом. На каждом шаге определяется оптимальное управление, т.е. совокупность
переменных, при которых целевая функция на этом этапе имеет наибольшее (наименьшее)
значение. В одних задачах, в которых оптимизируемый процесс естественно подразделен
на ряд этапов, решением задачи является совокупность оптимальных управлений на всех
этапах. В других задачах, в которых обычно оптимизируемый процесс подразделяется на
Страницы
- « первая
- ‹ предыдущая
- …
- 32
- 33
- 34
- 35
- 36
- …
- следующая ›
- последняя »
