Организация складского хозяйства на промышленном предприятии

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

      = ,      (5) 

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

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

     Определение 2. План Х* = {X_ij*}, при котором функция цели 1 принимает минимальное значение, называется оптимальным планом транспортной задачи.

     Ограничения 2 и 3 транспортной задачи представляют собой две группы уравнений. Первая из них, т.е. система уравнений 2, означает то, что сумма перевозок по каждой строке таблицы должна быть равна соответствующему запасу а_i. Каждое уравнение второй системы 3 означает то, что сумма перевозок по каждому столбцу таблицы должна быть равна соответствующей потребности b_j. Транспортная задача представляет собой задачу линейного программирования, записанную в каноническом виде. Следовательно, ее можно решать симплексным методом. Однако для решения транспортных задач существуют специальные методы. [19]

     Особенности транспортной задачи:

     1. Закрытая транспортная задача  всегда совместна, обладает планом, т.е. имеет решение.

     2. Если значения и а_i-е и b_j-е – целые и неотрицательные, то транспортная задача имеет целочисленное решение.

     3. Клетки таблицы транспортной  задачи с координатами, в которых  проставлены значения перевозок,  называются базисными и соответствуют  базисным переменным, а остальные клетки остаются свободными. Для невыраженного опорного плана в таблице транспортной задачи будет заполнена положительными числами m + n – 1 клетка. Если же опорный план задачи вырожден, то часть базисных клеток будет заполнена нулями.

     Нахождение  первоначального плана

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

     Метод северо-западного  угла. Пусть условие транспортной задачи задано в следующей таблице: 

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

     Матрицу перевозок начинаем заполнять с  левого верхнего (северо-западного) угла, с клетки (1,1). Для этого сравниваем два значения а₁ = 30 и b₁= 20, т.е. попытаемся удовлетворить потребность первого пункта назначения за счет запасов первого пункта отправления. Запасы пункта А₁ больше потребности пункта В₁, следовательно, в качестве значения Х₁₁ выбираем меньшее число – b₁ и запишем это число в соответствующей клетке таблицы. Таким образом, потребность пункта В₁ в грузе удовлетворена, и поэтому все остальные числа этого столбца (Х₂₁, Х₃₁, Х₄₁) считаем равными нулю, а соответствующие им клетки оставляем свободными.

     Получаем  новую матрицу из трех столбцов (В₂, В₃, В₄) и четырех строк (А₁, А₂, А₃, А₄) и новое значение запаса у первого пункта отправления ( = 30 – 20 = 10). Далее сравниваем значения = 10 и b₂ = 90 и повторяем алгоритм. Меньшее из этих значений, равное 10, выбираем в качестве Х₁₂ и записываем в клетку (1,2) таблицы. Тогда запас пункта А₁ будет полностью исчерпан, следовательно, остальные значения перевозок из первой строки (Х₁₃, Х₁₄) принимаем равными нулю, а соответствующие клетки остаются свободными. Продолжая заполнять таблицу, таким образом дойдем до клетки (4,4). Построенный план является опорным. В рассматриваемой задаче число пунктов отправления m = 4 и число пунктов назначения n = 4, следовательно, невырожденный план задачи определяется числами, стоящими в m+n-1 = 4 + 4 – 1 = 7 заполненных клетках. 

     Запишем первоначальный опорный план в виде матрицы Х: 

     Х = . 

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

     f(х) = 5 × 20 + 4 × 10 + 1 × 70 + 3 × 10 + 1 × 40 + 2 × 30 + 1 × 70 = 410.

     Вырожденный план. При построении опорного плана нужно следить, чтобы сумма перевозок по каждой строке была равна соответствующим запасам, а сумма перевозок по каждому столбцу – потребности. Количество заполненных клеток равно m + n – 1. Если план вырожденный, т.е. если на очередном шаге запас а_i равен потребности b_j, в этом случае необходимо считать одну из клеток (либо справа, либо под последней заполненной клеткой) базисной со значением, равным нулю. Этот нуль вписывают, и соответствующая клетка считается занятой.

     Пусть условия задачи заданы следующей  таблицей: 

     На  первом шаге заполняем северо-западный угол, полагая Х₁₁ = 20, клетки (2,1), (3,1) и (4,1) остаются свободными. На втором шаге полагаем Х₁₂ = 10. Этим мы используем полностью запас пункта А₁. Остальные клетки первой строки (1,3) и (1,4) остаются свободными. На третьем шаге рассматриваем перевозку Х₂₂. Поскольку в этом случае запас пункта А₂, равный 70, совпадает с оставшейся неудовлетворенной потребностью пункта В₂, равной 70, то выбираем Х₂₂ = 70. Этим самым заполняется одновременно и вся вторая строка и весь второй столбец. В этом случае нужно считать одну из переменный Х₂₃ или Х₃₂ базисной со значением, равным нулю. Пусть Х₃₂ = 0. Проставив в соответствующей клетке базисный нуль, мы получаем при продолжении процесса заполнения таблицы m + n – 1 заполненную клетку. Если не проставить нулевую базисную переменную, окажется, что число занятых положительными перевозками клеток меньше, чем m + n – 1.

     Метод минимального элемента. Выбор пунктов отправления и назначения можно производить иначе, ориентируясь на стоимость перевозок, т.е. на каждом шаге следует выбирать какую-нибудь клетку, отвечающую минимальной стоимости перевозки. Если таких клеток несколько, то можно выбрать любую. [19]

     Этот  метод позволяет найти первоначальный опорный план с меньшей стоимостью перевозок, чем план, полученный методом северо-западного угла: