РЕФЕРАТ
по дисциплине МАТЕМАТИЧЕСКИЕ ОСНОВЫ ПРОГРАММИРОВАНИЯ
на тему: «Метод потенциалов для решения транспортной задачи»
Москва, 2010
1.Решение транспортной задачи
Так как транспортная задача является задачейлинейного программирования, то основные этапы ее решения будут такими:
Iэтап. Нахождение начального допустимого решения.
IIэтап. Выделение из небазисных переменных вводимой в базиспеременной (метод потенциалов). Если все небазисные переменные удовлетворяютусловию оптимальности, то следует закончить вычисления; в противном случае —перейти к III этапу.
IIIэтап. Выбор выводимой из базиса переменной (используяусловия допустимости) из числа переменных текущего базиса; затем нахождениенового базисного решения и возвращение ко II этапу.
Для лучшего понимания метода потенциалов, рассмотримподробнее все этапы решения транспортной задачи, учитывая ее специфику.
I этап. Определениеначального допустимого решения
Для сбалансированной транспортной задачи существуеттолько m + n — 1 независимых уравнений. Таким образом, начальноебазисное допустимое решение должно иметь m+n-1 базисных переменных.
Начальное базисное решение транспортной задачиполучают непосредственно из транспортной таблицы. Для этого можно использоватьтри процедуры.
1. Правило«северо-западного угла»
При нахождении опорного плана транспортной задачиметодом «северо-западного угла» на каждом шаге рассматривают первыйиз оставшихся пунктов отправления и первый из оставшихся пунктов назначения.Заполнение транспортной таблицы начинается с левого верхнего угла(северо-западного), двигаясь далее по строке вправо или по столбцу вниз(увеличение i, увеличение j). Переменной Х11 приписываютмаксимальное значение, допускаемое ограничениями на спрос и запасы.
После этого вычеркивают соответствующий столбец илистроку, фиксируя этим, что остальные переменные вычеркнутого столбца (строки) полагаются равными нулю. Еслиограничения выполняются одновременно, то можно вычеркнуть либо строку, либостолбец. Процесс завершается тогда, когда будет присвоено значение переменной хmin.
Исходный опорный план, построенный по правилу«северо-западного угла», обычно оказывается весьма далеким отоптимального, так как при его формировании не учитывается стоимость перевозок(величина сij). Более совершенным правилом является правило«минимального элемента».
2.Правило «минимального элемента»
В методе «северо-западного угла» на каждомшаге потребность первого из оставшихся пунктов назначения удовлетворяется засчет запасов первого из оставшихся пунктов отправления. Очевидно, что выборпунктов назначения и отправления целесообразно производить, ориентируясь настоимость перевозок, а именно на каждом шаге следует выбирать какую-либоклетку, отвечающую минимальному тарифу (если таких клеток несколько, то следуетвыбирать любую из них), и рассматривать пункты назначения и отправления,соответствующие выбранной клетке.
Правило «минимального элемента»заключается в том, чтобы перевозить максимально возможные объемы из пунктовотправления маршрутами минимальной стоимости. Заполнение таблицы начинаем склетки, которой соответствует наименьшая стоимость перевозки (элемент cij) из всей таблицы. Переменной этой клетки хij присваивается максимально возможное значение сучетом ограничений. Затем остаток по столбцу или строке помещается в клеткутого же столбца или строки, которой соответствует следующее по величинезначение сij и т. д. Иными словами, последовательностьзаполнения клеток определяется по величине сij, а помещаемая в этих клетках величина хij такая же, как и в правиле «северо-западногоугла».
3.Метод аппроксимации Фогеля.
При определении оптимального плана транспортнойзадачи методом аппроксимации Фогеля на каждой итерации по всем столбцам и повсем строкам находят разность между двумя записанными в них минимальнымитарифами. Эти разности записывают в специально отведенных для этого строке истолбце условий задачи. Среди указанных разностей выбирают максимальную. Встроке (или столбце), которой данная разность соответствует, определяютминимальный тариф. Клетку, в которой он записан, заполняют на данной итерации.
Этот метод дает наилучшее начальное приближение,часто оказывающееся оптимальным планом.
Алгоритм решения транспортной задачи методомаппроксимации Фогеля следующий:
I этап. Определениеначального допустимого плана.
1. Для каждой строкитаблицы необходимо упорядочить элементы стоимости перевозок cij по возрастанию. Определить величину«штрафа» строки как разность значений второго и первого элемента вранжированном ряду.
2. Для каждого столбца таблицынеобходимо упорядочить элементы стоимости перевозок cij по возрастанию. Далее необходимо определитьвеличину штрафа столбца.
3. Определить строку (илистолбец), имеющую (имеющий) наибольший штраф по всем штрафам строк и столбцов,а в ней (в нем) — элемент с минимальной величиной стоимости перевозок сij. Зафиксировать индексы (i,j) этого элемента.
4. Присвоить наибольшеезначение из допустимых (с учетом ограничений) переменной хij, индексы которой соответствуют шагу 3.
5. Скорректироватьвеличины аi и bj ивычеркнуть строку i, если аi = 0, или столбец j,если bj = 0.
6. Проверить, все ливеличины аi и bj. равны нулю, если да, то окончить вычисления; впротивном случае взять в качестве исходной оставшуюся часть таблицы и перейти кшагу 3.
Как правило, применение метода аппроксимации Фогеляпозволяет получить либо опорный план, близкий к оптимальному, либо самоптимальный план.
II этап. Определение вводимой вбазис переменной («метод потенциалов»).
Отметим, что «метод потенциалов»эквивалентен принципу решения задачи линейного программирования и использованиюусловия оптимальности в симплекс-методе. Сначала находят опорный плантранспортной задачи, а затем его улучшают до получения «оптимальногоплана». Содержание «метода потенциалов» заключается в следующем:
1. Каждой строке iи столбцу j транспортной таблицы ставится в соответствие числа ui и vj, называемые потенциалами. Они должны для каждойбазисной переменной хij текущего решения удовлетворять условию ui + vj = сij. Эти условия приводят к системе, состоящей из m+ n — 1 уравнений (так как имеется всего m+ n — 1 базис-переменных), в которых фигурируют m+ n неизвестных. Значение потенциалов определяют изэтой системы уравнений, придавая одному из них произвольное значение (например,ui = 0).
2. Определяются оценки cij для небазисных переменных в соответствии ссоотношением:
/>сij = ui + vj – сij
3. />Если все оценки сij отрицательны, то найденное решение оптимально, впротивном случае необходимо определить новую вводимую в базис переменную.
4. />Вводимой в базис переменной является небазиснаяпеременная, имеющая самую большую положительную оценку сij.
Наиболее эффективным методом определения вводимойпеременной является метод дифференциальных рент. Если при определенииоптимального плана транспортной задачи методом потенциалов сначала находилсякакой-нибудь ее опорный план, а затем он последовательно улучшался, то принахождении решения транспортной задачи методом дифференциальных рент сначаланаилучшим образом распределяют между пунктами назначения часть груза (такназываемое условнооптимальное распределение) ина последующих итерациях постепенно уменьшают общую величину нераспределенныхпоставок.
Первоначальный вариант распределения грузаопределяют следующим образом. В каждом из столбцов таблицы данных транспортнойзадачи находят минимальный тариф. Найденные числа заключают в кружки, а клетки,в которых стоят указанные числа, заполняют. В них записывают максимальновозможные числа. В результате получают некоторое распределение поставок груза впункты назначения. Это распределение в общем случае не удовлетворяетограничениям исходной транспортной задачи. Поэтому в результате последующихшагов следует постепенно сокращать нераспределенные поставки груза так, чтобыпри этом общая стоимость перевозок оставалась минимальной. Для этого сначалаопределяют избыточные и недостаточные строки.
Строки, соответствующие поставщикам, запасы которыхполностью распределены, а потребности пунктов назначения, связанных с даннымипотребителями запланированными поставками, не удовлетворены, считаютсянедостаточными. Эти строки иногда называют также отрицательными. Строки, запасыкоторых исчерпаны не полностью, считаются избыточными. Иногда их называют такжеположительными.
После того как определены избыточные и недостаточныестроки, для каждого из столбцов находят разности между числом в кружке иближайшим к нему тарифом, записанным в избыточной строке. Если число в кружкенаходится в положительной строке, то разность не определяют. Среди полученныхчисел находят наименьшее. Это число называется промежуточной рентой. После определения промежуточной ренты переходят кновой таблице. Эта таблица получается из предыдущей таблицы прибавлением ксоответствующим тарифам, стоящим в отрицательных строках, промежуточной ренты.Остальные элементы остаются прежними. При этом все клетки новой таблицы считаютсвободными. После построения новой таблицы начинают j заполнение ее клеток. Теперь уже число заполняемыхклеток на одну больше, чем на предыдущем этапе. Эта дополнительная клетка находитсяв столбце, в котором была записана промежуточная рента. Все остальные клеткинаходятся по одной в каждом из столбцов и в них записаны наименьшие для данногостолбца числа, заключенные в кружки. Заключены в кружки и два одинаковых числа,стоящих в столбце, в котором в предыдущей таблице, была записана промежуточнаярента.
Поскольку в новой таблице число заполняемых клетокбольше, чем число столбцов, то при заполнении клеток следует пользоватьсяспециальным правилом, которое состоит в следующем. Выбирают некоторый столбец(строку), в котором имеется одна клетка с помещенным в ней кружком. Эту клеткузаполняют и исключают из рассмотрения данный столбец (строку). После этогоберут некоторую строку (столбец), в которой имеется одна клетка с помещенным вней кружком. Эту клетку заполняют и исключают из рассмотрения данную строку(столбец). Продолжая так, после конечного числа шагов заполняют все клетки, вкоторых помещены кружки с заключенными в них числами. Если к тому же удаетсяраспределить весь груз, имеющийся в пунктах отправления, между пунктаминазначения, то получают оптимальный план транспортной задачи. Если жеоптимальный план не получен, то переходят к новой таблице. Для этого находятизбыточные и недостаточные строки, промежуточную ренту и на основе этого строятновую таблицу. При этом могут возникнуть некоторые затруднения при определениизнака строки, когда ее нераспределенный остаток равен нулю. В этом случаестроку считают положительной при условии, что вторая заполненная клетка,стоящая в столбце, связанном с данной строкой еще одной заполненной клеткой,расположена в положительной строке.
После конечного числа описанных выше итерацийнераспределенный остаток становится равным нулю. В результате получаютоптимальный план данной транспортной задачи.
III этап. Определение переменной,выводимой из базиса (построение цикла).
Процедура построения цикла эквивалентнаиспользованию условия допустимости в симплекс-методе.
1. Строится замкнутыйцикл, соответствующий вводимой переменной. Он состоит из последовательностигоризонтальных и вертикальных связанных отрезков, концами которых должны бытьбазисные переменные (за исключением тех концов, которые относятся к вводимой вбазис переменной). Для каждого базисного решения и соответствующей небазиснойпеременной можно построить лишь один цикл.
2. Нечетным вершинам цикла(начиная с вводимой в базис переменной) присваивается знак "+",четным – "-" (будем называть эти клетки плюсовыми и минусовыми).
3. Определяется выводимаяиз базиса переменная, которой является одна из базисных переменных,расположенных в вершинах цикла, отмеченных знаком "-" и имеющихнаименьшее значение.
4. Формируется новоедопустимое базисное решение. Для этого переменные, находящиеся в вершинахцикла, соответствующим образом корректируются, а именно уменьшаются илиувеличиваются на величину вводимой в базис переменной в зависимости от знакавершины цикла.
Описанный выше переход от одного опорного планатранспортной задачи к другому ее опорному плану называется сдвигом по циклупересчета. Следует отметить, что при сдвиге по циклу пересчета число занятыхклеток остается неизменным и равным (n + m — 1).
Однако при определении опорного плана или в процессерешения задачи может быть получен вырожденный опорный план. Чтобы избежатьзацикливания, следует соответствующие нулевые элементы опорного плана заменитьсколь угодно малым числом ε и решать задачу как невырожденную. Воптимальном плане такой задачи необходимо считать ε = 0.
транспортныйзадача алгоритм фогель цикл
2. Примерпрактического решения задачи оптимального планирования
Перевозкитоваров различными транспортными средствами в ряде случаев приводят к такимнежелательным явлениям, как порожние пробеги, простои, встречные инерациональные перевозки. Для их исключения используются методы оптимальногопланирования перевозок, в частности такая экономико-математическая модель, кактранспортная задача.
Простейшимпримером транспортной задачи является задача о планировании перевозокнекоторого продукта из конечного числа пунктов отправления в конечное числопунктов назначения при обеспечении минимальных затрат на выполнение даннойоперации.
Пример: Трипоставщика некоторого товара располагают следующими запасами: первый – 120единиц, второй – 100 единиц, третий – 80 единиц. Товар должен быть перевезентрем потребителям: спрос первого – 90 единиц; спрос второго – 90 единиц; спростретьего – 120 единиц. Известны также показатели затрат (cij) наперевозку единицы товара от каждого поставщика к каждому потребителю.
Требуетсясоставить оптимальный план перевозок, приводящий к наименьшим затратам навыполнение данной операции.
Под планомперевозок понимается матрица
X11
X12
X13
X21
X22
X23
X31
X32
X33
в которой хij количество единиц товара, планируемого к перевозке отпоставщика с номером i к потребителюс номером j.
Для решениязадачи исходные данные удобно свести в таблицу:
Поставщики Возможности поставщиков Потребители и их спрос 1 2 3 90 90 120 1 120 7 6 4 2 100 3 8 5 3 80 2 3 7
Каждую клеткутаблицы пометим двойным индексом (i, j). Первый (i) – номерпоставщика, второй (j) – номерпотребителя.
Числа напересичении стоимости перевозок и обозначаются сij.
Математическаяпостановка данной задачи имеет вид: найти минимумцелевой функции (показателя эффективности)
Z= 7х11+ 6х12 + 4х13 + Зх21 + 8х22 + 5х23+ +2х31 +3х32 + 7х33 при ограничениях:
n n n
Σx1j =120; Σx2j =100; Σx3j =80;
j=i j=i j=i
m m m
Σxi1 =90; Σxi1 =90; Σxi1 =120; хij>0
i=l i=l i=l
Транспортнаязадача относится к классу задач линейного программирования. Решение таких задачобычно связано с получением опорного (допустимого) плана и последующим егоулучшением.
Опорныйплан может быть получен различными методами. Рассмотрим метод минимального элемента, или метод наименьших.
Всоответствии с методом наименьших затрат выберем в таблице клетку, имеющуюнаименьший показатель затрат, т. е. клетку (3,1). Произведем поставку в этуклетку, равную 80 единицам, поскольку первому потребителю требуется .90 единиц,а у третьего поставщика в наличии лишь 80 единиц. Первому потребителюнеобходимо еще 10 единиц товара. Он может получить их или от первого, или отвторого поставщика. Так как показатель затрат в клетке (2,1) меньше, чем в клетке(1,1), то записываем 10 единиц в клетку (2,1).
Второйпоставщик, отдав 10 единиц, будет располагать 90 единицами. Их можно направитьвторому или третьему потребителю. В связи с тем, что показатель затрат в клетке(2, 3) меньше, чем в клетке (2, 2), направим их третьему потребителю.Недостающие 30 единиц третий потребитель получит от первого поставщика.
Оставшиеся упервого поставщика 90 единиц запишем в клетку (1, 2) и, тем самым, удовлетворимспрос второго потребителя.
На этомраспределение можно считать законченным.Поставщики Возможности поставщиков Потребители и их спрос 1 2 3 90 90 120 1 120 7
6
90
4
30 2 100
3
10 8
5
90 3 80
2
80 3 7
Получивопорный план, необходимо оценить соответствующую ему стоимость перевозок(показатель эффективности или целевую функцию). Для плана, полученного методомнаименьших затрат, Z = 1300 ед.
Следующимэтапом решения задачи, независимо от того, каким методом был найден опорныйплан, является последовательное его улучшение до получения оптимального распределения.С этой целью каждому поставщику товаров поставим в соответствие потенциалы А1,А2, А3 и запишем их в дополнительном столбце, а каждомупотребителю – потенциалы B1, В2,В3, которые запишем в дополнительной строке. Один из потенциалов,например A1 приравняем кнулю, а остальные найдем с использованием:
Аij = Аi + Вj
Запишемданное соотношение для всех заполненных клеток (Хij > 0) и определим А2, А3, В1,В2, В3. Для незаполненных клеток (Хij = 0) запишем аналогичную зависимость, левую частькоторой принято называть псевдостоимостью.
Cij = Ai+Bj
Условиеоптимальности плана заключается в том, что для каждой свободной клетки (Xij = 0)
Сij
/>Найдем для свободных клеток разностиΔij = Сij – Cij Поскольку одна из разностей,соответствующая клетке (3,2), отрицательна, то улучшение плана начинаем именнос нее.Поставщики Возможности поставщиков Потребители и их спрос
Ai 1 2 3 90 90 120 1 120 72
6
90
4
30 2 100
3
10 87
5
90 2 3 80
2
80 36 74 4
Bj 7 6 3
Заметим, чтоесли отрицательных разностей несколько, то первой выбирается клетка, длякоторой разность по абсолютной величине больше.
Догрузимклетку (3, 2), поставив в нее знак плюс (+), и составим цепь пересчета поправилу: цепь пересчета строится в виде прямоугольника, одна из вершин которогонаходится в свободной клетке (3, 2), а остальные – в занятых; все углы должныбыть прямыми; в одной строке и в одном столбце не должно быть более двухвершин; всем вершинам приписываются чередующиеся знаки (плюс – догрузить, минус– разгрузить).Поставщики Возможности поставщиков Потребители и их спрос
Ai 1 2 3 90 90 120 1 120 72
/>6-
90
4+
30 2 100
/>3+
10 87
5-
90 2 3 80
2-
80 3+6 74 4
Bj 7 6 3
Из клеток сознаком минус (-) выбирается наименьшая величина груза min (80, 90, 90)= 80 и перемещается последовательно по клеткам построенной цепи: 80 единицдобавляются в клетки со знаком плюс и изымаются из клеток со знаком минус. Такимобразом, получаем новый план перевозок. Применив к нему рассмотренную вышеметодику, можно убедиться, что этот план является оптимальным.
Поставщики Возможности поставщиков Потребители и их спрос 1 2 3 90 90 120 1 120 7
6
10
4
110 2 100
3
90 8
5
10 3 80 2
3
80 7
В общемслучае математическая постановка транспортной задачи имеет вид:
/>,
приограничениях
/>
Врассмотренном примере
/>
т.е.возможности поставщиков равны суммарному спросу потребителей. Транспортныезадачи подобного вида называют закрытыми. Задачи, длякоторых это условие не выполняется представляют собой открытые задачи. Для решения открытых задач их приводят кзакрытому виду путем введения фиктивного поставщика или фиктивной потребителя свозможностями по поставке или спросом, определяемыми по формуле
/>
В остальномметодика решения задачи остается неизменной.
Список использованнойлитературы
1. Математическоепрограммирование. Учебное издание. Под общей редакцией К.В. Балдина, авторыК.В. Балдин, Н.А. Брызгалов, А.В. Рукосуев. Москва: «Издательско-торговаякорпорация «Дашков и К», 2010.