Системное програмирование

После небольшой тренировки для задач  небольшого объема эту процедуру  можно провопить устно. После  того как последней переменной присвоено  значение, суммы по всем строкам  и столбцам будут равны 0. Таким  образом получается решение

(значения переменных  находятся в левых верхних  углах клеток) с семью приводимыми ниже базисными переменными. Остальные переменные равны 0. Для общего массива из т строк и п столбцов получаем т+ п— 1 переменных в силу (1)

Полная  стоимость, соответствующая этому  решению, F = 3*1 + 12*0 + 2*5 + 8*3 +15*З +15*4 + 5*1=147 дол.

Попробуем теперь улучшить это решение, уменьшив стоимость С. Отметим, что полученные результаты для этого частного случая и метод их получения применимы и в случае общей транспортной задачи (см. соотношения (2)).

  Поскольку переменные (i=1,m; j=1,n) удовлетворяют системам линейных уравнений (3) и (4) и условию неотрицательности, обеспечиваются доставка необходимого количества груза в каждый из пунктов назначения, вывоз имеющегося груза из всех пунктов отправления, а также исключаются обратные перевозки.

Определение 1. Всякое неотрицательное решение систем линейных уравнений (3) и (4), определяемое матрицей X=( )( i=1,m; j=1,n), называется планом транспортной задачи. 

Определение 2. План , (i= 1,m; j=1,n) при котором функция (5) принимает свое минимальное значение, называется оптимальным планом транспортной задачи.

Обычно исходные данные транспортной задачи записывается в виде таблицы 1.

 
 

Очевидно, общее наличие груза у поставщиков  равно  , а общая потребность в грузе в пунктах назначения равно ед. Если общая потребность в грузе в пунктах назначения равна запасу груза в пунктах отправления, т.е.

=   (6)

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

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

В случае превышения запаса над потребностью, т.е. > , вводится фиктивный  (n+1)-й пункт назначения с потребностью b_n+1 = - и соответствующие тарифы равными считаются нулю: C_in+1= 0 (i= 1,m) Полученная задачами являются транспортной задачами, для которой выполняется равенство (6).

Аналогично, при < , вводится фиктивный (m+1)-й пункт отправления с запасом груза

a_m+1 = - и тарифы полагаются равными C_m+1j= 0 ( j=1,n).

  Эти задачи сводится к обычной транспортной задаче, из опорного плана которой  получении оптимального исходной задачами. В дальнейшем будем рассматривать  закрытую модель транспортной задачи. Если же модель транспортной задачами являются открытой, то исходя из сказанного выше, перепишем таблицу условий  задачами так, чтобы выполнялось  равенство (6).

  Число переменных x_ij в транспортной задаче с m пунктами отправления и n пунктами назначения равно m*n, а число уравнений в системах (3) и (4) равно n+m. Так как мы предполагаем, что выполняется условие (6),то число линейно независимых уравнений равно n+m-1. Следовательно, опорный план транспортной задачи может иметь не более n+m-1 отличных от нуля неизвестных.

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

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

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

  Для определения опорного плана транспортной задачи можно использовать изложенные выше методы. Однако ввиду исключительной практической важности этой задачи и  специфики ее ограничений (каждое неизвестное  уходит лишь в два уравнения систем (3) и (4) и коэффициенты при неизвестных  равны единице) для определения  оптимального плана транспортной задачи разработаны специальные методы: метод потенциалов и метод  дифференциальных рент.

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

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

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

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

  После того как проделаны т + п - 2 описанных выше шагов, получают задачу с одним пунктом отправления и одним пунктом назначения. При этом останется свободной только одна клетка, а запасы оставшегося пункта отправления будут равны потребностям оставшегося пункта назначения. Заполнив эту клетку, тем самым делают (п + т—1)-й шаг и получают искомый опорный план. Следует заметить, что на некотором шаге (но не на последнем) может оказаться, что потребности очередного пункта назначения равны запасам очередного пункта отправления. В этом случае также временно исключают из рассмотрения либо столбец, либо строку (что-нибудь одно). Таким образом, либо запасы соответствующего пункта отправления, либо потребности данного пункта назначения считают равными нулю. Этот нуль записывают в очередную заполняемую клетку. Указанные выше условия гарантируют получение п + т—1 занятых клеток, в которых стоят компоненты опорного плана, что является исходным условием для проверки последнего на оптимальность и нахождения оптимального плана.

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

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

Пример 2. Имеется 4 склада: в первом складе 15 ед. груза, во втором – 20 ед. груза, в третьем – 10 ед. груза, а в четвертом – 25 ед. груза и 5 магазинов, потребности которых: 1 магазин  – 5 ед. груза, у 2 -го – 18 ед. груза, у 3-го – 17 ед. груза, у 4-го – 22 ед. груза и у пятого магазина – 8 ед. груза.

Считая что  – количество ед. груза из -того склада, в -ый магазин, – количество ед. груза, в -том складе, – потребности -того магазина. Для того чтобы выполнить перевозку, необходимо выполнение 2 условий:

1) ;

2) ;

               

Исходя из этих условий составим математическую модель транспортной задачи:

; ;

или в виде таблицы:

Тарифы перевозок, заданные виде матрицы:

.

Найти план перевозок  транспортной задачи с минимальными затратами на дорогу, то есть:

.

Таким образом:

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

, I – множество номеров пунктов производства;

, J – множество номеров пунктов потребления;

Последовательно по итерациям метода получаем:

I. ; ; ; – 1 столбец исключен.

II. ; ; ; – 1 строка исключена.

III. ; ; ; – 2 столбец исключен.

IV. ; ; ; – 2 строка исключена.

V. ; ; ; – 3 столбец исключен.

VI. ; ; ; – 3 строка исключена.

VII. ; ; ; – 4 столбец исключен.

VIII. ; ; ; – 4 строка и 5 столбец исключены.