Дмитриева С.И. Управление денежными, материальными и информационными потоками (1084311), страница 15

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

Текст из файла (страница 15)

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

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

6.3. Пример решения транспортной задачи венгерским методом

Задача 3

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

Ниже приводится цепочка матриц, получаемых в процессе решения задачи, с соответствующими пометками. Снятие знака выделения «+» отмечено заключением его в рамку. Цепочка на этапе 2 отмечается стрелками.

Оптимальный вариант назначений х₁₁ = х₂₄ = х₃₅ = х₄₃ = х₅₂ = 1, остальные Хij = 0, т. е. первый исполнитель назначается на первую работу, второй — на четвертую, третий — на пятую, четвертый — на третью, пятый — на вторую. Соответствующая ему суммарная производительность 4 + 4 + 4 + 6 + 4 = 22.

Пояснения к решению задачи.

Процесс нахождения оптимального варианта назначений состоит из предварительного этапа и двух итераций.

Предварительный этап

На этом этапе осуществляются два последовательных преобразования матрицы С. Сначала находится максимальный элемент в каждом столбце: в первом столбце максимальный элемент равен 5, во втором — 4, в третьем — 6, в четвертом — 5, в пятом — 5. Из максимального элемента вычитаются элементы этого столбца. Получается неотрицательная матрица, в каждом столбце которой есть хотя бы один нуль. Затем из каждой строки полученной матрицы вычитаем минимальный элемент этой строки. В результате подготовительного этапа Осуществлен переход к неотрицательной матрице, в каждом столбце и каждой строке которой имеется хотя бы один нуль.

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

Итерация 1

Этап 1

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

Далее, отмечаем штрихом нуль, расположенный в четвертом столбце и во второй строке. Поскольку во второй строке имеется О* во втором столбце, то выделяем вторую строку и снимаем знак выделения над вторым столбцом. Так как во втором столбце имеются невыделенные нули, отмечаем нуль этого столбца, расположенный в пятой строке. Пятая строка матрицы не содержит О*. Следовательно, имеет место случай (б) (исход IA), т. е. необходим переход к этапу 2.

Этап 2

Строим цепочку. От последнего нуля со штрихом (пятая строка, второй столбец) движемся по столбцу к нулю со звездочкой (второй столбец, вторая строка), затем от 0* — к 0', расположенному в этой же строке в четвертом столбце. Поскольку в четвертом столбце матрицы нет 0*, процесс образования цепочки закончен. Искомая цепочка состоит из элементов: 0'₅₂, 0*₂₂, 0'₂₄. Для завершения этапа 2, а вместе с ним и первой итерации, необходимо поставить звездочки над нулями цепочки, отмеченными штрихами, уничтожить звездочку над единственным четным элементом цепочки и стереть все знаки выделения. В результате итерации / число независимых нулей увеличилось на единицу и стало равно 4.

Итерация 2

Этап 1

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

Этап 2

Минимальным из числа невыделенных элементов матрицы является единица. Поэтому из всех элементов невыделенных строк (первой, второй, третьей, пятой) вычитаем h = 1, а к элементам выделенных столбцов (второго, четвертого, пятого) прибавляем h = 1. Получается матрица, эквивалентная предыдущей и содержащая незанятые нули. Переносим все знаки выделения (+,*,') с предыдущей матрицы, кроме знаков, обведенных рамкой, и переходим к этапу 1.

Этап 3

Отмечаем штрихом невыделенный нуль первого столбца первой строки, так как в первой строке имеется 0* в пятом столбце, выделяем первую строку и снимаем знак выделения над пятым столбцом. В пятом столбце имеется невыделенный нуль, расположенный в третьей строке, отмечаем его штрихом. Поскольку в третьей строке нет нулей со звездочкой (случай (б)), переходим к этапу 2.

Этап 4

Строим цепочку. От последнего 0' (третья строка, пятый столбец) движемся по столбцу до 0*, расположенного на пересечении первой строки и пятого столбца, далее от 0* — к 0', находящемуся в этой же строке в первом столбце, затем по первому столбцу к 0* (четвертая строка, первый столбец) и по строке 4 к 0', расположенному в третьем столбце. Так как в третьем столбце нет 0*, процесс образования цепочки закончен. Искомая цепочка состоит из элементов: 0'₃₅, 0*₁₅, 0'₁₁, 0*_4], 0'₄₃. Снимаем звездочки у нулей из цепочки и заменяем звездочками штрихи у нулей из цепочки. В результате второй итерации число независимых нулей увеличилось на единицу и стало равно 5, поэтому процесс решения задачи закончен.

6.4. Решение транспортной задачи методом

«северо-западного угла»

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

Имеется т поставщиков определенного вида продукции (либо т — количество мест, складов, откуда происходит поставка продукции). Максимальные объемы возможных поставок заданы и равны соответственно a_i, ,i=1, 2,..., т. Эта продукция используется п потребителями. Объемы потребностей заданы и равны соответственно b_{j ,} j= 1, 2,..., п. Стоимость перевозки единицы продукции от i-го поставщика к j-му потребителю известна для всех i,j и равна Cij_,.

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

Задача 4

На двух складах (А и В) имеется соответственно 50 и 40 т продукции.

Таблица 6.4.1

Исходные данные для решения транспортной задачи

Стоимость перевозки от складов к потребителям приведена в табл. 1 (в правом верхнем углу каждой клетки). Например, стоимость перевозки единицы (1т) груза со склада А потребителю С равна 3 у.е.

Спланируйте перевозки к трем потребителям (С, D и Е) так, чтобы потребитель С получил 30 т груза, потребитель D — 20 т, потребитель Е — 40 т, а затраты на перевозку были минимальными.

Для решения задачи на первом этапе составляется система ограничений и целевая функция. Система ограничений в общем виде (для нашей задачи) имеет вид

причем Хij > 0 для i = 1, 2; j = 1, 2, 3.

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

Далее перераспределяются объемы поставок методом “северо-западного угла”, т.е. первой заполняется верхняя левая (северо-западная) клетка исходной таблицы.

Примем объем перевозки со склада А к потребителю С максимально возможным из условий задачи и равным 30 т. Потребитель С полностью удовлетворил свою потребность, и поэтому графу «С» в табл. 1 можно исключить из дальнейшего рассмотрения.

В таблице 1 найдем «северо-западный угол» (теперь это клетка AD) и укажем максимально возможное значение. Оно рассчитывается следующим образом: со склада А уже перевезено 30 т груза, поэтому остаток на этом складе составляет 20 т (50—30). Вносим в клетку AD вместо X12 значение, равное 20 т. Таким образом, весь груз со склада А перевезен потребителям и первая строка табл. 1 исключается из дальнейшего рассмотрения. Потребитель D полностью удовлетворил свою потребность в грузе, и графу D можно исключить из дальнейшего рассмотрения. В оставшейся части табл. 1 найдем новый «северо-западный угол» (клетка BE) и укажем в нем максимально возможное значение (40 т). В результате (в табл. 2) получено следующее распределение поставок: x₁₁= 30; x₁₂ = 20; x₂₃ = 40.

Таблица 6.4.2

Распределение поставок

Значение целевой функции будет иметь вид

(руб.).

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

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

Задача 1

В Вашу консультационную фирму обратилась голландская компания с вопросом: где ей выгоднее закупать комплектующие: в Европе или в Юго-Восточной Азии?

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

• удельная стоимость поставляемого груза — 4000 долл. США/куб. м;

• транспортный тариф — 170 долл. США/куб, м;

• импортная пошлина на товар из Юго-Восточной Азии —12%;

• ставка на запасы: в пути — 3%, страховые у — 0,8%;

• стоимость товара: в Европе — 116 долл. США, в Юго-Восточной Азии — 98.

Дайте ответ голландской компании.

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

Список файлов книги