WWW.PDF.KNIGI-X.RU
БЕСПЛАТНАЯ  ИНТЕРНЕТ  БИБЛИОТЕКА - Разные материалы
 

«МИНОБРНАУКИ РОССИИ Федеральное государственное бюджетное образовательное учреждение высшего профессионального образования «Ухтинский государственный ...»

МИНОБРНАУКИ РОССИИ

Федеральное государственное бюджетное образовательное учреждение

высшего профессионального образования

«Ухтинский государственный технический университет»

(УГТУ)

А. В. Семериков

Решение транспортных задач

Учебное пособие

Ухта, УГТУ, 2013

УДК 004 : 519.86 (076.1)

ББК 22.12 я7

С 30

Семериков, А. В.

С 30 Решение транспортных задач [Текст] : учеб. пособие / А. В. Семериков. –

Ухта : УГТУ, 2013. – 58 с.

ISBN 978-5-88179-781-2 В пособии представлено решение транспортной задачи. Она представляет собой задачу линейного программирования, которую можно решить с помощью симплексметода. Поэтому в пособии вначале представлено решение транспортной задачи этим методом, а затем продемонстрировано решение этой же задачи методом потенциалов, в котором идея симплекс-метода представлена в другой форме. Как известно, применение новой формы решения (более удобной для этой задачи) обусловлено особенностью ограничений в постановке задачи.

Материал в пособии изложен в следующем порядке:

а) представлена общая постановка, цели задачи;

б) представлено решение задачи симплекс-методом;

г) проиллюстрировано три метода отыскания опорного плана;

д) представлено решение методом потенциалов.

Тем самым на конкретном примере была показана связь симплекс-метода и метода потенциалов, а также продемонстрирована эффективность последнего при ручном счёте.



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

УДК 004 : 519.86 (076.1) ББК 22.12 я7 Учебное пособие рекомендовано к изданию Редакционно-издательским советом Ухтинского государственного технического университета.

Рецензенты: Н. А. Николаева, главный специалист планово-экономического отдела ОАО «Газпром промгаз», доцент, к.т.н.; В. М. Шарыгин, главный научный сотрудник филиала ООО «Газпром ВНИИГАЗ» в г. Ухта.

© Ухтинский государственный технический университет, 2013 © Семериков А. В., 2013 ISBN 978-5-88179-781-2 ОГЛАВЛЕНИЕ

1. Транспортная задача. Общая постановка задачи

2. Пример транспортной задачи

3. Решение транспортной задачи симплекс-методом

4. Решение транспортной задачи методом потенциалов

5. Методы составления начального опорного плана

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

7. Метод наименьшей стоимости

8. Метод Фогеля

9. Результаты вычислений всех методов

10. Понятие цикла

11. Метод потенциалов.

12. Результаты оптимизации базовых решений

13. Открытая транспортная задача.

14. Многопродуктовая транспортная задача.

15. Другие типы задач

15.1 Задача о назначениях

15.2 Задача с неразличимыми поставщиками и потребителями................. 42

15.3 Транспортная модель с промежуточными пунктами

15.4 Модель управления запасами

Заключение

Задания для самостоятельной работы

Литература

Введение

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





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

Задача ТЗ ассоциируется с перемещением груза от поставщиков к потребителям. Решение данной задачи позволяет разработать наиболее рациональные пути и способы транспортирования товаров, устранить чрезмерно дальние, встречные, повторные перевозки. Всё это сокращает время продвижения товаров, уменьшает затраты предприятий и фирм, связанные с осуществлением процессов снабжения сырьём, материалами, топливом, оборудованием и т. д.

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

Впервые высказывание о важности решения задач линейного программирования и, в частности, ТЗ было сделано в прошлом веке. Тогда же были предложены методы решения этих задач. У истоков создания теории линейного программирования стоял русский учёный – Л. В. Канторович. Широкое практическое использование этой теории началось после появления вычислительных машин. Это связано с тем, что при реализации методов линейного программирования требуется выполнять многочисленные последовательные арифметические операции. Ошибка в одном действии приводила к неверному результату и поиску верного решения путём повторного утомительного расчёта.

В настоящее время имеются многочисленные публикации по практическому использованию решений ТЗ, разработаны программные средства, в том числе WEB-приложения [1].

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

В учебном пособии представлена однопродуктовая модель. Вместе с тем её можно использовать и в случае многопродуктового перемещения товаров.

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

1. Транспортная задача. Общая постановка задачи

–  –  –

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

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

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

–  –  –

Система (1.5) содержит т + п уравнений с тп неизвестными. Её особенность состоит в том, что коэффициенты при неизвестных всюду равны единице.

Кроме того, все уравнения системы (1.5) могут быть разделены на две группы:

первая группа из т первых уравнений («горизонтальные» уравнения) и вторая группа из п остальных уравнений («вертикальные» уравнения). В каждом из горизонтальных уравнений содержатся неизвестные с одним и тем же первым индексом (они образуют одну строку матрицы перевозок), в каждом из вертикальных уравнений содержатся неизвестные с одним и тем же вторым индексом (они образуют один столбец матрицы перевозок). Таким образом, каждая неизвестная встречается в системе (1.5) дважды: в одном и только одном горизонтальном и в одном и только одном вертикальном уравнениях.

Для решения транспортной задачи необходимо, кроме запасов и потребностей, знать также и тарифы сij, т. е. стоимость перевозки единицы груза с базы Аi потребителю Вj.

Совокупность тарифов сij также образует матрицу, которую можно объединить с матрицей перевозок и данными о запасах и потребностях в одну таблицу:

–  –  –

Требуется в области допустимых решений системы уравнений (1.5) и (1.6) найти решение, минимизирующее линейную функцию (1.7).

Таким образом, мы видим, что транспортная задача является задачей линейного программирования. Для её решения применяют симплекс-метод и метод потенциалов. На конкретном примере проследим за всеми этапами решения задачи.

2. Пример транспортной задачи При заданных объёмах груза в пунктах отправления и потребности в пунктах назначения определить оптимальный план перемещения груза от отправителя к потребителю.

Исходные данные:

Запас груза в i-м пункте отправления ai: a1 = 30, a2 = 15, a3 = 25.

Потребность j-го пункта назначения в грузе bj: b1 = 20, b2 = 5, b3 = 45.

Матрица тарифов (стоимость перевозки единицы груза) Ci,j:

–  –  –

bi = 20 + 5 + 45 = 70.

Следовательно, задача является закрытой (сбалансированной).

Приведём систему ограничений к каноническому виду, для этого введём в каждое условие искусственную переменную R.

Тогда система запишется в виде:

–  –  –

0 x1,1 + 0 x1,2 + 1 x1,3 + 0 x2,1 + 0 x2,2 + 1 x2,3 + 0 x3,1 + 0 x3,2 + 1 x3,3 + R 6 = 45 Переходим к формированию исходной симплекс-таблицы. В строку F таблицы заносятся коэффициенты целевой функции.

Так как среди исходного набора условий были равенства, мы ввели искусственные переменные R. Это значит, что в симплекс-таблицу нам необходимо добавить дополнительную строку M, элементы которой рассчитываются как сумма соответствующих элементов условий-равенств (тех, которые после при

–  –  –

Так как в столбце свободных членов нет отрицательных элементов, то найдено допустимое решение. В строке M имеются отрицательные элементы, это означает, что полученное решение не оптимально. Определим ведущий столбец. Для этого найдём в строке M максимальный по модулю отрицательный элемент – это -2 (столбец x1,1 ). Ведущей строкой будет та, для которой положительное отношение свободного члена к соответствующему элементу ведущего столбца минимально. Ведущей строкой является R4, а ведущий элемент: 1.

–  –  –

В строке M имеются отрицательные элементы, это означает, что полученное решение не оптимально. Определим ведущий столбец. Для этого найдём в строке M максимальный по модулю отрицательный элемент – это -2 (столбец x1,2 ). Ведущей строкой будет та, для которой положительное отношение свободного члена к соответствующему элементу ведущего столбца минимально. Ведущей строкой является R5, а ведущий элемент: 1.

–  –  –

В строке M имеются отрицательные элементы, это означает, что полученное решение не оптимально. Определим ведущий столбец. Для этого найдем в строке M максимальный по модулю отрицательный элемент – это -2 (столбец x1,3 ). Ведущей строкой будет та, для которой положительное отношение свободного члена к соответствующему элементу ведущего столбца минимально. Ведущей строкой является R1, а ведущий элемент: 1.

–  –  –

В строке M имеются отрицательные элементы, это означает, что полученное решение не оптимально. Определим ведущий столбец. Для этого найдём в строке M максимальный по модулю отрицательный элемент – это -2 (столбец x2,1 ). Ведущей строкой будет та, для которой положительное отношение свободного члена к соответствующему элементу ведущего столбца минимально. Ведущей строкой является R2, а ведущий элемент: 1.

–  –  –

В строке M имеются отрицательные элементы, это означает, что полученное решение не оптимально. Определим ведущий столбец. Для этого найдём в строке M максимальный по модулю отрицательный элемент – это -2 (столбец x3,1 ). Ведущей строкой будет та, для которой положительное отношение свободного члена к соответствующему элементу ведущего столбца минимально. Ведущей строкой является x1,1, а ведущий элемент: 1.

–  –  –

В строке M имеются отрицательные элементы, это означает, что полученное решение не оптимально. Определим ведущий столбец. Для этого найдём в строке M максимальный по модулю отрицательный элемент – это -2 (столбец x2,2 ). Ведущей строкой будет та, для которой положительное отношение свободного члена к соответствующему элементу ведущего столбца минимально. Ведущей строкой является x1,2, а ведущий элемент: 1.

–  –  –

В строке M имеются отрицательные элементы, это означает, что полученное решение не оптимально. Определим ведущий столбец. Для этого найдём в строке M максимальный по модулю отрицательный элемент – это -2 (столбец x2,3 ). Ведущей строкой будет та, для которой положительное отношение свободного члена к соответствующему элементу ведущего столбца минимально. Ведущей строкой является x2,1, а ведущий элемент: 1.

–  –  –

В строке M имеются отрицательные элементы, это означает, что полученное решение не оптимально. Определим ведущий столбец. Для этого найдём в строке M максимальный по модулю отрицательный элемент – это -2 (столбец x3,2 ). Ведущей строкой будет та, для которой положительное отношение свободного члена к соответствующему элементу ведущего столбца минимально. Ведущей строкой является R3, а ведущий элемент: 1.

–  –  –

В строке F имеются отрицательные элементы, это означает, что полученное решение не оптимально. Определим ведущий столбец. Для этого найдём в строке F максимальный по модулю отрицательный элемент – это -15. Ведущей строкой будет та, для которой положительное отношение свободного члена к соответствующему элементу ведущего столбца минимально. Ведущей строкой является x3,2, а ведущий элемент: 1.

–  –  –

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

Найдено оптимальное решение (минимальные транспортные расходы):

F=10 · 30 + 10 · 20 + 25 · 10 + 20 · 10 + 5 · 10 = 1000, при значениях переменных равных:

x1,3 = 10 (количество продукции, доставленное от поставщика №1 к потребителю №3);

x2,3 = 10 (количество продукции, доставленное от поставщика №2 к потребителю №3);

x3,3 = 25 (количество продукции, доставленное от поставщика №3 к потребителю №3);

x1,1 = 20 (количество продукции, доставленное от поставщика №1 к потребителю №1);

x2,2 = 5 (количество продукции, доставленное от поставщика №2 к потребителю №2).

Результат решения задачи можно представить в виде графа.

–  –  –

4. Решение транспортной задачи методом потенциалов Рассмотренную выше задачу можно решить путём некоторых преобразований таблицы перевозок, которая изображена в разделе Общая постановка задачи.

Эти преобразования соответствуют переходу от одного плана перевозок к другому. Но, как и в общем случае, оптимальное решение ищется среди базисных решений. Следовательно, мы будем иметь дело только с базисными (или опорными) планами. Так как в данном случае ранг системы ограничений-уравнений равен т + п – 1, то среди всех тп неизвестных хij выделяется т + п – 1 базисных неизвестных, а остальные (m – 1)·(n – 1) неизвестных являются свободными.

В базисном решении свободные неизвестные равны нулю. Обычно эти нули в таблицу не вписывают, оставляя соответствующие клетки пустыми. Таким образом, в таблице перевозок, представляющей опорный план, мы имеем т + п – 1 заполненных и (т – 1)·(п – 1) пустых клеток.

Для контроля надо проверять, равна ли сумма чисел в заполненных клетках каждой строки таблицы перевозок запасу груза на соответствующей базе, а в каждом столбце – потребности заказчика [этим подтверждается, что данный план является решением системы (1.5)].

5. Методы составления начального опорного плана

Как и в общем случае, решение транспортной задачи начинается с отыскания первого опорного плана (исходного базиса). Мы рассмотрим три наиболее распространённых метода построения такого базиса. Суть этих методов состоит в том, что базисный план составляется последовательно, в несколько шагов (точнее, т + п – 1 шагов). На каждом из этих шагов заполняется одна клетка, при том так, что либо полностью удовлетворяется один из заказчиков (тот, в столбце которого находится заполняемая клетка), либо полностью вывозится весь запас груза с одной из баз (с той, в строке которой находится заполняемая клетка).

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

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

Начиная с первоначально данной таблицы и повторив т + п – 2 раз описанный шаг, мы придём к «таблице», состоящей из одной строки и одного столбца (иначе говоря, из одной пустой клетки). Другими словами, мы пришли к задаче с одной базой и с одним потребителем, причём потребности этого единственного заказчика равны запасу груза на этой единственной базе. Заполнив последнюю клетку, мы освобождаем последнюю базу и удовлетворяем потребность последнего заказчика. В результате, совершив т + п – 1 шагов, мы и получим искомый опорный план.

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

Для рассматриваемого примера начальная транспортная таблица имеет вид:

–  –  –

В колонке справа, в нижней строке расположены соответственно объёмы груза в пунктах производства и пунктах потребления. Внутри таблицы в маленьких квадратах расположены тарифы перевозок единицы груза. В результате реализации начального опорного плана должны быть заполнены т + п – 1 = 3 + 3 – 1 = 5 клеток с базисными переменными, а остальные (m – 1) · (n – 1) = (3 – 1) · (3 – 1) = 4 клетки с небазисными переменными не заполняются.

В настоящем пособии рассматриваются три метода нахождения начального решения.

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

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

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

Рассмотрим каждый из этих методов.

–  –  –

В оставшейся новой таблице с тремя строками A1, A2, A3 и одним столбцом B3 северо-западным углом будет клетка для неизвестного x13. Теперь третий заказчик B3 может принять весь запас с базы А1 (а"1 = 5, b3 = 45, а"1 b3).

Полагаем x13 = 5, вписываем это значение в клетку x13 и исключаем из рассмотрения первую строку. У заказчика из В3 осталась ещё не удовлетворённой потребность b'3 = 40.

–  –  –

Теперь переходим к заполнению клеток для неизвестного х23 и х33. Потребности B3 будут полностью удовлетворены базами А2, и А3. Исключаем третий столбец.

–  –  –

План составлен. Базис образован неизвестными x11, x12, x13, x23, x33. Правильность составленного плана легко проверить, подсчитав суммы чисел, стоящих в заполненных клетках по строкам и столбцам.

Общий объём перевозок в тонно-километрах для этого плана составит:

S1 = 20·10 + 5·20 + 5·30 + 15·20 + 25·10 = 1000.

7. Метод наименьшей стоимости

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

В данном случае заполнение таблицы начинается с клетки для неизвестного х31, для которого мы имеем значение с31 = 5, наименьшее из всех значений сij. Эта клетка находится на пересечении третьей строки и первого столбца, соответствующем третьей базе А3 и первому заказчику В1. Третья база А3 может полностью удовлетворить потребность первого заказчика В1 (а3 = 25, b1 = 20, a3 b1).

Полагая x31 = 20, вписываем это значение в клетку х31 и исключаем из рассмотрения первый столбец. На базе А3 остаётся изменённый запас а'3 = 5.

B1 B2 B3 A1 A2 A3 В оставшейся новой таблице с тремя строками А1, А2, А3 и двумя столбцами В2, В3 имеются две клетки с наименьшим значением cij, где c22 = 10 и c33 = 10. Выбираем (любую из них) клетку с c22 = 10. Вторая база А2 может полностью удовлетворить потребность второго заказчика В2 (а2 = 15 b2 = 5, a2 b2.

Полагая x22 = 5, вписываем это значение в клетку х22 и исключаем из рассмотрения второй столбец. На базе А2 остается изменённый запас а'2 = 10.

–  –  –

Остался незаполненным один третий столбец. Его заполняем согласно имеющимся запасам на базах А1, А2, А3. В результате получаем x13 = 30, x23 = 10, x33 = 5.

–  –  –

Общий объём перевозок в тонно-километрах для этого плана составит:

S1 = 20·5 + 5·10 + 30·30 + 10·20 + 5·10 = 1300.

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

8. Метод Фогеля

Суть метода состоит в следующем: в распределительной таблице по строкам и столбцам определяется разность между двумя наименьшими тарифами.

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

–  –  –

Три наибольшие разности оказались одинаковыми и равными 10.

Выбираем столбец В3 и заполняем клетку х33 с наименьшим тарифом 10 в этом столбце. Присвоим переменной х33 = 25. Запас на базе А3 полностью использован потребителем В3. Эта строчка исключается из расчёта.

–  –  –

Снова рассчитаем разности. Из расчёта исключаем столбец В1 и строку А3.

Все разности имеют одинаковое значение 10. В столбце В2 у переменной х22 наименьший тариф. Присвоим ей значение х22 = 5. Спрос у базы В2 полностью удовлетворён. Столбец В2 исключаем из расчёта.

–  –  –

Остались незаполненными две клетки. Присваиваем переменной х13 = 10 (остаток неиспользованного запаса на А1). Присваиваем переменной х23 = 10 (остаток запаса на А2).

–  –  –

Все базисные переменные в количестве пяти определены. Опорный план сформирован.

Общий объём перевозок в тонно-километрах для этого плана составит:

S1 = 20·10 + 5·10 + 10·30 + 10·20 + 25·10 = 1000.

–  –  –

Метод северо-западного угла:

S = 1000 тонно-километров.

Метод наименьшей стоимости:

S = 1300 тонно-километров.

Метод Фогеля:

S = 1000 тонно-километров.

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

При использовании метода Фогеля время расчёта больше, чем у двух выше рассмотренных. Это вызвано тем, что на каждом шаге приходится заново искать разности между минимальными элементами в строках и столбцах. Однако это время компенсируется при дальнейшем поиске оптимального решения по методу потенциалов. Уменьшение количества дальнейших расчётов обусловлено тем, что метод Фогеля, как правило, даёт не только начальное опорное решение, но и оптимальное решение. Метод потенциалов в этом случае нужен фактически только для подтверждения, что получено действительно оптимальное решение. По этой причине метод Фогеля наиболее предпочтителен для решения транспортной задачи.

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

10. Понятие цикла

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

Циклом пересчёта в таблице перевозок называется последовательность неизвестных, удовлетворяющая следующим условиям:

1. Одно из неизвестных последовательности свободное, а все остальные – базисные.

2. Каждые два соседних в последовательности неизвестных лежат либо в одном столбце, либо в одной строке.

3. Три последовательных неизвестных не могут находиться в одном столбце или в одной строке.

4. Если, начиная с какого-либо неизвестного, мы будем последовательно переходить от одного к следующему за ним неизвестному, то через несколько шагов мы вернёмся к исходному неизвестному.

Второе условие означает, что у двух соседних неизвестных в цикле либо первые, либо вторые индексы одинаковы.

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

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

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

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

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

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

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

Описанное выше преобразование таблицы перевозок, в результате которого преобразуется базис, называется пересчётом по циклу.

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

Выясним теперь, как пересчет по циклу влияет на общий объём затрат на перевозки и при каком условии эти затраты становятся меньше.

Пусть хpq – некоторое свободное неизвестное, для которого мы построили цикл и осуществили пересчёт по циклу с некоторым числом х. Если вершине цикла, находящейся в i-й строке и j-м столбце таблицы перевозок, приписан знак «+», то значение неизвестного хij, находящегося в этой вершине, увеличивается на х, что в свою очередь вызывает увеличение затрат на сij х, где сij – тариф, соответствующий этой клетке; если же указанной вершине приписан знак «–», то значение неизвестного хij уменьшается на х, что вызывает уменьшение затрат на сijх.

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

Теперь, очевидно, мы можем заключить, что в целом при пересчёте по циклу, соответствующему свободному неизвестному хpq общий объём затрат на перевозки изменится на произведение алгебраической суммы тарифов на х, т. е.

на величину Spqх. Следовательно, если алгебраическая сумма тарифов для некоторого свободного неизвестного хpq отрицательна (Spq 0), то пересчёт по циклу, соответствующему этому неизвестному, приводит к уменьшению общей суммы затрат на реализацию плана перевозок. Если же алгебраическая сумма тарифов положительна (Spq 0), то пересчёт по соответствующему циклу приведёт к увеличению общей суммы затрат. И, наконец, если алгебраическая сумма тарифов равна нулю (Spq = 0), то пересчёт по соответствующему циклу не изменит общую сумму затрат (два различных базисных плана требуют одинаковых затрат на их реализацию).

Рассмотрим цикл на примере в таблице перевозок, составленной по диагональному методу.

B1 B2 B3 A1 - + 30 A2 A3 + - 25 Свободной (небазисной переменной) х31 соответствует цикл х31, х33, х13, х11, х31.

В указанном выше цикле для свободного неизвестного х31 получим:

старые значения: х31 = 0, х33 = 25, х13 = 5, х11 = 20;

новые значения: х31 = х, х'33 = 25 – х, x13 = 5 + х, х'11 = 20 – х.

Так, в рассмотренном выше цикле имеем отрицательные вершины х33 и х11;

следовательно, выбрав х = min{20;25} = 20, мы получаем:

старые значения х31 = 0, х33 = 25, х13 = 5, х11 = 20;

новые значения: х31 = 20, х'33 = 5, x13 = 25, х'11 = 0.

Переменная х31 стала базисной, а переменная х11 небазисной, т. е.

вместо прежнего базисного решения получаем новое базисное решение:

B1 B2 B3 A1 A2 A3

Для цикла х31, х33, х13, х11, х31 в рассмотренной задаче алгебраическая сумма тарифов:

S21 = c31 – c33 + c13 – c11 = 5 –10 + 30 –10 = 15 0.

Значит, пересчёт по этому циклу не снижает расходы.

И действительно, осуществив такой пересчёт, мы получаем план, по которому объём перевозок в тонно-километрах составит:

S2 = 20·5 + 5·10 + 15·20 + 25·30 +5·20 = 1300.

Тогда как по исходному плану он составил S1 = 1000. Имеем увеличение объёма перевозок на 300 тонно-километров, что и следовало ожидать, так как алгебраическая сумма тарифов в данном случае равна 15, а пересчёт по циклу осуществляется с помощью числа х = 20 (изменение затрат равно -15·20 = 300).

Теперь рассмотрим цикл на примере в таблице перевозок, составленной по методу наименьшей стоимости.

B1 B2 B3 A1 + - 30 A2 A3

- + 25 Неизвестному х11 соответствует цикл х11, х13, х33, х31, х11.

В указанном выше цикле для свободного неизвестного х11 получим:

старые значения: х11 = 0, х13 = 30, х33 = 5, х13 = 20;

новые значения: х11 = х, х'13 = 30 – х, x33 = 5 + х, х'31 = 20 – х.

Так, в рассмотренном выше цикле имеем отрицательные вершины х13 и х31;

следовательно, выбрав х = min{20;30} = 20, мы получаем:

старые значения х11 = 0, х13 = 30, х33 = 5, х13 = 20;

новые значения: х11 = 20, х'13 = 10, x33 = 25, х'31 = 0, т. е. вместо прежнего базисного решения получаем новое базисное решение:

B1 B2 B3 A1 A2 A3

Для цикла х11, х13, х33, х31, х11 в рассмотренной задаче алгебраическая сумма тарифов:

S21 = c11 – c13 + c33 – c31 = 10 –30 + 10 –5 = -15 0.

Значит, пересчёт по этому циклу снижает расходы.

И действительно, осуществив такой пересчёт, мы получаем план, по которому объём перевозок в тонно-километрах составит:

S2 = 20·10 + 10·30 + 5·10 +20·10 + 25·10 = 1000.

Тогда как по исходному плану он составил S1 = 1300:

S1 = 20·5 + 5·10 + 15·20 + 25·30 +5·20 = 1300.

Имеем снижение объёма перевозок на 300 тонно-километров, что и следовало ожидать, так как алгебраическая сумма тарифов в данном случае равна 15, а пересчёт по циклу осуществляется с помощью числа х = 20 (изменение затрат равно -15·20 = -300).

–  –  –

где cij – тарифы, соответствующие клеткам, заполненным базисными неизвестными. Эти числа ui и j называются потенциалами соответствующих баз и потребителей.

Зная потенциалы, легко вычислить алгебраическую сумму тарифов.

Действительно, если в алгебраической сумме тарифов по циклу, соответствующему свободному неизвестному xpq, заменить тарифы базисных клеток их выражениями через потенциалы по формулам (12.1), то в силу чередования знаков при вершинах цикла все потенциалы, кроме ир и q, сократятся, и мы получим:

Spq = cpq – (up + q).

Для базисных клеток сумма потенциалов строки и столбца, в которых находится эта клетка, равна тарифу, соответствующему этой клетке; если же клетка для неизвестного xpq свободная, то сумму потенциалов up + q = cpq (12.2) называют косвенным тарифом этой клетки.

Следовательно, алгебраическая сумма тарифов для свободной клетки xpq равна разности её настоящего («истинного») и косвенного тарифов:

Spq = cpq – cpq. (12.3) Из (12.3) следует, что если косвенный тариф для данной свободной клетки больше её истинного тарифа, то алгебраическая сумма тарифов по циклу, соответствующему этой клетке, будет отрицательна; если же косвенный тариф меньше истинного, то алгебраическая сумма тарифов положительна, и, наконец, если косвенный тариф равен истинному, то алгебраическая сумма тарифов равна нулю.

Потенциалы можно найти из системы равенств (12.1), рассматривая их как систему т + п – 1 уравнений с т + п неизвестными. Так как неизвестных здесь на единицу больше, чем уравнений, то по крайней мере один из потенциалов мы можем выбрать произвольно, положив, например, u1 = 0; тогда остальные потенциалы легко определяются из уравнения (12.1).

Применим метод потенциалов для трёх рассмотренных выше опорных планов.

Для плана, полученного по диагональному методу, имеем

–  –  –

Для клетки с неизвестными х11 косвенный тариф больше истинного.

Следовательно, для них мы будем иметь отрицательные алгебраические суммы тарифов:

S11 = c11 c '11 = 10 25 = 15.

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

Цикл (1,1), (1,3), (3,3), (3,1), (1,1) – вершины цикла помечены значками плюс (+) и минус (-).

–  –  –

В указанном выше цикле для свободного неизвестного х11 получим:

старые значения: х11 = 0, х13 = 30, х33 = 5, х13 = 20;

новые значения: х11 = х, х'13 = 30 – х, x33 = 5 + х, х'31 = 20 – х.

Так, в рассмотренном выше цикле имеем отрицательные вершины х13 и х31;

следовательно, выбрав х = min{20;30} = 20, мы получаем:

старые значения х11 = 0, х13 = 30, х33 = 5, х13 = 20;

новые значения: х11 = 20, х'13 = 10, x33 = 25, х'31 = 0, т. е. вместо прежнего базисного решения получаем новое базисное решение:

–  –  –

Начальное решение идентично начальному решению, полученному по методу северо-западного угла. Таким образом, все дальнейшие вычисления по получению оптимального решения будут идентичны вычислениям, проведённым после применения метода северо-западного угла. Поэтому в данном случае нет необходимости в проведении расчётов по улучшению начального решения, полученного по методу Фогеля.

12. Результаты оптимизации базовых решений Метод северо-западного угла: S = 1000 ед.

Метод наименьшей стоимости: S = 1000 ед.

Метод Фогеля: S = 1000 ед.

Анализ решений позволяет сделать следующие выводы.

1. Улучшение различных опорных планов приводит к одинаковому оптимальному решению.

2. Метод северо-западного угла может привести к более близкому к оптимальному решению, чем метод наименьшей стоимости.

3. Метод Фогеля имеет существенное преимущество перед другими, потому что даёт возможность найти опорный план, максимально приближенный к оптимальному.

–  –  –

Рассмотрим последовательно эти два случая.

Транспортная задача с избытком запасов Сведем её к ранее рассмотренной транспортной задаче с правильным балансом. Для этого, сверх имеющихся n пунктов назначения В1, В2,..., Вn, введём ещё один, фиктивный пункт назначения Вn+1, которому припишем фиктивную заявку, равную избытку запасов над заявками bn+1 = ai b j (где i = 1,..., m; j = 1,..., n), а стоимость перевозок из всех пунктов отправления в фиктивный пункт назначения bn+1 будем считать равной нулю. Введением фиктивного пункта назначения F с его заявкой bn+1 мы сравняли баланс транспортной задачи, и теперь её можно решать как обычную транспортную задачу с правильным балансом.

Положим в пунктах производства A, B, C производится продукция соответственно в количестве 100 ед., 200 ед., 300 ед., которая потребляется в пунктах D, E в количестве соответственно 150 ед., 350 ед. В этом случае для фиктивного пункта назначения недостающий объём потребления равен (100 + 200 + 300) – (150 + 350) = 100 ед.

Транспортная задача становится сбалансированной. Её начальное решение имеет вид:

–  –  –

У поставщика C не востребовано 100 ед. продукции.

Транспортная задача с избытком заявок Эту задачу можно свести к обычной транспортной задаче с правильным балансом, если ввести фиктивный пункт отправления F с запасом ат+1, равным недостающему запасу, и стоимость перевозок из фиктивного пункта отправления во все пункты назначения принять равной нулю. Положим в пунктах производства A, B, C производится продукция соответственно в количестве 100 ед., 200 ед., 100 ед., которая потребляется в пунктах D, E в количестве соответственно 150 ед., 350 ед. В этом случае для фиктивного пункта производства недостающий объём составляет (150 + 350) – (100 + 200 + 100) = 100 ед.

Транспортная задача становится сбалансированной. Её решение имеет вид:

–  –  –

Потребитель E не получит продукцию в объёме 100 ед.

14. Многопродуктовая транспортная задача Это частный тип транспортных задач, при котором вместо одного вида товара их может быть несколько. Они могут отличаться как по стоимости перевозок, так и по конечному получателю, т. е. разные продукты с одной базы могут идти к разным потребителям или, наоборот, один потребитель может нуждаться в товарах с разных баз.

Такие задачи лучше всего разбить на однопродуктовые подзадачи и решать отдельно одним из вышеприведённых методов. А после получения частных решений объединить результат в одну таблицу.

Рассмотрим решение задачи при перемещении трёх видов продукции М1, М2, М3 между двумя поставщиками А1, А2 и двумя потребителями В1 и В2.

Поставщик А1 может поставить продукцию М1, М2 соответственно в количестве 300 ед. и 100 ед. Поставщик А2 может поставить продукцию М3, М1 соответственно в количестве 100 ед. и 200 ед. Потребителю В1 требуется продукция М2, М1 в количестве 100 ед. и 400 ед., а потребителю В2 требуется продукция М1, М3 в количестве 100 ед. и 100 ед. Для запрещения поставки продукции несоответствующего вида необходимо в точке пересечения продукций разного вида назначить тариф на порядок больше, чем у совпадающих видов. В данном случае назначаем тариф, равный 1000.

Начальный опорный план имеет вид:

В1 В2 М2 М1 М1 М3 М1 300 А1 М2 100 М3 100 А2 М1 200 Решение это транспортной задачи приводит к следующему оптимальному плану перемещения продукции:

В1 В2 М2 М1 М1 М3 М1 300 А1 М2 100 М3 100 А2 М1 200

Решение можно представить в виде графа:

–  –  –

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

К таким задачам относятся следующие:

• оптимальное закрепление за станками операций по обработке деталей.

В них сij является таким экономическим показателем, как производительность.

Задача позволяет определить, сколько времени и на какой операции нужно использовать каждый из станков, чтобы обработать максимальное количество деталей. Так как транспортная задача требует нахождения минимума, то значения сij берутся с отрицательным знаком;

• оптимальные назначения, или проблема выбора. Имеется m механизмов, которые могут выполнять т различных работ с производительностью сij.

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

• задача о сокращении производства с учётом суммарных расходов на изготовление и транспортировку продукции;

• увеличение производительности автомобильного транспорта за счёт минимизации порожнего пробега. Уменьшение порожнего пробега сократит количество автомобилей для перевозок, увеличив их производительность;

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

15.1 Задача о назначениях Это задача, когда требуется распределить «m» работ по «n» станкам. Работа на станке связана с затратами « cij », где i – номер работы, j – номер станка.

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

Здесь предложение в каждом исходном пункте равно 1. Аналогично спрос в каждом пункте назначения равен 1. Если какую-либо работу нельзя выполнить, то соответствующая стоимость cij берётся равной очень большому числу «М».

Структура задачи о назначениях:

–  –  –

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

Оптимальное решение задачи о назначениях не изменится, если к любой строке или столбцу матрицы стоимостей прибавить или вычесть постоянную величину. Этот факт доказывается следующим образом. Если pi и q j вычитаются из i-ой строки и j-го столбца, то новые стоимости имеют вид

cij = cij pi q j. Новая целевая функция имеет вид:

–  –  –

Отсюда следует, что минимизация z приводит к тому же решению, как и z. Это соображение показывает, что если можно построить новую матрицу cij с нулевыми элементами и эти элементы или их подмножество соответствуют допустимому решению, то такое решение будет оптимальным, поскольку стоимость не может быть отрицательной.

–  –  –

В этом случае невозможно найти допустимое решение, состоящее из 0.

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

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

Квадратами помечены элементы, соответствующие допустимому (оптимальному) назначению со стоимостью 2 + 13 + 7 + 8 = 30. Первый работник выполняет первую работу, второй работник выполняет третью работу, третий работник выполняет вторую работу, четвёртый работник выполняет четвёртую работу.

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

15.2 Задача с неразличимыми поставщиками и потребителями

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

Для моделирования такой схемы перемещения вводится понятие буфера В.

Буфер – это количество всей перевозимой продукции. Так, например, если имеются три поставщика А, B, C, которые поставляют продукцию в количестве соответственно 100 ед., 300 ед., 400 ед., то величина буфера должна быть равна B = 100 ед. + 300 ед. + 400 ед. = 800 ед. Такой же буфер должен присутствовать и у потребителя. При наличии двух потребителей D и E с объёмами потребления соответственно 250 ед. и 550 ед. B = 250 ед. + 550 ед. = 800 ед.

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

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

–  –  –

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

Изменим тарифы перевозки.

–  –  –

Результаты расчёта представим в виде графа:

Из графа видно, что поставщик B поставляет продукцию потребителю E транзитом через поставщика C. В данном случае поставщик C выступает в роли потребителя.

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

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

Исходные данные для задачи представим в виде графа:

В рассматриваемой задаче имеются: пять пунктов отправления продукции (A, B, C, D, F), четыре пункта назначении (C, D, F, E) и три транзитных пункта (C, D, F), через которые проходит транзитом продукция в объёме (100 + 200) = 300 ед. Поэтому в пункте D может присутствовать (300 + 50) = 350 ед., в пункте F (300 + 100) = 400 ед.

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

Метод решение этой задачи ничем не отличается от ранее рассмотренных задач.

Оптимальный опорный план имеет следующий вид:

C D F E A B C D F 300 50 + 300 100 + 300 150 1200

Это решение представим в виде графа:

–  –  –

Из графа видно, что вся продукция (300 ед.) из транзитного пункта C поступает в пункт потребления D, в котором остаётся потребляемое количество 50 ед. Остаток в объёме 250 ед. поступает в пункт F, из которого 100 ед. остаются, оставшиеся 150 ед. идут на потребление в пункт E.

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

15.4 Модель управления запасами

Предприятие производит продукцию, спрос на которую отмечается в течении четырёх месяцев. Он оценивается соответственно в 150, 200, 200, 150 единиц изделий в месяц. По технологическим причинам предприятие может выпускать в каждом месяце соответственно 200, 150, 150, 200 единиц изделий. Как видно, производство и спрос не совпадают. За непоставку продукции предприятие будет платить штраф в размере 2 рублей за одно изделие. За перепроизводство предприятие вынуждено хранить продукцию на складе. При этом расходы на хранение составляют 0,5 рубля за одно изделие в течение месяца.

Предприятие планирует разработать оптимальный план производства продукции в течение этих четырёх месяцев. Для этой цели может быть использовано решение транспортной задачи. В этом случае элементы транспортной задачи имеют другие названия. Алгоритм решения при этом не изменяется. Так, пункты отправления продукции заменяются на периоды производства, пункт назначения становится периодом потребления, предложение в пункте отправления заменяется объёмом производства за период, спрос в пункте потребления заменяется на объём реализации продукции за период и, наконец, тариф перемещения продукции представляет собой стоимость единицы продукции, которая рассчитывается как сумма цены продукции, затрат на хранение и штрафа за невыполнение условий поставки. Так, например, при производстве продукции в первом месяце для первого месяца потребления тариф перемещения будет равен цене продукции и составит 20 руб. В то же время при производстве продукции в первом месяце для второго месяца потребления цена продукции увеличится на величину затрат на хранение продукции в течение одного месяца и составит 20 + 0,5 = 20,5 руб. При производстве продукции во втором месяце для погашения задолженности в первом месяце цена продукции увеличится на величину штрафа и составит 20 + 2 = 22 руб.

Учитывая вышесказанное, транспортная модель имеет вид:

–  –  –

В таблице символы 1 м, 2 м, 3 м, 4 м означают месяцы производства и потребления продукции.

Оптимальное решение транспортной задачи, полученное с помощью симплекс-метода, имеет вид:

–  –  –

На основании полученного оптимального решения сформулируем стратегию поведения. Она выглядит следующим образом:

1. Изготовить 150 ед. в первом месяце для первого месяца и 50 ед. для второго месяца.

2. Во втором месяце изготовить 150 ед. для второго месяца.

3. В третьем месяце изготовить 150 ед. для третьего месяца.

4. В четвёртом месяце изготовить 50 ед. для третьего месяца и 150 ед.

для четвёртого месяца.

При этом доход составит:

150 · 20 + 50 · 20,5 + 150 · 20 + 50 · 22 + 150 · 20 = 11125.

Заключение

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

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

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

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

Для нахождения начального опорного решения в методическом пособии были рассмотрены три метода: метод северо-западного угла, метод наименьшей стоимости, метод Фогеля. Наилучшее приближение к оптимальному решению даёт метод Фогеля. Метод наименьшей стоимости по логике должен давать лучшее приближение, чем метод северо-западного угла. Вместе с тем в пособии показано, что это бывает не всегда.

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

Задания для самостоятельной работы

1. Разработать модель транспортной задачи, в которой три пункта производства A, B, C, два транзитных пункта D, E и три пункта потребления F, G, P.

В пунктах A, B, C находится соответственно 100, 200, 300 единиц продукции.

Спрос в пунктах потребления F, G, P составляет соответственно 50, 250, 300 единиц продукции.

За перемещение единицы продукции между пунктами транспортной сети назначены следующие тарифы:

аd = 1, ae = 3, bd = 5, be = 4, cd = 5, ce = 4, df = 6, dg = 6, gf = 4, ep = 10, pg = 7.

Отсутствие тарифа перемещения указывает на невозможность перемещения в данном направлении. Определить оптимальные маршруты и затраты на перемещение продукции.

2. Разработать модель транспортной задачи, в которой три пункта производства A, B, C, два транзитных пункта D, E и три пункта потребления F, G, P.

В пунктах A, B, C находится соответственно 100, 300, 300 единиц продукции.

Спрос в пунктах потребления F, G, P составляет соответственно 150, 250, 300 единиц продукции.

За перемещение единицы продукции между пунктами транспортной сети назначены следующие тарифы:

аd = 10, ae = 30, bd = 5, be = 4, cd = 5, ce = 4, df = 6, dg = 6, gf = 40, ep = 10, pg = 7.

Отсутствие тарифа перемещения указывает на невозможность перемещения в данном направлении. Определить оптимальные маршруты и затраты на перемещение продукции.

3. Разработать модель транспортной задачи, в которой три пункта производства A, B, C, два транзитных пункта D, E и три пункта потребления F, G, P.

В пунктах A, B, C находится соответственно 100, 150, 200 единиц продукции.

Спрос в пунктах потребления F, G, P составляет соответственно 150, 150, 150 единиц продукции.

За перемещение единицы продукции между пунктами транспортной сети назначены следующие тарифы:

аd = 1, ae = 30, bd = 5, be = 4, cd = 5, ce = 4, df = 6, dg = 6, gf = 4, ep = 10, pg = 7.

Отсутствие тарифа перемещения указывает на невозможность перемещения в данном направлении. Определить оптимальные маршруты и затраты на перемещение продукции.

4. Разработать модель транспортной задачи, в которой три пункта производства A, B, C, два транзитных пункта D, E и три пункта потребления F, G, P.

В пунктах A, B, C находится соответственно 100, 150, 200 единиц продукции.

Спрос в пунктах потребления F, G, P составляет соответственно 150, 150, 150 единиц продукции.

За перемещение единицы продукции между пунктами транспортной сети назначены следующие тарифы:

аd = 10, ae = 3, bd = 5, be = 40, cd = 5, ce = 4, df = 66, dg = 6, gf = 4, ep = 10, pg = 70.

Отсутствие тарифа перемещения указывает на невозможность перемещения в данном направлении. Определить оптимальные маршруты и затраты на перемещение продукции.

5. Разработать модель транспортной задачи, в которой три пункта производства A, B, C, два транзитных пункта D, E и три пункта потребления F, G, P.

В пунктах A, B, C находится соответственно 200, 150, 200 единиц продукции.

Спрос в пунктах потребления F, G, P составляет соответственно 150, 250, 150 единиц продукции.

За перемещение единицы продукции между пунктами транспортной сети назначены следующие тарифы:

аd = 10, ae = 3, bd = 5, be = 4, cd = 5, ce = 3, df = 6, dg = 7, gf = 4, ep = 1, pg = 70.

Отсутствие тарифа перемещения указывает на невозможность перемещения в данном направлении. Определить оптимальные маршруты и затраты на перемещение продукции.

6. Разработать модель транспортной задачи, в которой три пункта производства A, B, C, два транзитных пункта D, E и три пункта потребления F, G, P.

В пунктах A, B, C находится соответственно 200, 150, 200 единиц продукции.

Спрос в пунктах потребления F, G, P составляет соответственно 150, 250, 150 единиц продукции.

За перемещение единицы продукции между пунктами транспортной сети назначены следующие тарифы:

аd = 10, ae = 3, bd = 5, be = 4, cd = 5, ce = 3, df = 6, dg = 7, gf = 4, ep = 1, pg = 7, de = 15.

Отсутствие тарифа перемещения указывает на невозможность перемещения в данном направлении. Определить оптимальные маршруты и затраты на перемещение продукции.

7. Разработать модель транспортной задачи, в которой три пункта производства A, B, C, два транзитных пункта D, E и три пункта потребления F, G, P.

В пунктах A, B, C находится соответственно 200, 150, 100 единиц продукции.

Спрос в пунктах потребления F, G, P составляет соответственно 150, 250, 50 единиц продукции.

За перемещение единицы продукции между пунктами транспортной сети назначены следующие тарифы:

ad = 10, ae = 3, bd = 5, be = 4, cd = 5, ce = 3, df = 6, dg = 7, gf = 4, ep = 1, pg = 7, dp = 15.

Отсутствие тарифа перемещения указывает на невозможность перемещения в данном направлении. Определить оптимальные маршруты и затраты на перемещение продукции.

8. Разработать модель транспортной задачи, в которой три пункта производства A, B, C, два транзитных пункта D, E и три пункта потребления F, G, P.

В пунктах A, B, C находится соответственно 200, 150, 100 единиц продукции.

Спрос в пунктах потребления F, G, P составляет соответственно 150, 250, 50 единиц продукции.

За перемещение единицы продукции между пунктами транспортной сети назначены следующие тарифы:

аd = 10, ae = 3, bd = 5, be = 4, cd = 5, ce = 3, df = 6, dg = 7, fg = 4, ep = 1, gp = 7, dp = 15.

Отсутствие тарифа перемещения указывает на невозможность перемещения в данном направлении. Определить оптимальные маршруты и затраты на перемещение продукции.

9. Предприятие производит продукцию, спрос на которую отмечается в течение шести месяцев. Он оценивается соответственно в 150, 200, 200, 150, 200, 100 единиц изделий в месяц. По технологическим причинам предприятие может выпускать в каждом месяце соответственно 200, 150, 150, 200, 100, 200 единиц изделий. Как видно, производство и спрос по месяцам не совпадают. За непоставку продукции предприятие будет платить штраф в размере 12 рублей за одно изделие. За перепроизводство предприятие вынуждено хранить продукцию на складе. При этом расходы на хранение составляют 5 рублей за одно изделие в течение месяца. Цена продукции составляет 30 руб. Определить оптимальную стратегию производства продукции.

10. Предприятие производит продукцию, спрос на которую отмечается в течение шести месяцев. Он оценивается соответственно в 100, 200, 200, 200, 200, 100 единиц изделий в месяц. По технологическим причинам предприятие может выпускать в каждом месяце соответственно 200, 150, 150, 200, 100, 200 единиц изделий. Как видно, производство и спрос по месяцам не совпадают. За непоставку продукции предприятие будет платить штраф в размере 13 рублей за одно изделие. За перепроизводство предприятие вынуждено хранить продукцию на складе. При этом расходы на хранение составляют 4 рубля за одно изделие в течение месяца. Цена продукции составляет 20 руб. Определить оптимальную стратегию производства продукции.

11. Предприятие производит продукцию, спрос на которую отмечается в течение шести месяцев. Он оценивается соответственно в 100, 200, 200, 200, 200, 100 единиц изделий в месяц. По технологическим причинам предприятие может выпускать в каждом месяце соответственно 200, 100, 150, 200, 150, 200 единиц изделий. Как видно, производство и спрос по месяцам не совпадают. За непоставку продукции предприятие будет платить штраф в размере 16 рублей за одно изделие. За перепроизводство предприятие вынуждено хранить продукцию на складе. При этом расходы на хранение составляют 3 рубля за одно изделие в течение месяца. Цена продукции составляет 25 руб. Определить оптимальную стратегию производства продукции.

12. Предприятие производит продукцию, спрос на которую отмечается в течение шести месяцев. Он оценивается соответственно в 100, 200, 250, 200, 250, 100 единиц изделий в месяц. По технологическим причинам предприятие может выпускать в каждом месяце соответственно 200, 150, 150, 250, 150, 200 единиц изделий. Как видно, производство и спрос по месяцам не совпадают. За непоставку продукции предприятие будет платить штраф в размере 26 рублей за одно изделие. За перепроизводство предприятие вынуждено хранить продукцию на складе. При этом расходы на хранение составляют 2 рубля за одно изделие в течение месяца. Цена продукции составляет 30 руб. Определить оптимальную стратегию производства продукции.

13. Имеется 6 видов работ, которые могут быть выполнены шестью организациями. Каждая организация согласна выполнить работы за определённую оплату, которая приведена в таблице:

–  –  –

Найти оптимальное размещение работ по организациям.

14. Имеется водопроводная сеть с семью узлами, в которой два узла (1), (3) являются пунктами поставки воды в объёме соответственно 400 и 300 куб., а два узла (2), (4) – пунктами потребления в объёме соответственно 350 и 350 куб. Стоимость перекачки одного кубометра между узлами составляет: (1)-(2) 10 руб., (1)-(7) 15 руб., (3)-(7) 35 руб., (3)-(4) 45 руб., (7)-(2) 22 руб., (7)-(5) 33 руб., (2)-(6) 5 руб., (6)-(5) 21 руб., (4)-(5) 11 руб. Найти оптимальное решение для перекачки воды.

15. Найти кратчайший путь между узлами (1) и (7) транспортной сети, представленной на рисунке, на основе решения транспортной задачи.

16. Сформулировать транспортную задачу и найти оптимальное решение для автомобильной сети по перевозке продукции. Пункты отправления, пункты спроса и тарифы представлены на рисунке:

–  –  –

1. http://www.uchimatchast.ru/

2. http://xreferat.ru/

3. Таха Х. А. Введение в исследование операций / Х. А. Таха ; пер. с англ. – 7-е изд. – М. : Издательский дом «Вильямс», 2005. – 912 с.: ил. – Парал. тит.

англ.

4. Волков И. К. Исследование операций / И. К. Волков, Е. А. Загоруйко. – М. : Издательство «МГТУ им. Баумана», 2004. – 435 с.

5. Кремер Н. Ш. Исследование операций в экономике / Н. Ш. Кремер. – М. : Издательство «ЮНИТИ», 2006. – 407 с.

–  –  –

План 2013 г., позиция 135. Подписано в печать 29.11.2013.

Компьютерный набор. Гарнитура Times New Roman.

Формат 60х84 1/16. Бумага офсетная. Печать трафаретная.

Усл. печ. л. 3,4. Уч.-изд. л. 3,1. Тираж 120 экз. Заказ №280.

Ухтинский государственный технический университет.

169300, Республика Коми, г. Ухта, ул. Первомайская, д. 13.

Типография УГТУ.

Похожие работы:

«ТЕХНОЛОГИЧЕСКОЕ И ТРАНСПОРТНОЕ ОБОРУДОВАНИЕ РЫБОХОЗЯЙСТВЕННОЙ ОТРАСЛИ УДК 664. 951 (075.8) 633 А.И. Крикун, И.В. Панюкова, С.Д. Угрюмова Дальневосточный государственный технический рыбохозяйственный университет, 690087, г. Владивосток, ул. Луговая, 52б МЕТОДИКА КОМПЛЕКСНОЙ ОЦЕНКИ ЭФФЕКТИВНОСТИ И НАДЕЖНОСТИ ЛИ...»

«131 А.В. Кизим. Постановка и решение задач автоматизации работ УДК 658.27.004.5:681.3:338.001.36 А.В. Кизим Постановка и решение задач автоматизации работ по ремонту и техническому обслуживанию оборудования...»

«ПРОЕКТНАЯ ДЕКЛАРАЦИЯ на строительство двухсекционного жилого дома по ГП-4 (I этап строительства) («Жилой комплекс с подземным паркингом в квартале улиц Фабричная – Мельничная – М.Горького в г.Тюмени), расположенного по адресу: Тюменская область, г.Тюмень, ул.Фабричная Информация о застройщике: Полное наименование органи...»

«Министерство образования и науки РФ Федеральное государственное бюджетное образовательное учреждение высшего профессионального образования Нижегородский государственный технический университет им. Р. Е. Алексеева Кафедра Электрооборудование, электропривод и автоматика ФУНКЦИОНИРОВАНИЕ ОДНОКРИСТАЛЬ...»

«Министерство образования и науки Российской Федерации Федеральное государственное бюджетное образовательное учреждение высшего образования «НИЖЕГОРОДСКИЙ ГОСУДАРСТВЕННЫЙ ТЕХНИЧЕСКИЙ УНИВЕРСИТЕТ ИМ. Р. Е. АЛЕКСЕЕВА» (НГТУ) Институт...»

«Автономный аппаратно-программный комплекс высокочастотного индукционного каротажа Алмаз-1, 2 Инклинометр (АИС) Программное обеспечение RealDepth v 4.4.x Руководство оператора ЛУЧ 22.00.00.00 ПО Новосибирск 2004 г. Данное руководство оператора предназначено для ознакомл...»

«МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РФ КАЗАНСКИЙ ГОСУДАРСТВЕННЫЙ АРХИТЕКТУРНО-СТРОИТЕЛЬНЫЙ УНИВЕРСИТЕТ Кафедра истории и культурологии ИСТОРИЯ Методические указания к семинарским занятиям Часть 2 Россия в XVIII – нач...»

«Генеральный Директор | 10 Октябрь 2013 ОТРАСЛЕВЫЕ РЕШЕНИЯ: СТРОИТЕЛЬСТВО, АГРОПРОМ, ТРАНСПОРТНЫЕ УСЛУГИ Как создать экоферму, выйти на окупаемость и начать тиражировать бизнес Александр Коновалов  Глава крестьянско­фермерского хозяйства основатель и руководитель объединения «Экокластер», д. Степаньково (Шаховской райо...»

«Анализ задач, возникающих при создании нечетких когнитивных карт Гамазов И. Н.1, Терехов В. И.2 Гамазов Иван Николаевич / Gamazov Ivan Nikolaevich – бакалавр, магистрант; Терехов Валерий Игоревич / Terekhov Valery Igorevich – кандидат технических наук, доцент, кафедра системы обработки инфор...»

«ЛАБОРАТОРНЫЕ РАБОТЫ ПО ОРГАНИЧЕСКОЙ ХИМИИ Приведенные в данном разделе работы подготовлены преподавателями кафедры органической химии Санкт-Петербургской государственной лесотехнической академии им....»

«И. В. Челноков, Б. И. Герасимов, В. В. Быковский РЕГИОНАЛЬНАЯ ЭКОНОМИКА: ОРГАНИЗАЦИОННО-ЭКОНОМИЧЕСКИЙ МЕХАНИЗМ УПРАВЛЕНИЯ РЕСУРСАМИ РАЗВИТИЯ РЕГИОНА • ИЗДАТЕЛЬСТВО ТГТУ • МИНИСТЕРСТВО ОБРАЗОВАНИЯ РОССИЙСКОЙ ФЕДЕРАЦИИ ТАМБОВСКИЙ ГОСУДАРСТВЕННЫЙ ТЕХНИЧЕСКИЙ УНИВЕРСИТЕТ ИНСТИТУТ «ЭКОНОМИКА И ПРАВО» И. В. Чел...»

«МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РОССИЙСКОЙ ФЕДЕРАЦИИ САНКТ-ПЕТЕРБУРГСКИЙ НАЦИОНАЛЬНЫЙ ИССЛЕДОВАТЕЛЬСКИЙ УНИВЕРСИТЕТ ИНФОРМАЦИОННЫХ ТЕХНОЛОГИЙ, МЕХАНИКИ И ОПТИКИ ИНСТИТУТ ХОЛОДА И БИОТЕХНОЛОГИЙ Т.В. Меледина, А.Т. Дедегкаев КОЛЛ...»

«Глава VII. Эволюция живого В настоящее время подавляющее большинство ученых считает, что современное разнообразие жизни на Земле сложилось в ходе длительной эволюции. Меняется генетическое разнообразие популяций, эволюционируют виды, сообщества, биогеоцено...»

«База нормативной документации: www.complexdoc.ru МИНИСТЕРСТВО ТРАНСПОРТНОГО СТРОИТЕЛЬСТВА ГОСУДАРСТВЕННЫЙ ВСЕСОЮЗНЫЙ ДОРОЖНЫЙ НАУЧНО-ИССЛЕДОВАТЕЛЬСКИЙ ИНСТИТУТ СОЮЗДОРНИИ МЕТОДИЧЕСКИЕ РЕКОМЕНДАЦИИ ПО ОПРЕДЕЛЕНИЮ ГРУЗОПОДЪЕМНОСТИ ЖЕЛЕЗОБЕТОННЫХ ПРОЛЕТНЫХ СТР...»

«МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РОССИЙСКОЙ ФЕДЕРАЦИИ Федеральное государственное бюджетное образовательное учреждение высшего образования «НАЦИОНАЛЬНЫЙ ИССЛЕДОВАТЕЛЬСКИЙ МОСКОВСКИЙ ГОСУДАРСТВЕННЫЙ СТРОИТЕЛЬНЫЙ УНИВЕРСИТЕТ» УТВЕРЖДАЮ Председатель МК «» _20г. ФОНД ОЦЕНОЧНЫХ СРЕДС...»

«Инновационное развитие, устойчивый рост, модернизация экономики и экономические циклы Innovative development, sustainable growth, modernization of the economy and business cycles Знаменский Владимир Всеволодович, кандидат экономических наук, пр...»

«ХЕКСЕЛЬ Людомир Конрад МЕТОДОЛОГИЯ СОВЕРШЕНСТВОВАНИЯ СОДОВОГО ПРОИЗВОДСТВА НА ОСНОВЕ СИСТЕМНОГО ПОДХОДА 05.13.01 – Системный анализ, управление и обработка информации (химическая технология) АВТОРЕФЕРАТ диссертации на соискание ученой степени доктора технических наук Москва 2008 Работа выполнена...»

«ГОСТ 30547—97 УДК[69+691:699.8](083.74) Группа Ж14 МЕЖГОСУДАРСТВЕННЫЙ СТАНДАРТ МАТЕРИАЛЫ РУЛОННЫЕ КРОВЕЛЬНЫЕ И ГИДРОИЗОЛЯЦИОННЫЕ Общие технические условия ROOFING AND HYDRAULIC INSULATING MATERIALS IN ROLLS General specifications ОКС 83.140 ОКСТУ 5774 Дата введен...»

«ИНФОРМАЦИЯ И НАВИГАЦИЯ НА ОБЪЕКТАХ СОЦИАЛЬНОЙ ИНФРАСТРУКТУРЫ Докладчик: Елена Александровна Латникова заведующий консультативно-экспертным отделением по вопросам формирования д...»

«МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РОССИЙСКОЙ ФЕДЕРАЦИИ Федеральное государственное бюджетное образовательное учреждение высшего профессионального образования «Кузбасский государственный технический университет имени Т.Ф. Горбачева» Кафедра «Финансы и кредит» УТВЕРЖДАЮ Начальник управления реализации...»

«Алексей Павлович КИРЕЕВ, доктор экономических наук, профессор, Международный валютный фонд новое методическое пособие для учителя экономики1 УРОК 3. РынОЧнАя сИстЕМА ЭКОнОМИКИ Основные понятия Разделение труда, других факторов производства, рынок, спрос, закон спроса, предложение, закон предложения, рыноч...»

«УДК 629.331 (470+571) Хегай Юрий Александрович Khegay Yury Aleksandrovich кандидат технических наук, доцент, PhD in Technical Sciences, доцент кафедры экономики и организации Assistant Professor, Depar...»

«АО «Государственный Рязанский приборный завод» АППАРАТ СВАРОЧНЫЙ ПОСТОЯННОГО ТОКА ФОРСАЖ-315М Руководство по эксплуатации ВИАМ.683151.008-01РЭ -2СОДЕРЖАНИЕ 1 Назначение и рекомендации 4 2 Технические характеристики и функции 6 3 Устройство и принцип работы 10 3.1 Прин...»

«Трушина Дарья Борисовна СТРУКТУРА И СВОЙСТВА ЧАСТИЦ ВАТЕРИТА С РЕГУЛИРУЕМЫМ РАЗМЕРОМ И ИХ ПРИМЕНЕНИЕ В КАЧЕСТВЕ ОСНОВЫ НОСИТЕЛЕЙ ДЛЯ ДОСТАВКИ ЛЕКАРСТВЕННЫХ ВЕЩЕСТВ 01.04...»








 
2017 www.pdf.knigi-x.ru - «Бесплатная электронная библиотека - разные матриалы»

Материалы этого сайта размещены для ознакомления, все права принадлежат их авторам.
Если Вы не согласны с тем, что Ваш материал размещён на этом сайте, пожалуйста, напишите нам, мы в течении 1-2 рабочих дней удалим его.