Методы решения задач линейного программирования транспортного типа

Размещено на http://www.allbest.ru/

Методы решения задач линейного программирования транспортного типа



План

1. Постановка и модель транспортной задачи в различных формах записи

2. Алгоритм решения задачи

3. Приближенные распределительные методы



1. Постановка и модель транспортной задачи в различных формах записи

Среди проблем, для исследования которых успешно применяется линейное программирование, важное значение имеет так называемая транспортная задача.

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

Таким образом, пусть имеем m пунктов, в которых находится известное количество однородных грузов (поставщики). Порядковый номер поставщика обозначается i, то есть i=1,2,…,m. Наличие грузов у поставщика bi. Имеется n пунктов испытывающих потребность в этих грузах (потребителей). Порядковый номер потребителя j=1,2,…,n. Потребность в грузах каждого потребителя aj. Известна «цена» перевозки единицы груза от каждого поставщика к каждому потребителю (сij). Необходимо составить план перевозки грузов от поставщиков к потребителю, т.е. определить: какое количество груза необходимо перевезти от каждого поставщика к каждому потребителю (xij), причем значения xij должны отвечать следующим требованиям:

1) общие затраты на перевозку грузов должны быть минимальными;

2) все грузы от поставщиков должны быть вывезены;

3) потребности потребителей в грузах должны быть удовлетворены.

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

- условие разрешимости задачи.

Если условие разрешимости выполняется, то задача будет являться задачей, так называемого закрытого типа (сбалансированной). Иначе - задача открытого типа (несбалансированная). Для того чтобы решить задачу открытого типа, надо её «закрыть» (то есть привести к закрытому типу). Для этого вводится или фиктивный поставщик или фиктивный потребитель.

В случае, когда суммарные запасы превышают суммарные потребности, необходим дополнительный фиктивный пункт потребления, который будет формально потреблять существующий излишек запасов, то есть:

.

Если суммарные потребности превышают суммарные запасы, то необходим дополнительный фиктивный пункт отправления, формально восполняющий существующий недостаток продукции в пунктах отправления:

.

Введение фиктивного потребителя или отправителя повлечет необходимость формального задания фиктивных тарифов (реально не существующих) для фиктивных перевозок. Поскольку нас интересует определение наиболее выгодных реальных перевозок, то необходимо предусмотреть, чтобы при решении задачи (при нахождении опорных планов) фиктивные перевозки не рассматривались до тех пор, пока не будут определены все реальные перевозки. Для этого надо фиктивные перевозки сделать невыгодными, чтобы при поиске решения задачи их рассматривали в самую последнюю очередь. Таким образом, если целевая функция стремится к min, то затраты берутся во всех фиктивных клетках таблицы произвольные, одинаковые и на порядок выше настоящих цен, т.е. величина фиктивных тарифов должна превышать максимальный из реальных тарифов, используемых в модели: . Если целевая функция стремится к max, то берётся равная нулю.

Развёрнутая форма записи модели транспортной задачи.

Для удобства, прежде чем писать модель, запишем в виде матрицы цен все значения cij. А также в виде матрицы грузоперевозок переменные xij.

Матрица цен:

С =



Матрица С = (cij)m*n называется также матрицей тарифов (издержек или транспортных расходов).

Матрица грузоперевозок:

Х =

Матрица Х = (хij)m*n еще называется планом транспортной задачи.

Модель транспортной задачи будет выглядеть следующим образом.

I. Целевая функция описывает затраты на перевозку грузов:

Z=c11x11+c12x12+…+c1nx1n+c21x21+c22x22+…+c2nx2n+… +cm1xm1+cm2xm2+…+cmnxmnmin.

II. Система ограничений описывает второе и третье требования для xij из постановки задачи.

1 группа: условие полного вывоза грузов от поставщиков (сумма грузов, вывезенных от поставщика должна быть равна наличию):

x11+x12+…+x1n = b1,

x21+x22+…+x2n = b2,

……………………

xm1+xm2+…+xmn = bm;

2 группа: условие удовлетворения потребителя (сумма грузов привезённых потребителю должна быть равна его потребности):



x11+x21+…+xm1=a1,

x12+x22+…+xm2=a2,

…………………….

xm1+xm2+…+xmn = аn.

III. Условие неотрицательности переменных величин x110, x120, …, xmn0.

Структурная форма записи модели транспортной задачи.

В специализированной литературе модели даются в структурной форме.

II.

III. xij0 (i = 1,2,…,m, j = 1,2,…,n).

Табличная форма записи модели транспортной задачи.

Общепринято в таблице информацию по поставщикам располагать по строкам, по потребителю - по столбцам.

Размер таблицы: cтрок m+2, cтолбцов n+2.

Матрицы транспортных расходов и перевозок совмещают обычно в одну двойную матрицу - матрицу планирования.

Если в таблицу записана только исходная информация и нет значений xij, то это рабочая таблица или макет задачи. Если значения xij проставлены, то получаем первый вариант решения задачи. В такой форме задачи решаются.

	1	2	…	n	bi
1	c11 x11	c12 x12	…	c1n x1n	b1
2	c21 x21	c22 x22	…	c2n x2n	b2
…	…	…	…	…	…
m	cm1 xm1	cm2 xm2	…	cmn xmn	bm
aj	a1	a2	…	an

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

1. Полное отсутствие связи между поставщиком и потребителем, то есть xij = 0. Это означает, что в данной клетке матрицы искомый объем перевозок должен быть равен нулю. В этом случае оценка переменной завышается на большую величину, обычно обозначаемую буквой М, и «попадание» груза в эту клетку нежелательно, так как целевая функция стремиться к минимуму (и занижается, если Zmax).

2. Наличие частной заранее фиксированной связи между поставщиками и потребителями, то есть xij = q (искомый объем перевозок от i-го поставщика к j-му потребителю должен быть строго равен q). Тогда, до начала решения задачи от величины грузов соответствующего поставщика и потребителя вычитается величина q, затем в соответствующую клетку пересечения поставщика и потребителя записывается завышенная оценка М (при Zmin и заниженная при Zmax) и задача решается обычным методом.

3. xij ? q, то есть искомый объем перевозок от i-го поставщика к j-му потребителю должен быть не меньше величины q. В этом случае до начала решения от величины грузов соответствующего поставщика и потребителя вычитается величина q, затем задача решается обычным путем.

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

2. Алгоритм решения задачи

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

Решение транспортной задачи разбивается на два этапа:

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

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

После выполнения первого этапа шаги второго этапа проводятся до тех пор, пока не будет найдено оптимальное распределение поставок.

1-ый этап. Построение первоначального опорного плана

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

Пример.

b1 =1500 a1 = 800 13 12 15 16

b2 =1000 a2 = 1200 С = 17 15 14 13

b3 =2000 a3 = 1400 15 14 13 16

a4 = 1100

Решить на минимум, заполнив рабочую таблицу методом северо-западного угла.

Заполнение рабочей таблицы методом северо-западного угла

	1	2	3	4	bi
1	13 800	12 700	15	16	1500
2	17	15 500	14 500	13	1000
3	15	14	13 900	16 1100	2000
aj	800	1200	1400	1100	4500



Zmin = 800*13 + 700*12 + 500*15 + 500*14 + 900*13 + 1100*16 = 62600.

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

Методы наилучших цен и аппроксимации также можно использовать на данном этапе.

2-ой этап. Метод потенциалов. Оптимальность базисного решения.

Полученный одним из распределительных методов опорный план сначала необходимо проверить на вырожденность. Вариант будет невырожденным, если число заполненных клеток N равно сумме поставщиков и потребителей за вычетом единицы:

N = m + n - 1.

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

Невырожденный вариант необходимо проверить на оптимальность.

Теорема об оптимальности. Вариант решения задачи будет оптимальным, если найдется такая система абстрактных чисел, называемых потенциалами поставщиков и потенциалами потребителей, при которой для всех клеток таблицы будет выполняться условие:

vj - ui cij (при Z min) и vj - ui ? cij (при Z mах),

где vj - потенциалы потребителей,

ui - потенциалы поставщиков,

cij - цена перевозки единицы груза (условные т/км).

Причем,

vj - ui = cij

для занятых клеток и

vj - ui cij (или vj - ui ? cij)

для свободных клеток.

На основании этой теоремы исследование на оптимальность проводится в 2 этапа:

1) для каждой занятой клетки составляется уравнение

vj - ui = cij

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

2) для свободных клеток таблицы проверяется условие vj -ui cij (или vj - ui ? cij). Вариант будет оптимальным, если для всех свободных клеток это условие выполнится.

Для каждой клетки, в которой не выполняется условие vj - ui cij (или vj - ui ? cij), рассчитывается оценка

ij = (vj - ui) - cij

Клетка, содержащая ij, называется «плохой», а полученная оценка используется при перераспределении грузов.

То есть исследование на оптимальность не только отвечает на вопрос, оптимален вариант или нет, но еще и подсказывает, в каком направлении надо его улучшать при необходимости.

Перераспределение грузов и получение нового варианта.

Смысл перераспределения заключается в том, чтобы в самую «плохую» клетку (т.е. значение ij наибольшее) перераспределить какое-то количество груза. Перераспределение грузов должно отвечать следующим требованиям:

1) должны выполняться требования системы ограничений модели;

2) вариант решения задачи должен остаться ациклическим, т.е. не должна появиться лишняя заполненная клетка;

3) должно выполняться условие неотрицательности в модели, т.е. x ij 0.

С учетом данных требований, алгоритм перераспределения будет состоять из двух шагов:

1) наметить маршрут перераспределения груза.

Для этого в таблице строится цикл перераспределения объектов перевозок. Цикл представляет собой замкнутую ломаную линию, которая начинается в той свободной клетке, где условие оптимальности нарушается наиболее сильно (т.е. там, где ij наибольшая).

При построении цикла можно проходить как через занятые, так и через свободные клетки таблицы, но повороты делаются только в занятых клетках и под прямым углом;

2) определить порядок изменения объемов перевозок в вершинах цикла.

Для этого в вершинах цикла расставляют знаки «+» и «-», причем в начале цикла (клетка, где ij наибольшая) ставится знак «+», в следующей «-», в следующей «+» и т.д. Получаем чередование знаков. Направление движения при расстановке знаков от свободной клетки безразлично, так как количество вершин цикла является четной величиной. Наличие знака «+» в вершине цикла показывает, что объем перевозок необходимо увеличить, а «-» - уменьшить. Увеличение и уменьшение объемов перевозок в вершинах цикла производится на одинаковую величину, которая выбирается равной наименьшему из объемов перевозок в тех клетках, где в вершине цикла стоит знак «-». Таким образом, из отрицательной вершины контура необходимо выбрать наименьшее значение хij. В новой рабочей таблице получаем следующий вариант решения задачи: выбранное значение xij из отрицательных вершин контура предыдущей таблицы отнимаем, а к положительным - прибавляем. Заполненные клеточки, не являющиеся вершинами контура, не меняют свое значение.

В итоге получаем новый вариант. Следующие шаги поиска оптимального варианта совершаются по аналогии вышеизложенного.

Замечание: алгоритм перераспределения одинаков и при Zmin и при Zmах.

3. Приближенные распределительные методы

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

Метод наилучших цен

Метод наилучших цен позволяет получить более выгодный опорный план, чем метод северо-западного угла. При распределении груза на каждом шаге этого метода выбирается клетка с наилучшей ценой. Наилучшей считается минимальная цена при Z>min, и максимальная цена при Z>max. Если существует несколько клеток с одинаковыми лучшими тарифами, то из них для определенности можно выбрать клетку, находящуюся левее и выше остальных.

Алгоритм метода наилучших цен:

1) рассматривая рабочую таблицу, найти клетку с наилучшей ценой;

2) проставить в эту клетку максимально допустимое значение хij;

3) вычеркнуть свободные нерабочие клетки;

4) откорректировать клетки bi и aj.

На этом заканчивается один шаг (итерация) метода.

Из оставшихся свободных рабочих клеток снова выбрать клетку с наилучшей ценой и повторять до тех пор, пока полностью не будет распределен весь груз.

Заполнение рабочей таблицы методом наилучших цен

	1	2	3	4	bi
1	13 300	12 1200	15	16	1500
2	17	15	14	131000	1000
3	15 500	14	13 1400	16 100	2000
aj	800	1200	1400	1100	4500



Zmin = 300*13 + 1200*12 + 1000*13 + 500*15 + 1400*13 + 100*16 = 58600.

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

Метод аппроксимации

Данный метод, также как и предыдущий, использует понятие «наилучшая цена», но в отличие от него позволяет более однозначно сделать выбор между равнозначными клетками при распределении груза.

Алгоритм метода аппроксимации:

1) в рабочей таблице задачи берем дополнительную строку и столбец «разностей»;

2) заполняем эти строку и столбец разностями между двумя наилучшими ценами по каждой строке и каждому столбцу;

3) из всех разностей строки и столбца выбрать наибольшую, указать номер итерации;

4) в соответствующей строке или столбце выбираем клетку с наилучшей ценой, проставляем в эту клетку максимальное значение xij;

5) корректируем свободные члены и вычеркиваем нерабочие свободные клетки;

6) из оставшихся неиспользованных разностей снова выбрать наибольшую и так до тех пор, пока или не будут использованы все разности или не будет распределен весь груз.

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

Заполнение рабочей таблицы методом аппроксимации

	1	2	3	4	bi	Столбец разностей
1	13 300	12 1200	15	16	1500	1
2	17	15	14	13 1000	1000	1
3	15 500	14	13 1400	16 100	2000	1
aj	800	1200	1400	1100	4500
Строка разностей	23	22	1	31

Zmin = 300*13 + 1200*12 + 1000*13 + 500*15 + 1400*13 + 100*16 = 58600.

Разность 31 означает, что заполнение таблицы начинать следует с клетки (2,4) (столбец выбран с учетом наибольшей разности, клетка в этом столбце выбрана с наименьшей ценой, так как Z>min).

При заполнении таблицы следует помнить, что:

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

2) если в строке и столбце окажется несколько одинаковых разностей, то предпочтение надо отдать той, которая будет иметь «оптимальный элемент». «Оптимальный элемент» - это цена, которая является наилучшей, как по строке, так и по столбцу, на пересечении которых она стоит. Исследование на наличие «оптимального элемента» проводить после каждой итерации;

3) если оптимальный элемент имеется у нескольких одинаковых разностей, то предпочтение отдать тому «оптимальному элементу», который будет иметь наибольшую сумму «разностей» по строке и столбцу, на пересечении которых он стоит. Если и сумма окажется одинаковой, то заполнять можно клетку с любым «оптимальным элементом»;

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

Замечание. В качестве недостатка этого метода можно отметить необходимость в знании всех его особенностей, а также некоторую громоздкость таблиц.

Размещено на Allbest.ru

...