Реферат: Минимизация стоимостей перевозок

КП. 2203 81 – 21

3.ВЫБОР МЕТОДА РЕАЛИЗАЦИИ ПРОДУКЦИИ.

ОБОСНОВАНИЕ ВЫБОРА МЕТОДА .

Симплекс - метод является универсальным и применяется для решения любых задач.

Однако существуют некоторые частные типы задач линейного программирования ,

которые в силу некоторых особенностей своей структуры допускают решение более

простыми методами. К ним относится транспортная задача.

Распределительный метод решения транспортной задачи обладает одним

недостатком :

нужно отыскивать циклы для всех свободных клеток и находить их цены. От этой

трудоемкой работы нас избавляет специальный метод решения транспортной

задачи , который называется методом потенциалов. Он позволяет автоматически

выделять циклы с отрицательной ценой и определять их цены.

В отличии от общего случая ОЗЛП с произвольными ограничениями и

минимизированной функцией , решение транспортной задачи всегда существует.

Общий принцип определения оптимального плана транспортной задачи методом потенциалов аналогичен принципу решения задачи линейного программирования симплекс - метода ,. а именно : сначала находят опорный план транспортной задачи , а затем его улучшают до получения оптимального плана. Далее будет рассматриваться сам метод потенциалов.

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

Определение значений x­­­­_i,j начинается с левой верхней клетки таблицы. Находим значения x_1,1 из соотношения x₁₁ = min{a₁ ,b₁ }.

Если a_i < b₁ то x₁₁ =a₁ , строка i=1 исключается из дальнейшего рассмотрения , а потребность первого потребителя b₁ уменьшается на величину a₁ .

Если a₁ >b₁ , то x₁₁ =b₁ , столбец j=1 исключается из дальнейшего рассмотрения , а наличие груза у первого поставщика a₁ уменьшается на величину b₁ .

Если a₁ =b₁ , то x₁₁ =a₁ =b₁ , строка i=1 и столбец j=1 исключаются из дальнейшего рассмотрения.

Данный вариант приводит к вырождению исходного плана.

Затем аналогичные операции проделывают с оставшийся частью таблицы , начиная с его северо - западного угла. После завершения оптимального процесса необходимо провести проверку полученного плана на вырожденность.

Если количество заполненных клеток равно m + n -1 , то план является невырожденным. Если план вырожденный , т.е количество заполненных клеток стало меньше m + n -1 , то незаполненные клетки с минимальными стоимостями перевозок заполняются нулями , чтобы общие количество заполненных клеток стало равным

m + n -1.

Транспортная задача с неправильным балансом называется открытой моделью .

Чтобы ее решить , необходимое сбалансировать. Достигается это следующим образом: