Учебнометодическое пособие по разделу транспортная задача
 Скачать 0.51 Mb.
|
|
Сайт www.resolventa.ru , E-mail: Сайт www.resolventa.ru , E-mail: Доктор физико-математических наук, профессор КЛ. САМАРОВ МАТЕМАТИКА Учебно-методическое пособие по разделу ТРАНСПОРТНАЯ ЗАДАЧА © КЛ. Самаров, 2009 Сайт www.resolventa.ru , E-mail: Сайт www.resolventa.ru , E-mail: resolventa@list.ru 2 СОДЕРЖАНИЕ ТРАНСПОРТНАЯ ЗАДАЧА 1. Постановка транспортной задачи. Транспортная таблица 2. Сведение открытой транспортной задачи к закрытой 3. Первоначальный план перевозок 3.1. Составление первоначального плана перевозок с помощью метода северо-западного угла 3.2. Составление первоначального плана перевозок с помощью метода наименьшей стоимости 4. Вырожденные планы. Циклы и пополнение плана 5. Проверка оптимальности плана и перераспределение поставок с помощью метода потенциалов 5.1. Вычисление потенциалов 5.2. Проверка оптимальности плана 5.5. Перераспределение поставок 6. Пример решения типовой транспортной задачи ВОПРОСЫ ДЛЯ САМОКОНТРОЛЯ ЗАДАНИЯ ДЛЯ САМОСТОЯТЕЛЬНОЙ РАБОТЫ ЛИТЕРАТУРА Сайт www.resolventa.ru , E-mail: Сайт www.resolventa.ru , E-mail: resolventa@list.ru 3 ТРАНСПОРТНАЯ ЗАДАЧА 1. Постановка транспортной задачи. Транспортная таблица Рассмотрим следующую задачу, называемую транспортной задачей. Имеется m поставщиков m A A A ,..., , 2 1 , у которых сосредоточены запасы одного итого же груза в количестве m a a a ,..., , 2 1 единиц, соответственно. Этот груз нужно доставить n потребителям n B B B ,..., , 2 1 , заказавшим n b b b ,..., , 2 единиц этого груза, соответственно. Известны также все тарифы перевозок груза ij c (стоимость перевозок единицы груза) от поставщика i A к потребителю. Требуется составить такой план перевозок, при котором общая стоимость всех перевозок была бы минимальной. Условие транспортной задачи удобно записать в виде следующей Транспортной таблицы 1.1. Таблица заказы запасы 1 B 2 B … n B 1 b 2 b … n b 1 A 1 a 11 c 12 c … n c 1 2 A 2 a 21 c 22 c … n c 2 … … … … … … m A m a 1 m c 2 m c … Обозначим суммарный запас груза у всех поставщиков символом a , а суммарную потребность в грузе у всех потребителей – символом Тогда Сайт www.resolventa.ru , E-mail: Сайт www.resolventa.ru , E-mail: resolventa@list.ru 4 = = m i i a a 1 , = = n j j b b 1 • Транспортная задача называется закрытой, если b a = . Если же b a , то транспортная задача называется открытой. Далее будет показано, что в случае закрытой задачи от поставщиков будут вывезены все запасы груза, и все заявки потребителей будут удовлетворены. В случае открытой задачи привесь груз будет вывезен, однако будут недопоставки груза экономически невыгодным потребителям. При b a , наоборот, будут удовлетворены все потребители, но часть груза останется на складах экономически невыгодных поставщиков. • Пусть ( ) 0 ij ij x x – количество груза, отправляемого поставщиком потребителю j B . Тогда суммарные затраты на перевозки будут вычисляться по формуле = = = m i n j ij ij x c z 1 1 • Матрица X с неотрицательными элементами ij x называется планом перевозок. • Функция называется целевой функцией. Математическая формулировка транспортной задачи заключается в нахождении плана перевозок ij X x = , который удовлетворяет системе ограничений (1.1) и доставляет минимум целевой функции z • План перевозок, реализующий минимум целевой функции z , называется оптимальным. 1 1 , , 1,2,..., , 1,2,..., , n j m i ij i ij j x a i m x b j n = = = = = = Сайт www.resolventa.ru , E-mail: Сайт www.resolventa.ru , E-mail: resolventa@list.ru 5 Смысл первой группы равенств в системе ограничений (1.1) состоит в том, что суммарное количество груза, отправленное всем потребителям каждым поставщиком, равно запасу груза у этого поставщика. Вторая группа равенств в системе ограничений (1.1) показывает, что суммарное количество груза, полученное каждым потребителем от всех поставщиков, равно заказу этого потребителя. 4.2. Сведение открытой транспортной задачи к закрытой Решение транспортной задачи начинается с выяснения вопроса о том, является ли задача открытой или закрытой. Если задача является открытой, то необходимо провести процедуру закрытия задачи. С этой целью при b a добавляем фиктивного поставщика 1 ' + m A с запасом груза a b a m − = +1 ' . Если же b a , то добавляем фиктивного потребителя 1 ' + n B с заказом груза В обоих случаях соответствующие фиктивным объектам тарифы перевозок полагаем равными нулю. В результате суммарная стоимость перевозок не изменяется. 3. Первоначальный план перевозок Транспортная задача относится к задачам линейного программирования, и ее можно было бы решить симплекс-методом. Но поскольку система ограничений транспортной задачи проще, чем система ограничений ОЗЛП, то это дает возможность вместо использования объемных симплекс-таблиц применить более удобный метод, который состоит из следующих этапов 1. Составление первоначального плана перевозок 2. Последовательные улучшения плана перевозок (перераспределение поставок) до тех пор, пока план перевозок не станет оптимальным. Решение ОЗЛП начинается с нахождения опорного плана. Для транспортной задачи такой план всегда существует. Опишем два метода составления опорного плана (первоначального плана перевозок. При этом ненулевые Сайт www.resolventa.ru , E-mail: Сайт www.resolventa.ru , E-mail: resolventa@list.ru 6 элементы ij x плана перевозок будем записывать в соответствующие пустые клетки транспортной таблицы с исходными данными задачи, а символом ) , ( j i будем обозначать клетку таблицы, содержащую информацию опере- возках груза от поставщика i A к потребителю Составление первоначального плана перевозок с помощью метода северо-западного угла Составление первоначального плана перевозок начнем с перевозки запасов поставщика 1 A . Будем за счет его запасов максимально возможно удовлетворять заказы сначала потребителя 1 B , затем 2 B итак далее. Таким образом, мы будем заполнять таблицу, начиная с клетки (1,1), и двигаться вправо по строке до тех пор, пока остаток запасов поставщика 1 A не окажется меньше заказа очередного потребителя. Для выполнения этого заказа используем остатки запаса первого поставщика, а недостающую часть добавим из запасов поставщика 2 A , то есть переместимся наследующую строку таблицы по столбцу, соответствующему указанному потребителю. Далее аналогичным образом распределим запасы поставщика 2 A , затем 3 A итак далее. Проиллюстрируем это наследующем примере (Таблица 3.1). Таблица заказы запасы 1 B 2 B 3 B 4 B 100 40 80 60 1 A 160 4 8 10 5 100 40 20 2 A 30 4 6 2 3 30 3 A 90 4 4 6 5 30 60 Сайт www.resolventa.ru , E-mail: Сайт www.resolventa.ru , E-mail: resolventa@list.ru 7 Распределяя запасы поставщика 1 A сначала потребителю 1 B , а затем 2 B , получаем 100 11 = x , 40 12 = x . После этого у поставщика 1 A остается еще 20 единиц груза, а потребителю 3 B нужно 80 единиц. Удовлетворим спрос потребителя, отправив ему 20 единиц груза, оставшихся у поставщика 1 A , 30 единиц груза от поставщика 2 A и 30 единиц груза от 3 A . Следовательно, 13 20 x = , 23 30 x = и 33 30 x = , причем у поставщика 3 A остается 60 последних единиц груза. Этот грузи отправим потребителю 4 B . Таким образом 34 60 x = , все запасы груза вывезены и все потребители удовлетворены. Теперь мы можем подсчитать общую стоимость всех перевозок поданному плану 1460 60 5 30 6 30 2 20 10 40 8 100 Изложенный метод северо-западного угла прост в реализации, однако трудно надеяться, что он даст экономичный первоначальный план, поскольку при распределении перевозок мы совершенно не учитывали их стоимость. 3.2. Составление первоначального плана перевозок с помощью метода наименьшей стоимости Построение плана начнем с клетки с наименьшим тарифом перевозок. При наличии нескольких клеток с одинаковыми тарифами выберем любую из них. Пусть это будет клетка ) , ( j i . Запишем в эту клетку элемент ) , min( j i ij b a x = . Если j i b a , то запасы поставщика i A исчерпаны, а потребителю требуется еще i j j a b b − = ' единиц груза. Поэтому, не принимая более во внимание ю строку, снова ищем клетку с наименьшей стоимостью перевозок и заполняем ее с учетом изменившихся потребностей. В случае j i b a из рассмотрения исключается й столбец, а запасы i A полагаются равными j i i b a a − = ' . Продолжаем этот процесс до тех пор, пока все запасы не будут исчерпаны, а все потребности удовлетворены. Сайт www.resolventa.ru , E-mail: Сайт www.resolventa.ru , E-mail: resolventa@list.ru 8 Необходимо отметить, что при наличии в таблице клеток с одинаковыми тарифами, планы, полученные с помощью этого метода, могут быть разными, однако они, несомненно, ближе к оптимальному плану, чем план, составленный по методу северо-западного угла. Сформируем теперь первоначальный план по методу наименьшей стоимости для рассмотренного в параграфе 3.1 примера и сравним результаты Таблица 3.2). Поскольку наименьший тариф (число 2) стоит в клетке (2,3), то запишем в эту клетку элемент 30 23 = x . Тогда 50 ' 3 = b , а ю строку таблицы можно больше не учитывать. Среди оставшихся клеток имеются три клетки с наименьшим тарифом перевозок, равными. Выберем, например, клетку (1,1) и запишем в нее число 100 11 = x . Получаем, что 60 ' 1 = a , ай столбец таблицы больше не рассматриваем. Теперь наименьший тариф, равный 4, проставлен в клетке (3,2), поэтому 40 32 = x , 50 ' 3 = b и й столбец больше ненужен. Далее выбираем клетку (1,4) с тарифом 5 и пишем в нее 60 14 = x . Исключив из рассмотрения сразу ю строку и 4-ый столбец (поскольку 60 ' 4 1 = = b a ), переходим к последней клетке (3,3), в которую записываем перевозку 50 33 = x Таблица заказы запасы 1 B 2 B 3 B 4 B 100 40 80 60 1 A 160 4 8 10 5 100 60 2 A 30 4 6 2 3 30 3 A 90 4 4 6 5 40 50 Сайт www.resolventa.ru , E-mail: Сайт www.resolventa.ru , E-mail: resolventa@list.ru 9 Найдем суммарную стоимость перевозок поэтому плану 1220 50 6 40 4 30 2 60 5 100 Сравнивая это значение со стоимостью плана, полученного по методу северо-западного угла, видим, что 1220 < 1460, то есть мы получили более выгодный план перевозок. 4. Вырожденные планы. Циклы и пополнение плана Прежде, чем перейти к анализу оптимальности планов и способам их улучшения, выясним, каким требованиям должны удовлетворять составляемые планы. Для этого вернемся к системе ограничений (1). В соответствии с определением плана перевозок у матрицы ij X x = сумма элементов й строки равняется , 1,2,..., i a i m = , а сумма элементов о столбца равняется , 1,2,..., j b j n = . Условие закрытости транспортной задачи b a = означает, что среди n m + уравнений системы (1) независимыми являются только 1 − + уравнений, поэтому в любом базисном решении этой системы должно быть 1 − + n m базисных переменных. Поскольку свободные переменные в таком решении равны нулю, тов транспортной таблице им будут соответствовать пустые клетки. • Клетки таблицы, в которые записаны отличные от нуля перевозки, называются базисными, а остальные (пустые) - свободными. • План называется вырожденным, если количество базисных клеток в нем меньше, чем 1 − + Если на каком-то этапе решения получился вырожденный план, то его необходимо пополнить проставив в недостающем числе клеток нулевую перевозку и превратив, тем самым, эти клетки в базисные. Общий баланс и суммарная стоимость перевозок плана при этом не изменятся. Однако проводить пополнение плана, выбирая клетки произвольно, нельзя. Приведем условия, которым должен соответствовать пополненный план. Сайт www.resolventa.ru , E-mail: Сайт www.resolventa.ru , E-mail: resolventa@list.ru 10 • Циклом в транспортной таблице называется несколько клеток, соединенных замкнутой ломаной линией так, чтобы две соседние вершины ломаной были расположены либо водной строке, либо водном столбце. Ломаная линия может иметь точки самопересечения, ноне в клетках цикла. • План называется ациклическим, если его базисные клетки не содержат циклов. Доказано, что оптимальные планы являются ациклическими, поэтому и первоначальный план также должен удовлетворять этому требованию. Заметим, что планы, полученные с помощью метода северо-западного угла и метода наименьшей стоимости, ациклические. Однако если план оказался вырожденным, то при его пополнении требование ацикличности необходимо учитывать. Возвращаясь к рассматриваемому примеру, видим, что первоначальный план, полученный по методу наименьшей стоимости, имеет 5 базисных клеток, однако 6 1 4 3 1 = − + = − + n m . Значит, план нужно пополнить еще одной базисной клеткой. Попробуем выбрать для этого клетку (2,2). Соединив базисные клетки горизонтальными и вертикальными отрезками (рис. 1), получаем) рис.1 рис.2 Видим, что пополненный таким образом план содержит цикл из клеток (2,2); (2,3); (3,3) и (3,2), следовательно, клетка (2,2) была выбрана неудачно. Взяв вместо нее клетку (2,4), получим ациклический план (рис. 2). Поэтому можно заполнить эту клетку, положив 0 24 = x 5. Проверка оптимальности плана и перераспределение поставок с помощью метода потенциалов Сайт www.resolventa.ru , E-mail: Сайт www.resolventa.ru , E-mail: resolventa@list.ru 11 Для анализа полученных планов и их последующего улучшения удобно ввести дополнительные характеристики пунктов отправления и назначения, называемые потенциалами. 5.1. Вычисление потенциалов Сопоставим каждому поставщику i A и каждому потребителю j B величины и j v соответственно так, чтобы для всех базисных клеток плана были выполнены соотношения ij j i c v u = + , m i ,..., 2 , 1 = , n j ,..., 2 , 1 = . (2) Поскольку число базисных клеток в плане равно 1 − + n m (вырожденные планы должны быть предварительно пополнены, то для определения потенциалов получается система из 1 − + n m уравнений с n m + неизвестными. Такая система имеет бесконечное множество решений. Нам требуется любое ее решение. Обычно для простоты полагают один из потенциалов равным нулю и затем вычисляют остальные. В транспортной таблице для потенциалов заводится дополнительные строка, а для потенциалов n u u u ,..., , 2 1 – дополнительный столбец, куда проставляются найденные значения. Проверка оптимальности плана Для каждой свободной клетки плана вычислим разности ) ( j i ij ij v u c c + − = и запишем полученные значения в левых нижних углах соответствующих клеток. Заметим, что для базисных клеток выполнено соотношение, и этим фактом можно пользоваться для контроля правильности нахождения потенциалов. План является оптимальным, если все разности В противном случае план можно улучшить следующим способом. 5.3. Перераспределение поставок Сайт www.resolventa.ru , E-mail: Сайт www.resolventa.ru , E-mail: resolventa@list.ru 12 Найдем клетку с наибольшей по абсолютной величине отрицательной разностью ij c и построим цикл, в котором кроме этой клетки все остальные являются базисными. Такой цикл всегда существует и единственен. Заметим, что в новом плане суммы элементов по строками столбцам должны остаться прежними, поэтому изменение значения водной клетке цикла повлечет за собой соответствующие изменения значений во всех остальных клетках этого цикла. Так как в свободной клетке значение будет увеличено, то проставим в ее правом нижнем углу знак . Теперь пройдем по всей ломаной цикла, проставляя в правых нижних углах клеток поочередно знаки плюс в кружке и минус в кружке. Груз будет перераспределен по клеткам цикла на величину следующим образом. В клетках со знаком плюс значение перевозки нужно увеличить на величину x , а в клетках со знаком минус – уменьшить на величину x . Так как после пересчета у нас добавилась лишняя базисная клетка, то их количество необходимо сократить, убрав нуль водной из клеток цикла. Если таких клеток получилось несколько, то свободной делаем ту из них, в которой тариф перевозок максимален. После этого полученный план проверяется на оптимальность описанным выше способом. Перераспределение груза производится до тех пор, пока очередной план не станет оптимальным. На этом действие алгоритма завершается. Покажем, как нужно пользоваться методом потенциалов, на примере первоначального плана, полученного выше по методу северо-западного угла. Вначале проверим, не является ли этот план вырожденным. Так как 6 1 4 3 1 = − + = − + n m , и число базисных клеток в плане также равно 6, то план в пополнении не нуждается. Найдем потенциалы по базисным клеткам таблицы с помощью формул (7), положив 0 1 = u , Сайт www.resolventa.ru , E-mail: Сайт www.resolventa.ru , E-mail: resolventa@list.ru 13 = = + = + = + = + = + = + , 0 , 5 , 6 , 2 , 10 , 8 , 4 1 4 3 3 3 3 2 3 1 2 1 1 1 u v u v u v u v u v u v u = = = = − = − = = , 9 , 10 , 8 , 4 , 4 , 8 , 0 4 3 2 1 3 2 и занесем полученные значения в таблицу. Вычислим теперь разности для свободных клеток и также проставим эти данные в левых нижних углах соответствующих клеток. В итоге получим следующую таблицу 4. Таблица заказы запасы 40 80 60 u 1 A 160 4 8 10 5 100 40 20 – 4 0 2 A 30 4 6 2 3 8 6 30 2 – 8 3 A 90 4 4 6 5 4 0 30 60 – 4 v 4 8 10 9 Поскольку 0 4 14 − = c , то этот план не является оптимальным. Перераспределим груз по циклу, обозначенному в таблице 4 пунктиром, навели- чину 20 ) 60 , 20 min( = = x . Для этого в клетках со знаком плюс увеличим поставки на 20 единица клетках со знаком минус – поставки настолько же уменьшим. Для сохранения количества базисных клеток число 0 в клетке (1,3) не записываем, иона становится свободной. Сайт www.resolventa.ru , E-mail: Сайт www.resolventa.ru , E-mail: resolventa@list.ru 14 Вычислив потенциалы и разности ij c для нового плана, видим, что снова есть отрицательная разность 4 32 − = c . Поэтому придется еще раз улучшать план. С этой целью перераспределим груз по циклу, отмеченному в таблице 5 пунктиром, на величину 40 ) 40 , 40 min( = = x . Так как в результате в цикле получаются две клетки с нулевыми перевозками (1,3) и (3,4) , то сделаем свободной клетку (1,3), поскольку ее тариф перевозок больше. После перераспределения груза по циклу вычислим все необходимые разности Таблица заказы запасы 40 80 60 u 1 A 160 4 8 10 5 100 40 4 20 0 2 A 30 4 6 2 3 4 2 30 2 – 4 3 A 90 4 4 6 5 0 – 4 50 40 0 v 4 8 6 5 Как видим, все ij c неотрицательны, значит, план оптимален (таблица 6). Таблица заказы запасы 40 80 60 u 1 A 160 4 8 10 5 100 4 4 60 0 2 A 30 4 6 2 3 Сайт www.resolventa.ru , E-mail: Сайт www.resolventa.ru , E-mail: resolventa@list.ru 15 4 6 30 2 – 4 3 A 90 4 4 6 5 0 40 50 0 0 0 v 4 4 6 5 Сайт www.resolventa.ru , E-mail: Сайт www.resolventa.ru , E-mail: resolventa@list.ru 16 6. Пример решения типовой транспортной задачи Задача 6.1. На складах трех поставщиков 3 2 1 , , A A A хранится 300, 250 и 200 единиц одного итого же груза. Этот груз требуется доставить четырем потребителями, заказы которых составляют 220, 150, 250 и 180 единиц груза соответственно. Стоимости перевозок ij c единицы груза с го склада j -му потребителю указаны в правых верхних углах соответствующих клеток транспортной таблицы 7. Таблица заказы запасы 1 B 2 B 3 B 4 B 220 150 250 180 1 A 300 4 5 3 6 2 A 250 7 2 1 5 3 A 200 6 1 4 2 Составить такой план перевозок груза, при котором общая стоимость всех перевозок была бы минимальной. Решение. Поскольку суммарный запас груза а = 300 + 250 + 200 = 750 меньше суммарной потребности b = 220 + 150 + 250 + 180 = 800, то рассматриваемая транспортная задача является открытой. Сведем ее к закрытой, добавив фиктивного поставщика 4 ' A с нулевыми тарифами перевозок и запасом груза Составим первоначальный план перевозок с помощью метода наименьшей стоимости, заполняя клетки в следующем порядке (4,2) → (3,2) → (2,3) → (3,4) → (1,1) → (1,4). Получим таблицу 8. Сайт www.resolventa.ru , E-mail: Сайт www.resolventa.ru , E-mail: resolventa@list.ru 17 Таблица заказы запасы 1 B 2 B 3 B 4 B 220 150 250 180 1 A 300 4 5 3 6 220 80 2 A 250 7 2 1 5 250 3 A 200 6 1 4 2 100 100 4 ' A 50 0 0 0 0 50 Перейдем к анализу полученного плана. Заметим, что в этой задаче 7 1 4 4 1 = − + = − + n m , а число занятых клеток в имеющемся плане равно 6. Значит, необходимо пополнить план еще 1 клеткой, записав в ней 0 , так, чтобы пополненный план получился ациклическим. Выберем для этой цели, например, клетку (4,3). Вычислим потенциалы по базисным клеткам плана = = + = + = + = + = + = + = + , 0 , 0 , 0 , 2 , 1 , 1 , 6 , 4 1 3 4 2 4 4 3 2 3 3 2 4 1 1 1 u v u v u v u v u v u v u v u = = = = − = − = − = = , 6 , 5 , 5 , 4 , 5 , 4 , 4 , 0 4 3 2 1 4 3 и вычислим для свободных клеток разности Получим таблицу 9. Сайт www.resolventa.ru , E-mail: Сайт www.resolventa.ru , E-mail: resolventa@list.ru 18 Таблица потребности запасы 150 250 180 u 1 A 300 4 5 3 6 220 0 – 2 80 0 2 A 250 7 2 1 5 – 4 7 1 250 3 3 A 200 6 1 4 2 – 4 6 100 3 100 4 ' A 50 0 0 0 0 – 5 1 50 0 – 1 v 4 5 5 6 Поскольку среди чисел ij c есть отрицательные, то перераспределим грузна величину по циклу, обозначенному пунктиром. Клетка (1,3) станет базисной вместо клетки (4,3), и мы получим таблицу 10. План, указанный в таблице 10, не является оптимальным, поскольку 0 1 44 Улучшим этот план с помощью перераспределения поставок по циклу, обозначенному в таблице 10 пунктиром, на величину Получим таблицу 10. Сайт www.resolventa.ru , E-mail: Сайт www.resolventa.ru , E-mail: resolventa@list.ru 19 Таблица заказы запасы 150 250 180 u 1 A 300 4 5 3 6 220 0 0 80 0 2 A 250 7 2 1 5 – 2 5 – 1 250 1 3 A 200 6 1 4 2 – 4 6 100 5 100 4 ' A 50 0 0 0 0 – 5 1 50 2 – 1 v 4 5 3 6 В таблице 11 перераспределение осуществляется по ступенчатому циклу. Таблица заказы запасы 150 250 180 u 1 A 300 4 5 3 6 220 0 0 80 0 2 A 250 7 2 1 5 – 2 5 – 1 250 1 3 A 200 6 1 4 2 – 4 6 150 5 50 Сайт www.resolventa.ru , E-mail: Сайт www.resolventa.ru , E-mail: resolventa@list.ru 20 4 ' A 50 0 0 0 0 – 6 2 1 3 50 v 4 5 3 6 После еще одного перераспределения поставок на величину 80 = x , получим таблицу 12. Таблица заказы запасы 150 250 180 u 1 A 300 4 5 3 6 220 1 80 1 0 2 A 250 7 2 1 5 – 2 5 80 170 2 3 A 200 6 1 4 2 – 3 5 70 4 130 4 ' A 50 0 0 0 0 – 5 1 1 2 50 v 4 4 3 5 Заметим, что после каждого перераспределения груза производились вычисления потенциалов и разностей ij c для полученного плана, и эти данные проставлялись в таблицу. В таблице 12 все разности 0 ij c , следовательно, план оптимален. Таким образом, = 130 0 0 0 170 80 70 80 0 0 0 220 опт X Сайт www.resolventa.ru , E-mail: Сайт www.resolventa.ru , E-mail: resolventa@list.ru 21 Фиктивный груз 50 ' 4 = a в таблице означает, что потребителю 4 B будет недопоставлено 50 единиц груза. Найдем суммарную стоимость перевозок по оптимальному плану = = = + + + + + = = 3 1 4 1 min 1780 130 2 70 1 170 1 80 2 80 3 220 4 i j ij ij x c z Сайт www.resolventa.ru , E-mail: Сайт www.resolventa.ru , E-mail: resolventa@list.ru 22 ВОПРОСЫ ДЛЯ САМОКОНТРОЛЯ 1. Что называется транспортной задачей 2. Что называется тарифом перевозки в транспортной задаче 3. Какая транспортная задача называется закрытой 4. Какая транспортная задача называется открытой 5. В чем состоит процедура закрытия открытой транспортной задачи 6. Что называется фиктивным поставщиком 7. Что называется фиктивным потребителем 8. Что называется потенциалом в транспортной задаче 9. В чем состоит схема решения транспортной задачи с помощью метода потенциалов 10. Как строится первоначальный план перевозок с помощью метода севе- ро-западного угла 11. Как строится первоначальный план перевозок с помощью метода наименьшей стоимости 12. Что называется циклом в транспортной таблице 13. Какие клетки транспортной таблицы называются базисными 14. Какие клетки транспортной таблицы называются свободными 15. Какой план перевозок называется вырожденным 16. Какой план называется ациклическим 17. В чем состоит схема пополнения вырожденного плана перевозок 18. В чем состоит критерий оптимальности плана при решении транспортной задачи методом потенциалов Сайт www.resolventa.ru , E-mail: Сайт www.resolventa.ru , E-mail: resolventa@list.ru 23 ЗАДАНИЯ ДЛЯ САМОСТОЯТЕЛЬНОЙ РАБОТЫ 1. Транспортная задача задана следующей транспортной таблицей заказы запасы 1 B 3 B 4 B 20 25 30 1 A 24 6 4 2 2 A 28 3 5 4 3 A 23 3 6 3 1.1. Выяснить, является задача открытой или закрытой 1.2. Составить первоначальный план перевозок с помощью метода се- веро-западного угла 1.3. Составить первоначальный план перевозок с помощью метода наименьшей стоимости 1.4. С помощью метода потенциалов найти оптимальный план перевозок, обеспечивающий их минимальную стоимость 1.5. Найти минимальную стоимость перевозок. Сайт www.resolventa.ru , E-mail: Сайт www.resolventa.ru , E-mail: resolventa@list.ru 24 ЛИТЕРАТУРА Основная 1. Вентцель Е.С. Исследование операций Задачи, принципы, методология. Учебное пособие. – М Дрофа, 2004. 2. Колемаев В.А. Математическая экономика. Учебник для вузов. - М ЮНИТИ-ДАНА, 2005. 3. Кремер Н.Ш. Исследование операций в экономике. – М ЮНИТИ, 2006. 4. Орехов НА, Левин А.Г., Горбунов Е.А. Математические методы и модели в экономике. Учебное пособие для вузов / Под ред. проф. НА. Оре- хова – М ЮНИТИ-ДАНА, 2004. Дополнительная 5. Экономико-математическое моделирование. Учебник для вузов / Под общ. ред. И.Н. Дрогобыцкого. – М Изд. Экзамен, 2004. 6. Лунгу КН. Линейное программирование. Руководство к решению задач М Физматлит, 2005. 7. Малыхин В.И. Математика в экономике Учебное пособие. – М ИН- ФРА-М, 2002. 8. Самаров КЛ, Шапкин АС. Задачи с решениями по высшей математике и математическим методам в экономике Учебное пособие – М Из- дательско-торговая корпорация «Дашков и Ко, 2007. 9. Таха ХА. Введение в исследование операций. – М ВИЛЬЯМС, 2007. |