lopt8 (1013502)

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла

Лекция 88. ТРАНСПОРТНЫЕ ЗАДАЧИПОСТАНОВКА ЗАДАЧИПредположим, что в пунктах A1 , A2 ,..., Am хранится однородный груз в количествеa1 , a2 ,..., am единиц. Этот груз следует доставить в n заданных пунктов назначенияB1 , B 2 ,..., B n , причем в каждый из них требуется завезти соответственно b1 , b2 ,..., bn единиц этого груза. Обозначим через cij стоимость перевозки единицы груза из пункта Aiв пункт B j .Транспортные задачи делятся на две группы.1. Задачи, удовлетворяющие условию балансаmni =1j =1∑ ai = ∑ b j ,означающему, что общий запас груза на всех пунктах хранения равен суммарной потребности всех пунктов назначения.2.

Задачи с нарушенным балансом, среди которых выделяются два случая:a)б)mni =1j =1mn∑ ai > ∑ b j (суммарные запасы больше суммарных потребностей);∑ ai <i =1∑bj(суммарные запасы меньше суммарных потребностей).j =1Рассмотрим формализацию транспортной задачи, удовлетворяющей условию баланса.Обозначим x ij – количество груза, перевозимого из пункта Ai в пункт B j . Тогдасуммарная стоимость перевозок имеет видf (x ) =mn∑ ∑ ci j ⋅ x i j .i = 1 j =1Ограничения представляются уравнениями вывоза и привоза груза:x i1 + x i 2 + ... + x in = ai ,x1 j + x 2 j + ... + x m j = b j ,x i j ≥ 0 , i = 1,2,..., m ;i = 1,2,..., m ;j = 1,2,..., n ;j = 1,2,..., n .Первое уравнение означает, что из каждого пункта хранения Ai вывозится весьгруз, а второе уравнение описывает факт удовлетворения всех потребностей в пункте B j .Условие неотрицательности свидетельствует о том, что груз либо вывозится из пункта Aiв пункт B j , и тогда x i j > 0 , либо нет, и в этом случае x i j = 0 .64Решение xi j , i = 1,2,..., m ; j = 1,2,..., n , системы называется планом перевозок.Требуется найти такой план перевозок, чтобы их суммарная стоимость была минимальной, т.е.f (x ) =mn∑ ∑ ci j ⋅ x i j→ min .i = 1 j =1Условия задачи удобно записывать в виде матрицы перевозок (табл.

1).Таблица 1ПунктыА1А2B2B1Bj...Bn...c11c12c1 jc1nа1c21c22c2 jc2 nа2#Аi#ci 1ci jci 2cinai#AmПотребностиЗапасы#cm1cm 2b1cm jb2cmnbj......ambnСуммаЗаметим, что с помощью линейных преобразований можно показать зависимостьодного из уравнений в системе от остальных, т.е. в этой системе имеется (m + n − 1) независимых уравнений. Лишнее уравнение может быть исключено из системы уравненийограничений.В матрице перевозок хранится текущий план перевозок x i j , i = 1,2,..., m ;j = 1,2,..., n .Стратегия решения задачиТак как поставленная задача является частным случаем задачи линейного программирования, то стратегия решения аналогична:1) находится начальный план перевозок;2) производится улучшение начального плана, т.е. последовательный переход отодного плана к другому, связанный с уменьшением суммарной стоимости перевозок.Процесс перехода от одного плана к другому завершается, когда уменьшение суммарнойстоимости перевозок станет невозможным.65МЕТОДЫ НАХОЖДЕНИЯ НАЧАЛЬНОГО ПЛАНА ПЕРЕВОЗОККлетки матрицы перевозок, где x ij > 0 , называются базисными, а остальные, гдеx i j = 0 , – свободными.

В матрице имеется (m + n − 1) базисных клеток. Их число совпа-дает с числом независимых уравнений-ограничений.Значение x ij в матрице перевозок находится по формуле⎧ остаток груза в пункте Ai ,x i j = min ⎨⎩ неудовлетворенные потребности в пункте B j .(*)Значение x i j = 0 в свободной клетке не пишется явно, а вместо этого в ней ставится точка.А.

Метод северо-западного углаВычисления осуществляются по формуле (*), начиная с элемента x11 , стоящего всеверо-западном углу матрицы перевозок.Пример 1. Найти начальный план перевозок в транспортной задаче, заданной матрицей перевозок (табл. 2).Таблица 2ЗапасыПунктыB1B2B323420A11010•12540A2•1030Потребности10203060† Начнем с северо-западного угла, т.е. x11 = min [ 20, 10 ] = 10 .

Тогда в пункте B1потребности удовлетворены и, следовательно, x 21 = 0 (в табл. 2 ставится точка). Первыйстолбец выбывает из рассмотрения.Продолжим с северо-западного угла, т.е. x12 = min [ (20 − 10), 20 ] = min[10, 20] = 10 .Тогда запасы в пункте A1 исчерпаны и x13 = 0 (в табл. 2 ставится точка). При этом первая строка выбывает из рассмотрения.Продолжим с северо-западного угла:x 22 = min [ 40, (20 − 10) ] = min [ 40, 10 ] = 10 .Потребности в пункте B 2 удовлетворены, и второй столбец выбывает из рассмотрения.x 23Заполним последний элемент, находящийся в северо-западном углу:= min [ (40 − 10), 30 ] = 30 . Таким образом, получен начальный план перевозок:x11 = 10,x12 = 10,x13 = 0 ,x 21 = 0,x 22 = 10,x 23 = 30с суммарной стоимостью f = 2 ⋅ 10 + 3 ⋅ 10 + 4 ⋅ 0 + 1 ⋅ 0 + 2 ⋅ 10 + 5 ⋅ 30 = 220 .

Число базисных клеток, очевидно, составит m + n − 1 = 2 + 3 − 1 = 4 .„66З а м е ч а н и е. При нахождении начального плана перевозок возможен случайвырождения, когда в результате вычислений значения x i j получается, что потребности впункте B j удовлетворены, а запасы в пункте Ai исчерпаны. Тогда одновременно из рассмотрения выбывают строка и столбец. В этом случае рекомендуется поставить в одну изклеток выбывающих строки и столбца (лучше в клетку с наименьшей стоимостью) такназываемый базисный нуль. Клетка с базисным нулем считается базисной (в ней пишется0 ), а общее число базисных клеток остается равным (m + n − 1) .Пример 2. Методом северо-западного угла найти начальный план перевозок втранспортной задаче, заданной матрицей перевозок (табл.

3).ПунктыB1A11A24A31Потребности30••30B2212B33200•2015Таблица 3Запасы504060150B4•5•4010502•105050□ Начнем заполнение таблицы с северо-западного угла:x11 = min [ 50, 30 ] = 30 ;x 21 = x 31 = 0 (ставится точка).Далее снова продолжим с северо-западного угла:x12 = min [ (50 − 30), 20 ] = min [ 20, 20 ] = 20 (это случай вырождения, так как выбываютпервая строка и второй столбец: x13 = x14 = x 22 = x 32 = 0 .Базисный нуль поставим в клетку (2,2) с наименьшей стоимостью, равнойmin [ 3; 5; 1; 2 ] = 1 .

В остальных выбывающих клетках ставятся точки.Продолжим с северо-западного угла:x 23 = min [ 40, 50 ] = 40 ; x 24 = 0 (ставится точка).Из рассмотрения выбывает вторая строка.Продолжим с северо-западного угла:x 33 = min [ 60, (50 − 40) ] = 10 иx 34 = min [ (60 − 10), 50 ] = 50 .Таким образом, получен начальный план перевозокx11 = 30,x12 = 20,x13 = x14 = 0 ,x 21 = x 22 = 0,x 23 = 40,x 24 = 0 ,x 31 = x 32 = 0,x 33 = 10,x 34 = 50с суммарной стоимостьюf = 30 + 40 + 40 + 50 + 500 = 660 .Число базисных клетокm + n − 1 = 3 + 4 − 1 = 6 .„сучетом67базисногонуля,очевидно,составитПример 3. Методом северо-западного угла найти начальный план перевозок втранспортной задаче, заданной матрицей перевозок (табл.

4).ПунктыB1A13A22A33A42B240•••40ПотребностиB3B44•5•1530••30610••1011325B5010••10361•10501060410Таблица 4Запасы40505010150† Решим аналогично примеру 2:а) x11 = min [ 40, 40 ] = 40 (случай вырождения);x12 = x13 = x14 = x15 = x 21 = x 31 = x 41 = 0 (базисный нуль ставится в клетку(1,4) с наименьшей стоимостью, а в остальные ставятся точки);б) x 22 = min [ 50, 30 ] = 30 , x 32 = x 42 = 0 (ставятся точки);в) x 23 = min [ (50 − 30), 10 ] = 10, x 33 = x 43 = 0 (ставятся точки);г) x 24 = min [ (50 − 30 − 10), 10 ] = min [ 10, 10 ] = 10 (случай вырождения);x 25 = 0 (ставится базисный нуль, так как это клетка с наименьшей стоимостью среди выбывающих клеток), x 34 = x 44 = 0 (ставятся точки);д) x 35 = min [ 50, 60 ] = 50 ;е) x 45 = min [ 10, (60 − 50) ] = 10 .Таким образом, начальный план перевозок содержит два базисных нуля, следовательно, число базисных клеток составит m + n − 1 = 4 + 5 − 1 = 8 .„Б.

Метод минимального элементаПолучаемый методом северо-западного угла начальный план перевозок не зависитот их стоимости и поэтому в общем случае далек от наилучшего. В методе минимальногоэлемента учитываются затраты на перевозку, следовательно, соответствующий начальный план, как правило, позволяет обеспечить меньшую суммарную стоимость, болееблизкую к оптимальной.В этом методе по формуле (*) последовательно заполняются клетки с наименьшейстоимостью перевозок. Если имеется несколько клеток с наименьшей стоимостью, то изних выбирается любая.Пример 4.

Найти начальный план перевозок в транспортной задаче, заданной матрицей перевозок (табл. 5).ПунктыA1A2ПотребностиB1B2B32•3•41101022020568201030Таблица 5Запасы204060† Заполним клетку с наименьшей стоимостью, равной 1:x 21 = min [ 40, 10 ] = 10 .Тогда потребности в пункте B1 удовлетворены и x11 = 0 (в табл. 5 ставится точка), первый столбец выбывает из рассмотрения.Из оставшихся клеток найдем клетку с наименьшей стоимостью и заполним ее:x 22 = min [ (40 − 10),20 ] = 20 . Тогда x12 = 0 (в табл. 5 ставится точка), потребности впункте B 2 удовлетворены и выбывает второй столбец.Из оставшихся двух клеток заполним клетку с наименьшей стоимостью:x13 = min [ 20, 30 ] = 20 .

Тогда первая строка выбывает (запасы в пункте A1 исчерпаны)и x 23 = min [ (40 − 30), (30 − 20) ] = 10 .Таким образом, получен начальный план перевозокx11 = 0,x12 = 0,x13 = 20 ,x 21 = 10,x 22 = 20,x 23 = 10с суммарной стоимостьюf = 2 ⋅ 0 + 3 ⋅ 0 + 4 ⋅ 20 + 1 ⋅ 10 + 2 ⋅ 20 + 5 ⋅ 10 = 180 .Заметим, что она меньше полученной с помощью метода северо-западного угла(см. пример 1). Число базисных клеток, очевидно, составляет m + n − 1 = 2 + 3 − 1 = 4 .

„МЕТОД ПОТЕНЦИАЛОВМетод обеспечивает улучшение начального плана перевозок. При этом происходитпереход от одного плана перевозок к другому (от одной матрицы перевозок к другой) дотех пор, пока уменьшение суммарной стоимости перевозок станет невозможным.Введем следующие понятия.1. Цикл – замкнутая ломаная с вершинами в клетках и звеньями, расположеннымивдоль строк и столбцов матрицы перевозок. В каждой вершине встречаются два звена,причем одно из них располагается по строке, а другое – по столбцу.

Число вершин циклачетно. Циклом может быть самопересекающаяся ломаная, но точки ее самопересеченияне могут быть вершинами цикла.2. Означенный цикл – цикл, в котором некоторой вершине приписан знак «+», а затем при обходе цикла в каком-либо направлении знаки чередуются.3. Сдвиг по циклу на число θ ≥ 0 . При этом значения x i j , стоящие в положительных вершинах цикла, увеличиваются на число θ , а стоящие в отрицательных вершинах,уменьшаются на число θ .4. Потенциалы – числа α i , i = 1,2,..., m; β j , j = 1,2,..., n . Каждому пункту храненияAi ставится в соответствие число α i , пункту потребления B j – число β j .69АлгоритмШаг 1. Найти начальный план перевозок методом северо-западного угла или методом минимального элемента.Шаг 2.

Для каждой базисной клетки составить уравнениеα i + β j = ci j .Так как эти уравнения образуют систему (m + n − 1) уравнений с (m + n) неизвестными(она имеет бесконечное множество решений), то для определенности следует положитьα1 = 0 . Тогда все остальные потенциалы находятся однозначно.Шаг 3. Для каждой свободной клетки вычислить относительные оценки:Δ i j = ci j − (α i + β j ) .Шаг 4. Проанализировать относительные оценки:а) если все относительные оценки неотрицательные, т.е. выполняется условиеΔi j ≥ 0 ,то задача решена, и следует выписать полученный оптимальный план перевозокиз последней матрицы, подсчитать его стоимость;б) если среди оценок Δ i j есть отрицательные, найти среди них наименьшую отрицательную оценку и пометить знаком ⊗ .Шаг 5.

Характеристики

Тип файла PDF

PDF-формат наиболее широко используется для просмотра любого типа файлов на любом устройстве. В него можно сохранить документ, таблицы, презентацию, текст, чертежи, вычисления, графики и всё остальное, что можно показать на экране любого устройства. Именно его лучше всего использовать для печати.

Например, если Вам нужно распечатать чертёж из автокада, Вы сохраните чертёж на флешку, но будет ли автокад в пункте печати? А если будет, то нужная версия с нужными библиотеками? Именно для этого и нужен формат PDF - в нём точно будет показано верно вне зависимости от того, в какой программе создали PDF-файл и есть ли нужная программа для его просмотра.

Список файлов лекций