Решебник_МО

В столбце x3 коэффициент а73 = 0, следовательно, продвижение вдоль этой оси нецелесообразно. В столбце x5 коэффициент а75 = 0, следовательно, продвижение вдоль этой оси нецелесообразно. Для оси

x6: x6A = 8 и x6B = 9. Для оси х1 x1A x1B , следовательно отрезок [ x1A , x1B ] не принадлежит многограннику допустимой области решений, на оси x1 нет ни одной его вершины. Для оси х6 x6A x6B , следовательно,

отрезок [ x6A , x6B ] является ребром первого ранга многогранника, а

точки x6A и x6B его вершинами.

Для нахождения опорного решения сделаем шаг замены переменной с разрешающим элементом а96=2, и получим таблицу:

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

Определим оптимальное решение. В Z-строке полученной матрицы четыре положительных элемента, следовательно, значение

отрицательные элементы отсутствуют, следовательно наша задача не ограничена.

Построим двойственную задачу. В связи с наличием в задаче параметрических ограничений, транспонируем каноническую матрицу исходной задачи:

131

Сформулируем двойственную задачу:

W= 8у1+18у2 16у34 min, у1+3у2+у3+1 ≤ 0, у2–1≤0, –43у2+2у3+1 ≤ 0, у1+1 ≤ 0, у3+1 ≤ 0, 6у1+2у2+2у3–1 ≤ 0, у1 ≥ 0, у2 ≥ 0, у3 ≥ 0.

Система ограничений двойственной задачи противоречива: у1+1≤ 0 и у1 ≥ 0. Это объясняется тем, что прямая задача не ограничена.

ТРАНСПОРТНАЯ ЗАДАЧА

В общем виде транспортную задачу (ТЗ) можно представить так: требуется найти такой план доставки грузов от поставщиков к потребителям, чтобы стоимость перевозки (или суммарная дальность, или объем транспортной работы в тонно-километрах) была наименьшей. В простейшем виде, когда распределяется один вид продукта и потребителям безразлично, от кого из поставщиков его

получать, задача формулируется следующим образом.

Пусть в пунктах А1,..., Am производят некоторый однородный продукт, причем объем производства в пункте Ai составляет ai единиц, i=1,..., m. Допустим, что данный продукт потребляют в пунктах B1,.., Bn, a объем потребления в пункте Вj составляет bj единиц j=1,…, n. Предположим, что из каждого пункта производства возможно транспортировка продукта в любой пункт потребления. Транспортные издержки по перевозке единицы продукции из пункта Ai в пункт Вj равны ci j (i=1,…, m; j=1,…, n ). Транспортная задача (ТЗ) состоит в определении такого плана перевозок, при котором:

a)полностью удовлетворен спрос потребителей в грузе,

b)все товары поставщиков будут вывезены из пунктов отправления,

c)суммарные транспортные издержки будут минимальны.

132

Условия ТЗ наглядно можно представить табл. 13, называемой

распределительной (табличной или матричной моделью).

Таблица 13

Классическая формулировка транспортной задачи следующая, Пусть xi j – количество продукта, перевозимого из пункта Ai в пункт Вj, Требуется определить множество переменных xi j 0, i=1,…, m, j=1,…, n, удовлетворяющих условиям:

значение.

Таким образом, транспортная задача представляет собой ЗЛП с m*n числом переменных, и (m+n) числом ограничений равенств.

что все xi j ≥ 0.

Удельные транспортные издержки (расходы) записываются в

133

доставляющий функции цели оптимальное (min) значение, называют

оптимальным.

Условие (9) называется условием баланса. ТЗ, в которой выполняется условие баланса, называется закрытой (сбалансированной), а если оно не выполняется – открытой (несбалансированной). В последнем случае ТЗ нужно преобразовать в закрытую путем введения либо фиктивного (n+1)-го пункта назначения Вn+1, либо фиктивного (m+1) поставщика An+1. В обоих случаях транспортные расходы сi, n+1 = 0 и сm+1, j = 0. Добавление фиктивной строки или фиктивного столбца не влияет на разрешимость ТЗ, так как ранг матрицы А транспортной задачи на единицу меньше числа уравнений: r(A) = m+n–1.

Если в плане перевозок переменная хi j равна некоторому числу а ≠ 0, то это число записывают в соответствующую клетку (i, j) и считают клетку занятой (или базисной), если же хi j=0, то клетка (i, j) остается свободной. При этом число занятых опорным планом клеток в соответствии с теоремой о ранге матрицы должно быть равно (m+n–1), а остальные (mn–(m+n–1)) клеток будут свободными.

ПОСТРОЕНИЯ ДОПУСТИМОГО ПЛАНА ТЗ

Метод северо-западного угла. Распределять груз начинают с загрузки верхней левой (условно называемой северо-западной) клетки (1,1), двигаясь затем от нее по строке вправо или по столбцу вниз.

В клетку (1,1) заносят меньшее из чисел а1 или в1, т.е.

х11=min(а1, в1). Если а1 > в1, то х11 = в1 и 1-й потребитель В1 будет полностью удовлетворен. В дальнейшем 1-й столбец в расчет не

принимается и в нем хi1 = 0, i=(2,…, m). Двигаясь вправо по 1-й строке, заносим в соседнюю клетку меньшее из чисел {(а1–в1), в2}, т.е. х12=min{(а1–в1), в2}. Если (а1–в1) < в2, то запасы 1-го поставщика исчерпаны, и 1-я строка в дальнейшем в расчет не принимается (т.е. х1j = 0, j = 3,…, n). Переходим к аналогичному распределению груза 2-го поставщика.

Если а1 < в1, то х11 = min(а1, в1) = а1. При этом запас 1-го поставщика будет исчерпан, а поэтому х1j = 0, j = 2,…, n. Первая строка

из дальнейшего рассмотрения исключается. Переходим к распределению запасов 2-го поставщика. В клетку (2,1) заносим

134

х21 = min{а2, (в1–а1)}. Заполнив таким образом клетку (1,2) или (2,1) переходим к загрузке следующей свободной северо-западной клетки. Процесс распределения продолжается аналогично, пока не исчерпаются все ресурсы и не будут удовлетворены все потребители. Последней заполняется клетка (m, n).

Метод минимального элемента. Просматриваются тарифы перевозок, т.е. ci j в распределительной матрице, и в первую очередь заполняется клетка с минимальным тарифом. При этом в клетку записывается максимально возможное значение поставки. Затем из рассмотрения исключают строку, соответствующую поставщику, запасы которого полностью израсходованы, или столбец, соответствующий потребителю, спрос которого полностью удовлетворен. После этого из оставшихся свободных клеток таблицы выбирают клетку с минимальным тарифом. Процесс распределения заканчивается, когда все запасы поставщиков исчерпаны, а спрос потребителей полностью удовлетворен. В результате получим план, который должен содержать (m +n –1) загруженных клеток. В процессе заполнения таблицы могут быть одновременно исключены из дальнейшего рассмотрения строка и столбец. Так бывает, когда одновременно полностью исчерпывается запас груза и полностью удовлетворяется спрос. В этом случаев в одну из свободных (исключаемые из рассмотрения) клеток строки (столбца) записывают число 0 – «нуль загрузки», условно считая такую клетку занятой.

В основе метода аппроксимации Фогеля лежит концепция штрафов, взимаемых за выбор не самого оптимального (выгодного) маршрута перевозок. Алгоритм метода состоит из следующих шагов.

1.В каждой строке и в каждом столбце матрицы вычисляется разность между наименьшим и ближайшим к нему по величине тарифами (штраф).

2.Выбирается максимальная из всех разностей (штрафов).

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

135

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

ПОСТРОЕНИЯ ОПТИМАЛЬНОГО ПЛАНА ТЗ

Метод потенциалов. Каждому поставщику (ограничению по запасам) ставят в соответствие потенциал ui (i=1,…, m), а каждому потребителю (ограничению по спросу) – потенциал νj (j=1,…, n).

Каждой занятой клетке таблицы допустимого плана ТЗ будет соответствовать уравнение: ui+νj=сi j. Так как занятых клеток (m+n–1), т.е. на одну меньше числа потенциалов, то для определения чисел ui и νj необходимо решить систему из (m+n–1) уравнений ui+νj = сi j с (m+n) неизвестными. Эта система неопределенная, и, чтобы найти частное решение, одному из потенциалов присваивают произвольное числовое значение (для облегчения расчетов одному из потенциалов, как правило, встречающемуся в системе уравнений наиболее часто, присваивают значение 0).

Для исследования плана на оптимальность для каждой свободной клетки проверяют условие ui+νj ≤ сi j. Если хотя бы одна из клеток не удовлетворяет этому условию, то опорный план не является оптимальным и его можно улучшить за счет этой клетки. Если таких клеток несколько, то наиболее перспективной для загрузки является клетка, для которой разность (оценка) между тарифом клетки и суммой потенциалов наименьшая, т.е. sij = min(сij–(ui+νj) < 0). Экономически эта оценка показывает, на сколько единиц уменьшатся транспортные издержки от загрузки перспективной клетки единицей груза. Эффективность плана от загрузки перспективной клетки грузом в К единиц составит f = si j*K ед.

Если для всех свободных клеток оценки sij ≥ 0, то опорный план перевозок является оптимальным.

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

136

под прямым углом. Каждое звено соединяет две клетки строки или столбца распределительной матрицы. Цикл содержит одну свободную клетку а (перспективную), а остальные клетки цикла – занятые. В цикле всегда четное число клеток. Для свободной клетки всегда можно построить единственный цикл.

Вершинам этого цикла условно присваиваются знаки: свободной клетке «+», следующей занятой клетке «–», следующей – «+» и т.д. Из поставок в клетках со знаком «–» выбирают наименьшее количество груза К, которое и перемещается по клеткам цикла. Эту величину прибавляют к поставкам клеток со знаком «+» и вычитают из поставок клеток со знаком «–», в результате чего баланс цикла не нарушится (рис. 13).

AлгоритмРис. 13решения. ПерераспределениеТЗ м тодом потенциаловперевозок в, ТЗ

Алгоритм метода потенциалов состоит из следующих шагов:

1.Строится опорный план одним из методов.

2.Вычисляются потенциалы поставщиков ui и потребителей νj (i=1,…, m, j=1,…, n), решается система уравнений вида ui+νj = сij.

3.Вычисляются оценки sij для всех свободных клеток по формуле sij = сij-(ui+νj). Если все sij ≥ 0, то план оптимален. Если все sij > 0, то план единственный. Если существует хотя бы одна sij = 0, то имеется множество оптимальных планов с одним и тем же значением функции цели. Если план не оптимальный, выполняют загрузку перспективной клетки с помощью построения цикла и переходят к п. 2.

Пример 36. Необходимо составить план перевозок зерна из районов А1, А2, А3 и А4, в которых запасы составляют соответственно 800, 700, 1000 и 500 тыс. центнеров. Затраты на перевозку 1 тыс. ц зерна из района на элеваторы равны соответственно:

137

с11=3, с12=5, с13=6, с21=7, с22=2, с23=4, с31=4, с32=3, с33=5, с41=6, с42=4, с43=7.

Решение. Проверим условие баланса.

Составим распределительную матрицу.

Построим допустимый план методом северо-западного угла.

Недостающее зерно для элеватора В1 будет поставлено из района А2: в клетку (2,1) помещаем х21 = min(700, 1000–800) = 200. В этом случае мощность элеватора В1 будет полностью использована, т.е. хi1=0 при i = 3,4. Остаток зерна из р-на А2 будет отправлен на элеватор В2: в клетку (2,2) помещаем х22 = min(1100, 700–200)=500. Запас зерна в районе А2 исчерпан, т.е. х23 = 0. Переходим к перевозке зерна из района А3: в клетку (3,2) помещаем х32 = min(100, 1100–500) = 600, элеватор В2

завершена. Начнем отгрузку из р-на А3: х43 = min(500, 900–400) = 500. В результате полной отгрузки зерна получен план перевозок ХСЗ, представленный в табл.14.

138

Суммарные затраты на перевозку зерна составляют:

Z(ХСЗ) = 3*800+7*200+2*500+3*600+5*400+7*500 = 12100 усл. ед.

Построим допустимый план методом минимального элемента. Минимальные затраты на перевозку зерна соответствуют маршруту А2–В2, поэтому в клетку (2,2) помещаем х22 = min(ai, b2) = 700. В дальнейшем вторая строка из рассмотрения исключается, так как запас зерна в районе А2 исчерпан. В остальных незаполненных клетках минимальный тариф соответствует c11= c32 =3. В клетку (1,1) помещаем

х11 = min(a1, b1)=800, а в клетку (3,2) – х32 = min(a3, b2–х22) = min(1000, 400) = 400. Далее, согласно величине тарифа, следует заполнять клетку

(3,1): х31 = min (1000–400, 1000–800) = 200; клетку (3,3): х33 = min(1000– 200–400, 900) = 400; последняя клетка (4,3): х43 = 500. В результате получаем план ХМЭ, представленный в табл.15.

Суммарные затраты на перевозку зерна составляют: Z(XМЭ)=3*800+2*700+4*200+3*400+5*400+7*500=11300 усл.ед.

Построим допустимый план методом Фогеля. Вычислим «штраф» для поставщика А1: наименьший тариф с11 = 3, ближайший к нему тариф с12 = 5, следовательно, штраф равен 2. Поступая таким же образом со всеми строками и столбцами матрицы, получим для первого этапа максимальный штраф у поставщиков А1, А2, А4. Выбираем поставщика А1 и заполняем в его строке клетку с минимальным тарифом: х11 = min(a1, b1)=800. Отгрузка зерна из А3 полностью завершена, оставшиеся свободные клетки первой строки из

139

дальнейшего рассмотрения исключаются. Вычисление штрафов второго этапа позволило определить х22 = min(a2, b2) = 700, третьего –

х42 = min (a4, b2–700) = 400, четвертого – х31 = min(a3, b1–800) = 200,

пятого – х33 = min(a3–200, b3) = 800, последним определили х43 = 100. В результате полной отгрузки зерна получен план перевозок Xф, представленный в табл. 16.

Таблица 16

Суммарные затраты на перевозку зерна составляют:

Z(Xф) = 3*800+2*700+4*200+5*800+4*400+7*100 = 10900 усл. ед.

Это лучший результат. С помощью метода потенциалов проверим, является ли он оптимальным.

1. Для «занятых» клеток построенной таблицы составим систему

u1 = 3, u3 = 4, v3 = 1, u4 = 6, v2 = –2, u2 = 4.

2.Вычислим оценки sij=сij–(ui+νj) для всех свободных клеток: s12 = 5–(3+(–2)) = 4, s13 = 6–(3+1) = 2, s21 = 7–(4+0) = 3,

s23 = 4–(4+1) = –1, s32 = 3–(4+(–2)) = 1, s41 = 6–(6+0) = 0.

План не оптимален, так как s23 = –1< 0.

140