Часть 3

СПЕЦИАЛЬНЫЕ ЗАДАЧИ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ

Транспортная задача

Постановка задачи. Основные понятия

Общая постановка транспортной задачи состоит в определении оптимального плана перевозок некоторого однородного груза из m пунктов отправления в n пунктов назначения. При этом в качестве критерия оптимальности обычно берется либо минимальная стоимость перевозок всего груза, либо минимальное время его доставки

(3.1)

(3.2)

(3.3)

(3.4)

Определение 3.1. Всякое неотрицательное решение системы линейных уравнений (3.2) и (3.3), определяемое матрицей называется планом транспортной задачи.

Определение3.2. План,при котором функция (3.1) принимает свое минимальное значение, называется оптимальным планом транспортной задачи.

Если общая потребность в грузе в пунктах назначения равна запасу груза в пунктах отправления, т. е. (3.5) то модель такой транспортной задачи называется закрытой.

Теорема 3.1. Для разрешимости транспортной задачи необходимо и достаточно, чтобы запасы груза в пунктах отправления были равны потребностям в грузе в пунктах назначения, то есть, чтобы выполнялось равенство (3.5).

Если в опорном плане число отличных от нуля компонент равно в точности, то план является невырожденным, а если меньше - то вырожденным.

Четыре предприятия A, B, C и D для производства продукции используют сырье, хранящееся на трех складах (I, II и III), емкости которых равны 160, 140 и 170 единиц. Потребности предприятий в сырье соответственно равны 120, 50, 190 и 110 единиц. На каждое из предприятий сырье можно довозить из любого склада. Тарифы перевозок задаются матрицей

Составить план перевозок, при котором общая стоимость перевозок является минимальной.

Определение опорного плана транспортной задачи. Метод северо-западного угла

Этот план можно находить методом северо-западного угла, методом минимального элемента или методом аппроксимации Фогеля.

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

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

Определение оптимального плана транспортной задачи. Метод потенциалов

Теорема 3.2. Если для некоторого опорного плана транспортной задачи существуют такие числа,,что при при

для всех i и j, то - оптимальный план транспортной задачи.

Определение 3.3. Числа и называются потенциалами соответственно пунктов отправления (складов) и пунктов назначения (предприятий).

Определение 3.4. Циклом в таблице условий транспортной задачи называется ломаная линия, вершины которой расположены в занятых клетках, а звенья вдоль строк и столбцов, причем в каждой вершине цикла встречается ровно два звена, одно из которых находится в строке, а другое – в столбце.