План реферата
Введение
1. Формулировка транспортнойзадачи
2. Математическая модель транспортной задачи
3. Необходимое и достаточное условия разрешимоститранспортной задачи
4. Свойство системы ограниченийтранспортной задачи
5. Опорное решение транспортной задачи
6. Методы построения начального опорного решения
6.1 Построение первоначального плана по способусеверо-западного угла
6.2 Построение первоначального плана по способуминимального элемента
7. Переход от одного опорногорешения к другому
8. Распределительный метод
9. Метод потенциалов
10. Особенности решения транспортных задач с неправильнымбалансом
11. Алгоритм решения транспортной задачи методомпотенциалов
11.1 Предварительный шаг
11.2 Общий повторяющийся шаг
12. Транспортная задача с ограничениямина пропускную способность
13. Транспортная задача по критерию времени
14. Применение транспортной задачи для решенияэкономических задач
Заключение
Список использованной литературы
Введение
Методы линейного программированияприменяются для решения многих экстремальных задач, с которыми довольно часто приходитсяиметь дело в экономике. Решение таких задач сводится к нахождению крайних значений(максимума и минимума) некоторых функций переменных величин.
Линейное программирование основанона решении системы линейных уравнений (с преобразованием в уравнения и неравенства),когда зависимость между изучаемыми явлениями строго функциональна. Для него характерныматематическое выражение переменных величин, определенный порядок, последовательностьрасчетов (алгоритм), логический анализ. Применять его можно только в тех случаях,когда изучаемые переменные величины и факторы имеют математическую определенностьи количественную ограниченность, когда в результате известной последовательностирасчетов происходит взаимозаменяемость факторов, когда логика в расчетах, математическаялогика совмещаются с логически обоснованным пониманием сущности изучаемого явления.
С помощью этого метода в промышленномпроизводстве, например, исчисляется оптимальная общая производительность машин,агрегатов, поточных линий (при заданном ассортименте продукции и иных заданных величинах),решается задача рационального раскроя материалов (с оптимальным выходом заготовок).В сельском хозяйстве он используется для определения минимальной стоимости кормовыхрационов при заданном количестве кормов (по видам и содержащимся в них питательнымвеществам). Задача о смесях может найти применение и в литейном производстве (составметаллургической шихты). Этим же методом решаются транспортная задача, задача рациональногоприкрепления предприятий-потребителей к предприятиям-производителям.
Все экономические задачи, решаемыес применением линейного программирования, отличаются альтернативностью решения иопределенными ограничивающими условиями. Решить такую задачу — значит выбрать извсех допустимо возможных (альтернативных) вариантов лучший, оптимальный. Важностьи ценность использования в экономике метода линейного программирования состоят втом, что оптимальный вариант выбирается из весьма значительного количества альтернативныхвариантов. При помощи других способов решать такие задачи практически невозможно.
Весьма типичной задачей, решаемойс помощью линейного программирования, является транспортная задача. [1]
Транспортная задача (transportationproblem) — одна из наиболее распространенных задач математического программирования(обычно — линейного). В общем виде ее можно представить так: требуется найти такойплан доставки грузов от поставщиков к потребителям, чтобы стоимость перевозки (илисуммарная дальность, или объем транспортной работы в тонно-километрах) была наименьшей.Следовательно, дело сводится к наиболее рациональному прикреплению производителейк потребителям и наоборот. [2]
1. Формулировка транспортной задачи
В простейшем виде, когда распределяетсяодин вид продукта и потребителям все равно, от кого из поставщиков его получать,задача формулируется следующим образом.
Исходная информация:
Mi — количествоединиц груза в i-м пункте отправления (i = 1, 2, …, k);
Nj — потребностьв j-м пункте назначения (j = 1, 2, …, l) (в единицах груза);
aij — стоимостьперевозки единицы груза из i-гo пункта в j-й.
Обозначим через xijпланируемое количество единиц груза для перевозки из i-ro пункта в j-й.
В принятых обозначениях:
/> - общая(суммарная) стоимость перевозок;
/> - количествогруза, вывозимого из i-ro пункта;
/> - количествогруза, доставляемого в j-и пункт.
В простейшем случае должны выполнятьсяследующие очевидные условия:
/>
/>
/>
Таким образом, математической формулировкойтранспортной задачи будет:
найти
/>
при условиях
/>;
/>;
/>
Эта задача носит название замкнутой(закрытой, сбалансированной) транспортной модели.
Заметим, что условие /> является естественным условиемразрешимости замкнутой транспортной задачи.
Более общей транспортной задачейявляется так называемая открытая (несбалансированная) транспортная модель:
найти
/>
при условиях
/>
/>
/>
Ясно, что в этой задаче не предполагается,что весь груз, накопленный в i-м пункте, должен быть вывезен. [3]
2. Математическая модель транспортной задачи
Простейшими транспортными задачамиявляются задачи о перевозках некоторого однородного груза из пунктов отправления(от поставщиков) в пункты назначения (к потребителям) при обеспечении минимальныхзатрат на перевозки.
Обычно начальные условия таких задачзаписывают в таблицу. Например, для k поставщиков и l потребителейтакая задача имеет следующий вид:
/>
Здесь показатели aijозначают затраты на перевозку единицы груза от i-го поставщика (i=1,2,…,k)к j-тому потребителю (j=1,2,…,l), Mi — мощностьi-того поставщика в планируемый период, Nj — спрос j-тогопотребителя на этот же период. Обозначим через xij поставку (количествогруза), которая планируется к перевозке от i-того поставщика к j-томупотребителю. Математически задача сводится к нахождению минимума целевой функции,выражающей суммарные затраты на перевозку груза, т.е. функции
/>
при ограничениях
/>(1)
Если к этим ограничениям добавитьеще одно:
/>,(2)
т.е. суммарная мощность поставщиковравна суммарному спросу потребителей, то соответствующая модель задачи называетсязакрытой.
Задачам, в которых ограничение (2)отсутствует, т.е.
/>,
первоначально соответствует открытаямодель.
Отметим некоторые особенности экономико-математическоймодели транспортной задачи.
Система ограничений (1) сразу имеетвид уравнений, поэтому отпадает необходимость вводить добавочные переменные.
Матрица коэффициентов при переменныхв системе (1) состоит только из единиц и нулей.
Система ограничений (1) включаетk уравнений, связывающих поставки i-того поставщика с мощностью Mi(i=1,2,…,k) этого поставщика, и l уравнений, связывающих поставкиj-тому потребителю со спросом Nj (j=1,2,…,l)этого потребителя. Заметим, что число k равно числу строк исходной таблицы,а число l — числу столбцов.
Число переменных xij,входящих в целевую функцию и в систему уравнений (1), равно произведению kl,т.е. числу клеток таблицы.
Таким образом, система ограничений(1) есть система из k+l уравнений с kl переменными.
Любое решение транспортной задачи(x11, x12,…, xkl) называетсяраспределением поставок. Так как поставки не могут быть отрицательными, то речьидет только о допустимых решениях.
Оптимальному решению транспортнойзадачи соответствует оптимальное распределение поставок, при котором целевая функция/> достигает своего минимума.
В ходе решения задачи и нужно получитьэто оптимальное распределение поставок, которому соответствует какое-то допустимоебазисное решение системы ограничений (1). [4]
3. Необходимое и достаточное условия разрешимости транспортнойзадачи
Ограничение (1) и условия неотрицательностипеременных, исключающие обратные перевозки xij>0; i= 1, 2,…, k; j= 1, 2,., l.
Эти условия образуют систему ограничений.Любой план, компоненты которого удовлетворяют этой системе, будет допустимым.
Как видим, система ограничений заданав основном (k + l) уравнениями. Установим условия, при которых этасистема будет совместной, т.е. будет иметь решения.
Сложим элементы xijматрицы перевозок по строкам, каждая строка в сумме дает Mi, ив итоге получим />. Сложим те же элементы по столбцам,каждый столбец дает Nj, и в сумме получим />. Но от перестановки слагаемыхсумма не меняется, поэтому для любого допустимого плана обязательно будет выполнятьсяусловие
/>.
Равенство /> является необходимым условиемсовместности ограничений задачи.
Докажем и достаточность этого условия:если запасы равны потребностям, то всегда имеется допустимый план.
Действительно, пусть />. Рассмотрим такие числа:
/>
Убедимся, что эти числа образуютдопустимый план. Для этого достаточно проверить, что они удовлетворяют всем ограничениямзадачи.
Просуммируем эти числа по индексуi:
/>.
Но величины Nj,/> от индекса i не зависяти их можно вынести за знак суммы. В результате
/>
или
/>, />
Следовательно, взятые числа удовлетворяютгруппе уравнений (1).
Просуммируем эти числа по индексуj:
/>
Вынося постоянные Miи /> за знак суммы и имея в виду,что />, получаем
/>
или в развернутом виде
/>
Как видим, наши числа удовлетворяютгруппе уравнений (1). Эти числа неотрицательны, т.е. система ограничений полностьюудовлетворяется. Таким образом, допустимый план существует, что и требовалось доказать.
Равенство запасов потребностям естьнеобходимое и достаточное условие совместности и, следовательно, разрешимости транспортнойзадачи. [5]
4. Свойство системы ограничений транспортной задачи
Согласно теореме о структуре координатопорного плана задачи линейного программирования, в невырожденном опорном планедолжно содержаться r отличных от нуля координат, где r — ранг системы ограничений
/>.
В этой системе ограничений уравненийзакрытой транспортной задачи имеется k+l-1 линейно-независимых уравнений,т.е. ранг системы ограничений равен k+l-1. [6]
5. Опорное решение транспортной задачи
Опорное решение (опорный план, базисноерешение, basic solution) — одно из допустимых решений, находящихся в вершинах областидопустимых решений. Оно является решением системы линейных ограничений, котороенельзя представить в виде линейной комбинации никаких других решений.
При решении задачи линейного программированияможно поступить следующим образом: найти любое из таких «вершинных» решений,не обязательно оптимальное, и принять его за исходный пункт расчетов. Такое решениеи будет базисным. Если окажется, что оно и оптимальное, расчет на этом закончен,если нет — последовательно проверяют, не будут ли оптимальными соседние вершинныеточки. Ту из них, в которой план эффективнее, принимают снова за исходную точкуи так, последовательно проверяя на оптимальность аналогичные вершины, приходят кискомому оптимуму. На этом принципе строятся так называемый симплексный метод решениязадач линейного программирования, а также ряд других способов, объединенных общимназванием «методы последовательного улучшения допустимого решения (МПУ)»:метод обратной матрицы, или модифицированный симплекс-метод, метод потенциалов длятранспортной задачи и другие. Они отличаются друг от друга вычислительными особенностямиперехода от одного базисного решения к другому, улучшенному. [2]
6. Методы построения начального опорного решения6.1 Построение первоначального плана по способу северо-западногоугла
В этом случае не обращают вниманияна показатели затрат. Начав заполнение с клетки (1.1) — «северо-западного угла»таблицы, ступенями спускаются вниз до клетки (k, l), вычеркивая либоодну строку, либо один столбец. На последнем шаге вычеркиваются последняя (k-я)строка и последний (l-й) столбец. При практическом заполнении таблицы, вычеркиваниестрок и столбцов производится лишь мысленно.
Когда осуществляется первоначальноераспределение поставок, то не ставится цель получить оптимальное распределение.Достижению этой цели служат последующие этапы решения задачи. Они заключаются впереходах к новым распределениям поставок, пока не будет найдено оптимальное распределениепоставок. [4]6.2 Построение первоначального плана по способу минимальногоэлемента
При построении первоначального планапо способу северо-западного угла совершенно не учитываются тарифы, потому план получаетсявесьма далеким от оптимального. Для решения задачи приходится делать много приближений(шагов).
Способ минимального элемента учитываеттарифы и потому позволяет найти план, более близкий к оптимальному.
Этот способ заключается в следующем.
1. Располагаем все клетки таблицыв очередь по мере возрастания тарифов, начиная с минимального.
линейное программирование транспортная задача
2. В клетку с минимальным тарифомзаписываем наибольшую возможную перевозку (исходя из запасов и потребностей), затемзаполняем очередную по порядку клетку и т.д., пока не получим план. При этом долженстрого соблюдаться баланс по строкам и столбцам. Пустые клетки прочеркиваем, а незаполняем нулями (чтобы было видно, что они не входят в план).
Полученный план будет ациклическими будет состоять не более чем из k+l-1 компонент. Этот план и принимаемза исходный. Он будет лучше плана, построенного по способу северо-западного угла,и для нахождения оптимума потребуется меньше вычислений. [5]
7. Переход от одного опорного решения к другому
Числа /> и/> называют потенциалами. В распределительнуютаблицу добавляют строку /> и столбец />. Потенциалы /> и /> находятиз равенства />, справедливого для занятыхклеток. Одному из потенциалов дается произвольное значение, а остальные потенциалыопределяются однозначно. Если известен потенциал />, то />, если известен потенциал />, то />.
Обозначим />, которую называют оценкой свободныхклеток. Если все оценки свободных клеток />, то опорноерешение является оптимальным. Если хотя бы одна из оценок />, то опорное решение не являетсяоптимальным и его можно улучшить, перейдя от одного опорного решения к другому.
Наличие положительной оценки свободнойклетки (/>) при проверке опорного решенияна оптимальность свидетельствует о том, что полученное решение не оптимально и дляуменьшения значения целевой функции надо перейти к другому опорному решению. Приэтом надо перераспределить грузы, перемещая их из занятых клеток в свободные. Свободнаяклетка становится занятой, а одна из ранее занятых клеток — свободной.
Для свободной клетки с /> строится цикл (цепь, многоугольник),все вершины которого, кроме одной, находятся в занятых клетках; углы прямые, числовершин четное. Около свободной клетки цикла ставится знак (+), затем поочереднопроставляют знаки (-) и (+). У вершин со знаком (-) выбирают минимальный груз, егоприбавляют к грузам, стоящим у вершин со знаком (+), и отнимают от грузов у вершинсо знаком (-). В результате перераспределения груза получим новое опорное решение.Это решение проверяем на оптимальность и т.д. до тех пор, пока не получим оптимальноерешение. [7]
8. Распределительный метод
Распределительный метод решения транспортнойзадачи отличается от метода потенциалов некоторым изменением вычислительного процессаи иным (по форме) критерием оптимальности.
Алгоритм распределительного методазаключается в следующем.
1. Отыскиваем первоначальный ациклическийплан, содержащий (k+l-1) компонент (при недостатке компонент дописываемнули).
2. Включаем в набор свободную клетку,строим для нее цикл, означиваем его, приписывая свободной клетке знак плюс, и вычисляемпо этим знакам алгебраическую сумму тарифов, стоящих во всех вершинах цикла. Полученноечисло с его знаком записываем внутри свободной клетки.
3. Проделываем указанную в п.2 операциюдля каждой свободной клетки, строя всякий раз свой цикл пересчета. В результатев каждой свободной клетке появится число (положительное, отрицательное или нуль).
4. Если все полученные числа неотрицательны,то найдено оптимальное решение, минимизирующее функционал. Если эти числа неположительны,достигнут максимум функционала. При наличии чисел разных знаков включаем в плансвободную клетку, в которой стоит наибольшее по модулю отрицательное число для минимумаи положительное — для максимума.
5. В отрицательной полуцепи тогоцикла, который соответствует выбранной клетке, отыскиваем наименьшую перевозку иделаем сдвиг по циклу на это число. Находим новый допустимый план.
6. Испытываем этот план на оптимальность,т.е. для каждой свободной клетки строим цикл пересчета и вычисляем алгебраическуюсумму тарифов. При неоптимальности плана снова включаем свободную клетку в плани делаем сдвиг по соответствующему циклу. Так продолжаем до тех пор, пока план небудет оптимальным.
Для ручного счета более удобен методпотенциалов. Однако на распределительном методе основаны некоторые другие способырешения задач, что и вызывает необходимость его изучения. [5]
9. Метод потенциалов
Решение транспортной задачи любымспособом производится на макете. Макет для применения метода потенциалов имеет следующийвид.
/>
Основная часть макета выделена двойнымилиниями. Она содержит k?lклеток. Каждая клетка в этой части обозначается символом (i, j). Например,клетка, стоящая во второй строке и первом столбце, будет обозначена (2, 1). Макетсодержит в себе матрицу тарифов. Назначение строки vj и столбцаui будет выяснено в дальнейшем.
Прежде чем приступить к изложениюметода, рассмотрим некоторые предварительные понятия.
Произвольную совокупность клетокв макете называют набором. Цепью называется последовательный набор клеток, в которомкаждые две соседние клетки расположены в одном ряду (строке, столбце), причем никакиетри клетки в одном ряду не располагаются.
Пример цепи приведен в табл.2.
/>
Прямые, соединяющие взятые клетки,пересеклись, но так как клетку в пересечении мы не берем, правило цепи не нарушается.
Если последняя клетка цепи расположенав одном ряду с первой, то такая замкнутая цепь называется циклом. Некоторые разновидностициклов показаны в табл.3.
/>
Теорема. Пусть в макете (или матрице)из k строк и l столбцов произвольно отмечено k+l клеток, причемk+l ? kl. В этом случаевсегда можно построить цикл, вершины которого лежат в отмеченных клетках (можетбыть не во всех).
Замечание. Числа k и lцелые, и для них не всегда будет выполнено неравенство k+l ? kl. Если одно из этих чисел — единица,это неравенство не выполняется. Например, при k=3, l=1 имеем 3 + 1> 3·1. Однако при k=2 и l=2 будет 2+2 = 2·2, а при k и l,одновременно больших двух, неравенство всегда выполняется.
Условие k+l ? kl исключает случаи матриц с однойстрокой или одним столбцом, в которых вообще цикла построить нельзя.
Доказательство. Рассмотрим минимальныйвозможный случай: k=2, l=2 (табл.4).
/>
В макете надо выбрать k+l =4, т.е. все 4 клетки. Для этого случая теорема справедлива: выбранные клетки образуютцикл.
Возьмем теперь любые k>2,l>2. Доказательство будем вести методом математической индукции.
Допустим, теорема справедлива длямакета, у которого сумма строк и столбцов на единицу меньше взятых нами (k+l).Докажем, что при этом предположении теорема будет справедлива для принятых (k+l).
Первый случай. Среди отмеченных клетокимеется одна клетка, единственная в ряду (строке или столбце) (табл.5).
/>
Откажемся от этой клетки, исключимэту строку из рассмотрения. Тогда придем к таблице, у которой строк на единицу меньше,а число столбцов сохранилось. Число строк в сумме с числом столбцов будет меньше(k+l) на одну единицу, но и число отмеченных клеток уменьшится наодну. Для этого случая можно построить цикл по принятому допущению. Этот цикл возьмеми для нашей таблицы, так как в соответствии с оговоркой вершины цикла могут бытьи не вo всex отмеченных клетках.
Второй случай. Нет таких ситуаций,когда клетка одна. В каждой строке (столбце) больше чем одна клетка (или нет ниодной) (табл.6).
/>
Отметим одну клетку знаком плюс,пойдем от нее по строке, попадем в клетку, которая в другом столбце и неединственнаяв нем; по столбцу перейдем в другую строку, по этой строке в другой столбец и т.д.Это можно было бы продолжать до бесконечности, если бы не было конечным число отмеченныхклеток. На каком-то этапе придем в строку (столбец), в которой уже были, чем будетзамкнута цепь, т.е. получен цикл.
Выше было показано, что теорема справедливадля k=2, l=2, т.е. для k+l=4. По доказанному она справедливадля случаев: k+l=5, т.е. k+l>4; k+l=6,т.е. k+l>5; k+l>6 и т.д., т.е. для любого макета.
Допустимый план Х (xij)называется ациклическим (нециклическим), если набор клеток с отличными от нуля компонентамиплана xij>0 не содержит ни одного цикла.
Пример ациклического плана приведенв табл.7,
/>
где точки обозначают клетки, в которыхxij >0 (xij
Если в ациклическом плане Х(xij) число положительных компонентов
N = k + l — 1(остальные компоненты — нули), то элементы aij матрицы тарифовиз набора клеток, в которых расположены xij>0,будем называть Х-отмеченными.
Если же число положительных компонентплана N k + l — l, то к клеткам, занятым положительнымиxij добавляем недостающие до (k+l-1) из нулевыхклеток, лишь бы присоединенные клетки вместе с уже взятыми не допускали циклов.Тарифы aij всех взятых клеток, равно как и сами клетки, включаютсяв число Х-отмеченных.
Больше (k + l — 1)число компонент ациклического плана не может быть: />,так как уже при N=k+l по доказанной выше теореме всегда из выбранных клетокможно построить цикл.
Теорема 2 (основная теорема). Еслидля некоторого плана Х= (xij) k?l транспортнойзадачи можно подобрать систему из k+l чисел u1, u2,…,ui,…, uk; vl, v2,…, vj,…,vl, удовлетворяющую следующим условиям: vj — ui? aij для всехi = 1, 2,., k; j = 1, 2,., l, а для xij>0(xij (-X)) vj — ui = aij,то план Х будет оптимальным.
Числа ui,vj называются потенциалами пунктов отправления и пунктов назначения;условия vj — ui?aij и vj — ui = aij называютусловиями потенциальности плана Х.
К каждой клетке (i, j)относятся два потенциала: i-ro пункта отправления ui иj-ro пункта назначения vj. Условия потенциальностисловесно можно сформулировать так: разность потенциалов для всех без исключенияклеток должна быть меньше или равна тарифу, а для занятых (Х-отмеченных)клеток она должна быть точно равна тарифу. План, удовлетворяющий этим условиям,называется потенциальным.
С учетом такой терминологии основнуютеорему можно изложить короче: если некоторый план транспортной задачи потенциален,то он оптимален.
Доказательство. Допустим, что длянекоторого плана Х (xij) условия потенциальности выполнены,т.е. существует такая система чисел ui и vj,которая удовлетворяет условиям vj — ui = aijи vj — ui?aij (табл.8).
/>
Иными словами, пусть план Хпотенциален. Докажем, что этот план будет оптимальным. План Х дает значениефункционалу
/>.
Так как мы еще не знаем, оптималенплан Х или нет, то возьмем заведомо оптимальный план Х' (x?ij) и посмотрим, какое значениеон доставляет функционалу:
/>
(транспортные расходы минимальны).Выполняются ли условия потенциальности для плана Х' — неизвестно, но каждойклетке (i, j) макета 8, исходя из потенциальности плана Х,соответствует неравенство vj — ui?aijили, наоборот, aij? vj — ui. Возьмем из каждой клетки макета соответствующийх'ij, умножим его на левую и правую части последнего неравенстваи сложим. Получим неравенство
/>.
Двойную сумму в правой части обозначимдля краткости буквой S:
/>,
ее можно переписать в виде разностидвух двойных сумм:
/>.
Преобразуем эти суммы следующим образом.Первая из них в развернутом виде дает
/>
или
/>.
Аналогично вторую двойную сумму можнозаписать так:
/>.
Тогда равенство /> запишется в иной форме:
/>.
Но /> естьсумма компонент плана по j-му столбцу, она
равна потребности j-ro пунктаназначения
/>.
Аналогично /> есть сумма компонент плана,взятая по i-й строке, она равна запасам в i-м пункте отправления
/>.
Эти равенства сумм компонент по строкеи столбцу соответственно запасам и потребностям будут выполняться для любого допустимогоплана, в том числе и для взятого в самом начале плана Х (xij):
/>
Поэтому для любых допустимых плановбудем иметь
/>
и в написанном выше равенстве /> суммы x?ij можно заменить соответствующимисуммами xij:
/>
Теперь вернемся к форме записи
/>.
В плане Х (xij)по условию его потенциальности для каждой положительной компоненты xij>0 выполняется равенство vj — ui = aij.
Остальные компоненты плана равнынулю, и соответствующие слагаемые в сумме обратятся в нули. Поэтому полученная суммабудет равна
/>.
Подставляя /> в
/>,
приходим к неравенству
/>
или zmin ? zX.Иными словами, транспортные расходы по плану Х меньше или равны минимальнымрасходам. Но меньше минимальных они быть не могут, остается только равенство zX= zmin… План Х доставляет минимальные издержки, т.е. он оптимален, чтои требовалось доказать.
Таким образом, если план потенциален,то он оптимален. Это и является тем критерием, по которому судят об оптимальностиплана.
Справедливо и обратное положение:если план оптимален, то он о6язательно потенциален. Это условие (необходимость)принимается без доказательства. [5]
10. Особенности решения транспортных задач с неправильнымбалансом
Может случиться, что в рассматриваемыхпунктах запасы не равны потребностям: или запасы превосходят потребности, или жезапасы не обеспечивают потребностей.
Такая модель задачи называется открытой.Для нее тоже можно отыскать план с минимумом транспортных издержек, но не будутудовлетворены все потребности или не будет вывезен весь груз, так как нельзя подобратьтакую систему чисел, которая при суммировании по строкам давала бы один результат,а при суммировании по столбцам — другой.
Для решения задачи поступаем следующимобразом.
Первый случай. />.
В математическую модель транспортнойзадачи введем фиктивный (l+l) — й пункт назначения. Для этого в матрице задачипредусмотрим один столбец, для которого потребность будет равна излишку груза:
/>,
Все тарифы на доставку груза в этотпункт будем считать равными нулю. Получим новую задачу, причем для старой и новойзадачи функционал будет один и тот же, так как цены на дополнительные перевозкиравны нулю:
/> min
Фиктивный потребитель обеспечиваетсовместность ограничений, не внося искажений в решение.
Второй случай.
Если запасов не хватает для удовлетворенияпотребностей, т.е. />, то вводим фиктивный (k+1)- й пункт отправления, которому приписываем запас груза, равный
/>,
тарифы на доставку грузов из этогофиктивного склада опять, полагаем нулевыми. В матрице добавится одна строка. Нафункционале это не отразится, а система ограничений задачи станет совместной, т.е.станет возможным отыскание оптимального плана на минимум стоимости перевозок. [5]
11. Алгоритм решения транспортной задачи методом потенциалов
Алгоритм метода потенциалов разделяетсяна предварительный шаг, выполняемый в начале решения, и общий шаг, повторяемый дотех пор, пока не будет получен оптимум.11.1 Предварительный шаг
Этот шаг включает следующих три этапа.
1. Находим допустимый ациклическийплан.
2. Составляем систему чисел — потенциаловпунктов отправления и пунктов назначения.
3. Анализируем систему на потенциальность.Если она потенциальна (т.е. план потенциален), то найденный план оптимален. Еслисистема не потенциальна, приступаем к общему шагу.
Первый этап: нахождение допустимогоациклического плана способом северо-западного угла.
Невзирая на тарифы, начинаем составлениеплана с заполнения левой верхней клетки (1,1) (с северо-западного угла).
Смотрим на запасы M1и потребности N1. Если M1 Ml (т.е. отдаем пункту назначения весьзапас груза из первого пункта отправления — случай в таблице). Если N1M1, то в клетку (1,1) записываем N1, т.е.покрываем всю потребность первого пункта назначения за счет первого пункта отправления.
Перепишем баланс после первой операции(изменятся и потребности, и запасы). В первой строке остальные клетки можно прочеркнуть,так как весь груз пошел в первый пункт.
Второй тур начинаем опять с северо-западногоугла. Удовлетворяем оставшуюся потребность первого пункта назначения, доставив туда(N1-Ml) единиц груза из второго пункта отправления.Если потребность первого пункта удовлетворена полностью, остальные клетки в первомстолбце прочеркиваем. Переписываем баланс после второй операции.
Снова начинаем с северо-западногоугла, удовлетворяем потребность второго пункта назначения и т.д., пока справа иснизу не будут стоять нули, т.е. весь груз распределен и потребности удовлетворены.Полученный внутри таблицы план будет допустимым. Его и берем в качестве исходного.
Второй этап предварительного шага:определение системы потенциалов.
Потенциал приписывается каждому пунктуотправления (обозначается ui) и каждому пункту назначения (vj).Всего потенциалов k+l чисел. Они вносятся в специально отведенныедля этого строку и столбец макета.
Для Х-отмеченных тарифов aij,число которых всегда равно (k + l — 1), должны выполняться равенстваvj — ui = aij. Эти равенства и будут служитьтеми уравнениями, из которых находятся потенциалы. Однако таких уравнений будеттолько (k + l — 1), а неизвестных в системе (k + l),т.е. на единицу больше. Такая система уравнений имеет бесчисленное множество решений,любое из которых годится для нашей цели. Чтобы найти какое-то одно решение, значениеодного потенциала выбираем произвольно. Остальные потенциалы определяем из решениясистемы. Третий этап предварительного шага: испытание плана или системы потенциаловна потенциальность. Потенциальность заключается в том, чтобы неравенство vj — ui выполнялось для всех без исключений клеток.При этом Х-отмеченные клетки проверять не надо, так как потенциалы подобраныиз условия выполнения в них равенства.
Выделяем положительные разности dij:
dij = vj — ui — aij >0.
На этом предварительный шаг закончен.
11.2 Общий повторяющийся шаг
Общий шаг выполняется в такой последовательности.
1. Из положительных разностей dij находим наибольшую разность di0j0:
diojo = mах (vj — ui — aij> 0).
Пусть этот максимум имеет место дляклетки (i0, j0). Включаем эту клетку в наборХ-отмеченных (k + l — 1) клеток. Клеток становится (k+l),а для такого их количества всегда можно построить цикл. Этот цикл будет в даннойситуации единственным.
Действительно, набор Х-отмеченныхклеток является ациклическим. Добавим к нему одну клетку и предположим, что длянее можно построить два цикла. В этом случае всегда можно выделить цикл с вершинами,принадлежащими исходному набору, что противоречит условию его ацикличности. Поэтомутакой цикл существует только один и задача заключается в его выделении.
2. Означиваем цикл, т.е. расставляемзнаки в его вершинах. В исходной клетке (включаемой в набор) ставим плюс. Двигаемсяпо ходу или против хода часовой стрелки и ставим знаки попеременно минус, плюс,- пока не придем к исходной вершине. Так как количество вершин в цикле четно, направлениедвижения безразлично. В результате получим так называемый означенный цикл, клеткикоторого делятся поровну на клетки положительной полуцепи и клетки отрицательнойполуцепи.
3. Выбираем наименьшее значение перевозкив клетках отрицательной полуцепи (xij) —. Пусть оноравно Q:
min (xij)- = Q.
Если таких значений несколько, беремодно из них, безразлично какое.
4. Из перевозок каждой клетки отрицательнойполуцепи вычитаем Q, а к перевозкам каждойклетки положительной полуцепи прибавляем Q.Эта операция называется сдвигом по циклу на величину Q.
Процесс сдвига меняет план, но планостается допустимым.
Действительно, допустимый план обеспечиваетбаланс в строках и столбцах; всякий план, не нарушающий этот баланс, будет допустимым.Любой цикл, по которому производится сдвиг, содержит в каждом ряду (строке, столбце)по две вершины. В одну клетку добавляем Q,а из другой вычитаем Q, и баланс не нарушается.Следовательно, план, найденный в результате сдвига, останется допустимым.
После сдвига в клетке отрицательнойполуцепи с минимальной перевозкой будет стоять нуль, а в клетке (i0,j0), включенной в набор, окажется число Q. Первую клетку из плана исключаем, а вторуювключаем; план остается по-прежнему ациклическим, так как единственный имевшийсяцикл нарушается исключением клетки.
Полученный после сдвига план можнозаписать следующим образом:
/>
5. для полученного после сдвига планасоставляем новую систему потенциалов. Эти новые потенциалы можно вычислить так же,как это делалось в предварительном шаге, а можно найти исправлением уже имеющейсясистемы.
Для занятых клеток должны выполнятьсяравенства />.
Поэтому берем в таблице клетку, занятуюв результате сдвига, и исправляем для нее потенциалы так, чтобы их разность равняласьтарифу. Лучше изменять один из них — тот, который стоит в строке или столбце с меньшимчислом занятых клеток.
Затем испытываем другие занятые клеткии корректируем последовательно остальные потенциалы. Изменению подвергаются, какправило, не все числа, и такой порядок сокращает расчеты.
6. Производим исследование новойсистемы на потенциальность, т.е. исследование найденного плана на оптимальность.Для этого проверяем выполнение неравенств vj — ui ?aij для всех незанятых клеток. Если для них неравенства выполняются,то система потенциальна и план оптимален, т.е. решение закончено. Если для каких-токлеток неравенства не выполняются, вычисляем разности dij и делаем снова общий шаг и т.д., до тех пор,пока не будет получен оптимальный план. Вырождение в транспортной задаче проявляетсяв том, что среди (k+l-1) Х-отмеченных клеток оказывается клеткас нулевой перевозкой. Если эта клетка не попадает в цикл, на нее не обращаем внимания.Если она попадает в положительную полуцепь цикла, то на следующем шаге вместо нуляполучим в этой клетке положительное число. Если же нулевая клетка оказывается вотрицательной полуцепи, то Q=0, т.е. сдвигнадо делать на число нуль. Такой нулевой сдвиг плана не меняет, но нуль переходитв другую клетку, меняется набор Х-отмеченных клеток и система потенциалов. Это даетвозможность на очередном шаге осуществить уже не нулевой сдвиг и изменить план всторону его улучшения. Контроль вычислений осуществляется таким образом. В процессерешения задачи на каждом шаге полученный план проверяется на допустимость. Для этогокомпоненты плана суммируются по строкам и столбцам; суммы должны равняться соответственнозапасам и потребностям пунктов. Окончательный (оптимальный) план проверяется поформуле, вытекающей из доказательства основной теоремы:
/>,
при этом контролируются и потенциалы.[5]
12. Транспортная задача с ограничениями на пропускнуюспособность
Транспортная задача с ограниченнымипропускными спосо6ностями коммуникаций решается с дополнительным ограничением: />, где dij — пропускная способность звена (i, j) в единицу времени. Математическаямодель задачи такова:
/>,
при ограничениях
/>
Эта задача разрешима при выполненииусловий
/>.
Для транспортной задачи с ограниченнымипропускными способностями справедливы следующие условия оптимальности полученногорешения:
/>
/>
/> [8]
13. Транспортная задача по критерию времени
Кроме транспортной задачи по критериюстоимости существует задача транспортного типа по критерию времени. Постановка такойзадачи состоит в следующем.
Дана матрица времени (tij)k?l, где tij — время на перевозку грузаиз i-того пункта отправления в j-тый пункт назначения. Матрица перевозокгрузов (xij) k?l, гдеxij — количество перевозимого груза из i-того пункта отправления в j-тыйпункт назначения. Известно также наличие груза Mi и спрос на негоNj, />. Требуется определить такойплан перевозок, при котором весь груз будет доставлен потребителям в кратчайшийсрок.
Постановка транспортной задачи покритерию времени отличается от транспортной задачи по критерию стоимости лишь целевойфункцией.
Если в задаче по критерию стоимостиопределялись минимальные транспортные издержки, то при решении задачи по критериювремени следует определить наименьший промежуток времени, за который груз будетдоставлен потребителю. Решение такой задачи очень важно в случае доставки скоропортящегосяпродукта.
Исходный опорный план можно получитьпо правилам «северо-западного угла», «минимального элемента»,приближенным методом. Далее просматриваем все занятые клетки и в них выбираем максимальноевремя t, за которое осуществляется опорный план перевозок, т.е. Т=max(tij), где клетки (i; k) занятые. Каждому плануперевозок будет соответствовать вполне определенное значение Т, зависящееот плана, т.е. T=f (x). Следовательно, нужно найти такой план доставки грузапотребителям, для которого Т будет минимальным.
Определив максимальное значение Тдля исходного плана, просматриваем ту клетку, для которой t=Т=max (tij).Например, такой клеткой является (p, q). Для этой клетки строитсяцикл, который включает в себя занятые и свободные клетки. Таких циклов может бытьнесколько. Однако при построении его следует учесть условия. Занятая клетка (p,q), для которой tiq = Т будет нечетной, следующая клеткапо часовой или против часовой стрелки — четная, следующая — нечетная и т.д. Циклсостоит из двух полуциклов — четного и нечетного. Для нечетных клеток цикла обязательнодолжна быть загрузка больше нуля, а для четных — время меньше Т. Свободныеклетки, для которых время tij>Т, прочеркиваются и врасчет не принимаются.
Построив цикл для разгрузочной клетки(p, q), для которой t (p,q) = Т, определяем наименьшуюзагрузку в нечетных клетках цикла. Полученное количество груза вычитается из грузовнечетных клеток и добавляется к числам четных клеток цикла. При этом может оказаться,что после смещения по циклу клетка (p, q) не разгрузится, тогда сновастроится цикл и производится разгрузка клетки до тех пор, пока количество грузане станет равным нулю. После разгрузки клетки, имеющей максимальный промежуток времени,получаем новый план перевозок, для которого отыскивается разгрузочная клетка и сновапроизводится процедура построения цикла и смещения груза по циклу. Процесс продолжаетсядо тех пор, покуда можно будет строить разгрузочные циклы. В случае невозможностипостроить такой цикл в полученных занятых клетках плана выбираем максимальное время,которое и будет искомым по реализации оптимального плана. [9]
14. Применение транспортной задачи для решения экономическихзадач
Во многих снабженческих, транспортныхи других организациях во всем мире рассчитываются маршруты доставки материалов настроительные площадки, планы длительного прикрепления поставщиков к потребителям,планы перевозок топлива. Задачи эти часто усложняются разного рода дополнительнымиусловиями; например, в них включается расчет не только себестоимости перевозок,но и себестоимости производства продукции (производственно-транспортная задача),оптимизируется совместно доставка взаимозаменяемых видов продукции, оптимизируетсядоставка грузов с промежуточными базами (складами).
Кроме того, следует учитывать, чтоэкономико-математическая модель транспортной задачи позволяет описывать множествоситуаций, весьма далеких от проблемы перевозок, в частности, находить оптимальноеразмещение заказов на производство изделий с разной себестоимостью. [2]
Алгоритм н методы решения транспортнойзадачи могут быть использованы при решении некоторых экономических задач, не имеющихотношения к транспортировке грузов. В этом случае величины тарифов aijимеют различный смысл в зависимости от конкретной задачи.
1. Оптимальное закрепление за станкамиопераций по обработке деталей. В них величина aij является производительностью.Задача позволяет определить, сколько времени и на какой операции нужно использоватькаждый из станков, чтобы обработать максимальное количество деталей. Так как транспортнаязадача требует нахождения минимума, то значения aij берутся сотрицательным знаком.
2. Оптимальные назначения или проблемавыбора. Имеется k механизмов, которые могут выполнять l различныхработ с производительностью aij. Задача позволяет определить,какой механизм и на какую работу надо назначить, чтобы добиться максимальной производительности.
3. Задача о сокращении производствас учетом суммарных расходов на изготовление и транспортировку продукции.
4. Увеличение производительностиавтомобильного транспорта за счет минимизации порожнего пробега, сокращение которогопозволит уменьшить количество автомобилей для перевозок за счет увеличения их производительности.
5. Решение задач с помощью методазапрещения перевозок. Используется в том случае, если груз от некоторого поставщикапо каким-то причинам не может быть направлен одному из потребителей. Данное ограничениеможно учесть, присвоив соответствующей клетке достаточно большое значение стоимости.[7]
Заключение
Первым звеном в системе рационализацииструктуры хозяйственных связей является плановая увязка потребностей и ресурсов,т.е. определение плана снабжения, в котором суммарные производственные потребностина период планирования сбалансированы с фондами, предназначенными на тот же период.Баланс производства и потребления — необходимое условие составления планов материально-техническогоснабжения. Это связано с подготовкой оптимизационных межотраслевых и межпродуктовыхдинамических моделей производства и распределения продукции.
В рамках же сбалансированности производстваи потребления роль системы материально-технического обеспечения заключается в оказанииуслуг на всех уровнях управления обращением средств производства, которые состоятв размещении заказов на отгрузку конкретных видов продукции по поставщикам, прикреплениипотребителей на прямые длительные связи, транзитное и складское снабжение, в установленииоптимальных уровней запасов и методов управления ими, оказании услуг по гарантированномукомплексному снабжению, плановому распределению средств производства путем оптовойторговли и др. Эти вопросы теснейшим образом связаны с рационализацией хозяйственныхсвязей.
Рациональное прикрепление потребителейк поставщикам в значительной степени определяет структуру хозяйственных связей,их экономическую эффективность. Под оптимальным мы понимаем такой план их прикрепления,который позволяет при минимальных издержках на поставки и содержание запасов максимальноиспользовать производственные мощности поставщиков и бесперебойно питать потребителей.[8]
Итак, установление рациональных связеймежду предприятиями наряду с выявлением потребностей и их увязкой с ресурсами — основная задача материально-технического снабжения, поэтому владение приемами инавыками решения оптимизационных задач математического программирования, в частноститранспортной, является важной составляющей образования экономиста-менеджера.
Список использованной литературы
1) Баканов, М.И. Экономический анализ: Учебное пособие / М.И. Баканов,А.Д. Шеремет. — М.: Финансы и статистика, 2002. — С.40-41.
2) Лопатников, Л.И. Словарь современной экономической науки / Л.И. Лопатников// Экономико-математический словарь. — М.: ABF, 1996. — С.43-44, 543-545.
3) Карманов, В.Г. Математическое программирование: Учебник для вузов.- М.: Наука, 1975. — С.16-18.
4) Карасев, А.И. Курс высшей математики для экономических вузов: Учебникдля экономических вузов / А.И. Карасев, З.М. Аксютина, Т.И. Савельева — М.: Высшаяшкола, 1982. — С.279-285.
5) Полунин, И.Ф. Курс математического программирования: Учебник длявузов. — Минск: Высшая школа, 1970. — С. 194-230.
6) Сакович, В.А. Исследование операций: Учебник для вузов. — Минск:Высшая школа, 1985. — С.75.
7) Красс, М.С. Математика для экономистов: Учебник для экономическихвузов. — Санкт-Петербург: Питер, 2006. — С.289-299.
8) Сакович, В.А. Управление комплексными поставками: Учебник для вузов.- Минск: Высшая школа, 1989. — С.100-108.
9) Холод, Н.И. Математические методы анализа и планирования: Учебникдля вузов. — Минск: Ураджай, 1989. — С.97-99.
10) Холод, Н.И. Пособие по решению задач по линейной алгебре и линейномупрограммированию: Пособие для вузов. — Минск: издательство БГУ, 1971. — С.159.