Задачи календарного планирования производства: модель без дефицита, модель с дефицитом
Дипломная работа - Менеджмент
Другие дипломы по предмету Менеджмент
е груза у поставщиков равно , а общая потребность в грузе в пунктах назначения равна . Если общая потребность в грузе в пунктах назначения равна запасу груза в пунктах отправления, т. е.
= (1.2)
то модель такой транспортной задачи называется закрытой. Если же указанное условие не выполняется, то модель транспортной задачи называется открытой.
Теорема 1.1. Для разрешимости транспортной задачи необходимо и достаточно, чтобы запасы груза в пунктах отправления были равны потребностям в грузе в пунктах назначения, т. е. чтобы выполнялось равенство.
В случае превышения запаса над потребностью, т. е. при >, вводят фиктивный (n+1)-й пункт назначения с потребностью bn+1=- и соответствующие тарифы считают равными нулю: cin+1=0 (i=1,m). Полученная задача является транспортной задачей, для которой выполняется равенство закрытости.
Аналогично, при <, вводят фиктивный (m+1)-й пункт отправления с запасом груза am+1=- и соответствующие тарифы считают равными нулю: cm+1j=0 (j=1,n). Этим задача сводится к транспортной задаче с закрытой моделью, из оптимального плана которой получается оптимальный план исходной задачи. Поэтому в дальнейшем мы будем рассматривать только закрытую модель транспортной задачи.
Число переменных xij в транспортной задаче с m пунктами отправления и n пунктами назначения равно nm, а число уравнений в системе ограничений равно n+m. Так как предполагается, что выполняется условие закрытости, то число линейно-независимых уравнений равно n+m-1. Следовательно, опорный план транспортной задачи может иметь не более n+m-1 отличных от нуля неизвестных.
Если в опорном плане число отличных от нуля компонент равно в точности n+m-1, то план является невырожденным, а если меньше - то вырожденным. Для определения опорного плана существует несколько методов. Ниже рассматриваются два из них - метод северо-западного угла, метод минимального элемента.
Как и для всякой задачи линейного программирования, оптимальный план транспортной задачи является и опорным планом.
Определение оптимального плана транспортной задачи начинают с нахождения какого-нибудь ее опорного плана.
2.2 Методы составления первоначальных опорных планов
Метод северо-западного угла используют для нахождения произвольного опорного плана транспортной задачи.
Схема метода: 1) Полагают верхний левый элемент матрицы X
x11 = min(a1,b1).
Возможны три случая:
а) если a1 < b1, то х11 = a1 и всю первую строку, начиная со второго элемента, заполняют нулями.
б)если a1 > b1ь то х11 = b1 а все оставшиеся элементы первого столбца заполняют нулями.
в)если a1 = b1 то х11 = a1= b1 и все оставшиеся элементы первых столбца и строки заполняют нулями.
На этом один шаг метода заканчивается.
) Пусть проделано к шагов, (к) - й шаг состоит в следующем.
Определяют верхний левый элемент незаполненной части матрицы X. Пусть это элемент x? (? + = к + ?).
Тогда полагают xXil = min(а?,b), где
a?(k)=a?- и b(k)=b- (1.3)
Если a? < b, то заполняют нулями ?-ю строку начиная с ( +1) -го элемента. В противном случае заполняют нулями оставшуюся часть - го столбца. Метод минимального элемента позволяет построить начальный опорный план транспортной задачи и является вариантом метода северо-западного угла, учитывающим специфику матрицы С = (Cij)m,n. В отличие от метода северо-западного угла данный метод позволяет сразу получить достаточно экономичный план и сокращает общее количество итераций по его оптимизации.
Схема метода: элементы матрицы С нумеруют, начиная от минимального в порядке возрастания, а затем в этом же порядке заполняют матрицу Х.
Пусть элементом с минимальным порядковым номером оказался элемент xij.
Тогда полагают xij= min(ai, bj)
Возможны три случая:
а) если min(ai, bj) = а;, то оставшуюся часть i-й строки заполняют нулями;
б) если min(ai, bj) = bj, то оставшуюся часть j-ro столбца заполняют нулями.
в) если ai = bj, то оставшуюся часть строки и столбца заполняют нулями.
Далее этот процесс повторяют с незаполненной частью матрицы. Пусть элементом с k-м порядковым номером оказался x?.
Тогда x? =min(a?, b),где
a?(k)=a?-(g) g=1тАжk-1
b(k)=b-(u) u=1тАжk-1 (1.4)
Возможны три случая:
а) a?(k)< b(k)', тогда x?(k) = a?(k) и оставшуюся часть строки ? заполняют нулями;
б) a?(k)> b(k), тогда x?(k) = b(k) и остаток столбца заполняют нулями;
в) a?(k) = b(k), тогда оставшуюся часть строки ? и столбца заполняют нулями.[4]
2.3 Метод потенциалов
Общий принцип определения оптимального плана транспортной задачи методом потенциалов: сначала находят опорный план транспортной задачи, а затем его последовательно улучшают до получения оптимального плана.
Для определения опорного плана транспортной задачи будем пользоваться одним из методов, рассмотренных выше. Эти методы гарантируют получение m+n-1 занятых клеток в исходной таблице условий, причем в некоторых из них могут стоять нули. Полученный таким образом план следует проверить на оптимальность.
Теорема 1.2. Если для некоторого опорного плана X*=(xij*) (i=1,m; j=1,n) транспортной задачи существуют такие числа U1, U2, . . . , Um, V1, V2, . . . , Vn, что
Vj- Ui=cij при xij>0
Vj- Ui<=cij при xij=0
для всех (i=1,m) и (j=1,n), то X*=(xij*) - оптимальный план транспортной задачи.
Определение 1. 3. Числа Ui и Vj (i=1,m; j=1,n) называются потенциалами соответственно пунктов