Математическое программирование

     В общем виде задачу можно представить  следующим образом: в m пунктах производства А₁, А₂,    ,А_m имеется однородный груз в количестве соответственно а₁,а₂,   , а_m. Этот груз необходимо доставить в n пунктов назначения B₁, B₂, …, B_n  b₁, в количестве соответственно b₂, …, b_n. Стоимость перевозки единицы груза (тариф) из пункта A_i в пункт B_j равна c_ij.

     Требуется составить план перевозок, позволяющий  вывезти все грузы и имеющий минимальную стоимость.

     Математическая  модель задачи выглядит следующим образом:

     Пусть x_ij – количество груза, перевозимого из пункта Ai в пункт Bi.

     Целевая функция имеет вид:    (1)

при следующих  системах ограничений:

(2)           

(3)              

Определения:

1. Всякое  матричное решение систем (2) и  (3), определяемое матрицей Х(x_ij), называется планом транспортной задачи.

2. Решение,  при котором функция (1) принимает  минимальное значение, называется  оптимальным планом транспортной задачи.

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

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

Теорема.

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

Обычно  условия транспортной задачи записываются в виде таблицы:

c_ij - тарифы на перевозку груза от поставщика A_i к потребителю B_j

     В случае превышения запасов над потребностью ( > ) вводится фиктивный потребитель B_n+1 с нулевыми тарифами на перевозку от всех поставщиков (c_{i n+1}=0).

     Аналогично, если потребности превышают запасы, ( < ), то вводится фиктивный поставщик A_m+1 с нулевыми тарифами (c_{m+1 j}=0).

     Число переменных транспортной задачи с m-пунктами отправления и n-пунктами назначения равно m·n, а число уравнений равно m+n.

     При условии выполнения баланса запасов и потребностей число линейно независимых уравнений равно (m+n-1).

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

     Для решения транспортной задачи существует несколько способов.

     Рассмотрим  три из них:

1. метод северо-западного угла;
2. метод минимального элемента;
3. метод потенциалов.

 

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

 

Пусть имеется  таблица исходных данных задачи: 

 

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

     Заполним  таблицу, начиная с левого верхнего угла, двигаясь далее по строке вправо, или по столбцу вниз. В клетку (1; 1) занесем меньшее из чисел  a₁ и b₁ , т.е. .

     Если  a₁ > b₁, то x₁₁=b₁ и первый столбец «закрыт», т.е. потребности первого потребителя удовлетворены полностью. Далее движение продолжаем по первой строке. В соседнюю клетку (1; 2) записываем меньшее из чисел a₁-b₁ и b₂ , т.е. .

     Если  же b₂>a₁, то аналогично «закрывается» первая строка и далее переходим к заполнению соседней клетки (2; 1), куда заносим . Этот процесс продолжается до тех пор, пока на каком-то этапе не исчерпаются ресурсы a_m и потребности b_n .

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

     Пример. На три базы А₁, А₂, А₃ поступил однородный груз в количествах, соответственно равных 140, 180 и 160 ед. Этот груз требуется перевезти в пять пунктов назначения В₁, В₂, В₃, В₄, В₅ соответственно в количествах 60, 70, 120, 130 и 100 ед. Тарифы перевозок единицы груза с каждого из пунктов отправления в соответствующие пункты назначения указаны в следующей таблице: 
 
 
 
 
 

     Найти план перевозок.

     Решение. Здесь число пунктов отправления m=3, а число пунктов назначения n=5. Следовательно, опорный план задачи определяется числами, стоящими в 5+3-1=7 заполненных клетках.

     Заполнение  таблицы начнем с клетки для неизвестного х₁₁, т.е. попытаемся удовлетворить потребности первого пункта назначения за счет запасов первого пункта отправления. Т.к. запасы пункта А₁ больше, чем потребности пункта В₁, то полагаем х₁₁=60, записываем это значение в соответствующей клетке таблицы и временно исключаем из рассмотрения столбец В₁, считая при этом запасы пункта А₁ равными 80. 

 

     Рассмотрим  первые из оставшихся пунктов отправления А₁ и назначения В₂. Запасы пункта А₁ больше потребностей пункта В₂. Положим х₁₂=70, запишем это значение в соответствующей клетке таблицы и временно исключим из рассмотрения столбец В₂. В пункте А₁ запасы считаем равными 10 ед. Снова рассмотрим первые из оставшихся пунктов отправления А₁ и назначения В₃. Потребности пункта В₃ больше оставшихся запасов пункта А₁. Положим х₁₃=10 и исключим из рассмотрения строку А₁. Значение х₁₃=10 запишем в соответствующую клетку таблицы и считаем потребности пункта В₃ равными 110 ед.

     Далее переходим к заполнению клетки для  неизвестного х₂₃ и т.д. Через шесть шагов остается один пункт отправления А3 с запасом груза 100 ед. и один пункт назначения В5 с потребностью 100ед. Соответственно имеется одна свободная клетка, которую и заполняем, полагая х₃₅=100. в результате получаем опорный план

     

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

       

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

2. Метод минимального элемента.

 

     Сущность  метода минимального элемента состоит  в выборе клетки с минимальным  тарифом (если таких клеток несколько, то следует выбрать любую из них).

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

     Пример. Четыре предприятия данного экономического района для производства продукции используют три вида сырья. Потребности в сырье каждого из предприятий соответственно равны 120, 50, 190 и 110 ед. Сырье сосредоточено в трех местах его получения, а запасы соответственно равны 160, 140, 170 ед. На каждое из предприятий сырье может завозиться из любого пункта его получения. Тарифы перевозок являются известными величинами и задаются матрицей

     

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

     Решение. Исходные данные запишем в виде таблицы.