Исследование операций на примере ОАО "АвиаМоторс"
Дипломная работа - Менеджмент
Другие дипломы по предмету Менеджмент
?сключается либо i-й поставщик, , , либо j-й потребитель, , .
Таблица 2.2: Нахождение решения методом северо-западного угла
Запасы постав. ,biЗапросы потребителей, аj5001201802004909 490 13201131023 105 1209 1801820018 9 12 13 200Определим затраты на перевозки по формуле
F= (2.13)
F1=
Вывод: стоимость перевозок для компании ОАО АвиаМоторс, найденная по методу северо-западного угла составляет F1=9460.
.б. Метод наименьшей стоимости
Метод минимальной стоимости позволяет построить опорное решение, достаточно близкое к оптимальному, так как использует матрицу стоимостей транспортной задачи , ,. Как и метод северо-западного угла, он состоит из ряда однотипных шагов, на каждом из которых заполняется только одна клетка таблицы, соответствующая минимальной стоимости , и исключается из рассмотрения только одна строка (поставщик) или один столбец (потребитель).
Очередную клетку, соответствующую, заполняют по тем же правилам, что и в методе северо-западного угла. Поставщик исключается из рассмотрения, если его запасы использованы полностью. Потребитель исключается из рассмотрения, если его запросы удовлетворены полностью. На каждом шаге исключается либо один поставщик, либо один потребитель. При этом если поставщик еще не исключен, но его запасы равны нулю, то на том шаге, когда от данного поставщика требуется поставить груз, в соответствующую клетку таблицы заносится базисный нуль и лишь, затем поставщик исключается из рассмотрения. Аналогично с потребителем.
2. Метод потенциалов
В зависимости от состояния между суммарными запасами груза и суммарными в нем запросами, транспортные задачи могут быть открытыми и закрытыми.
Если сумма запасов груза равна суммарной потребности, то есть то транспортная задача называется закрытой.
Клетки, в которые поместим грузы называются закрытыми, им соответствуют базисные переменные опорного решения. Остальные клетки пустые, им соответствуют переменные. При распределении грузов может оказаться, что количество занятых клеток меньше чем m+n-1. В этом случае недостающее их число заполняется клетками с нулевыми поставками. Такие клетки называются условно занятыми. Такая транспортная задача называется выраженной. В нашей задаче число заполненных клеток равно 5, m + п - 1 = 6, следовательно, задача является вырожденной.
Таблица 2.4 Нахождение решения методом потенциалов
Запасы постав., b iЗапросы потребителей, аjui5001201802004909 490 13 20 11031023 105 1209 18018 0-1420018 9 12 13 200-9Vj9-9-54
Строим систему потенциалов, соответствующих опорному решению. Для этого решим системы уравнений:
(2.14)
Для того чтобы найти частное решение системы, одному из потенциалов задаем произвольно некоторое значение, равное нулю.
Пусть u1 = 0
u1 + 9 = v1v1 = 9
u2 + 23 = v1u2 = 9-23=-14
u2 + 5 = v2=>v2 = -14+5=-9+ 9 = v3v3 = -14+9=-5+ 18 = v4v4 = -14+18=4+ 13 = v4u3 = 4-13=-9
Составим матрицу оценок, где
(2.15)
D =
Так как матрица положительная, то мы получили план перевозок, полностью удовлетворяющий партнеров и обеспечивающий минимум затрат на перевозку продукции.
Вывод: стоимость перевозок для компании ОАО АвиаМоторс, найденная по методу потенциалов составляет F3=9460, и F1= F2= F3.
Минимальные затраты на перевозки машин марки BMW от компании ОАО АвиаМоторс в филиалы, находящиеся в Екатеринбурге Bayerhof ул. Блохера 45, Перми Верра- Моторс ул. Героев Хасана 81, Самаре Aldis ул. Демократическая 65 и Нижнем Новгороде ТрансТехСервис ул. Бринского 12, равны 9460, что подтверждается тремя методами.
3. Задача динамического программирования
Динамическое программирование (ДП) - это вычислительный метод для эффективного решения задач с пересекающимися подзадачами. Возникло и сформировалось в 1950 - 1953 гг. благодаря работам Р. Беллмана.
Динамическим программированием (в наиболее общей форме) называют процесс пошагового решения задач, когда на каждом шаге выбирается одно решение из множества допустимых (на этом шаге) решений, причем такое, которое оптимизирует заданную целевую функцию или функцию критерия. В основе теории динамического программирования лежит принцип оптимальности Беллмана: каково бы ни было начальное состояние на любом шаге и решение, выбранное на этом шаге, последующие решения должны выбираться оптимальными относительно состояния, к которому придет система в конце данного шага. Использование этого принципа гарантирует, что решение, выбранное на любом шаге, является не локально лучшим, а лучшим с точки зрения задачи в целом.
Динамическое программирование решает задачу, разбивая её на подзадачи и объединяя их решения. Рекурсивные алгоритмы также делят задачу на независимые подзадачи, эти подзадачи - на более мелкие подзадачи и так далее, а затеи собирают решение основной задачи снизу вверх. Динамическое программирование применимо тогда, когда подзадачи не являются независимыми, иными словами, когда у подзадач есть общие подподзадачи. В этом случае при использовании рекурсии будут решаться одни и те же подзадачи несколько раз. Формы алгоритма динамического программирования могут быть разными - общим для них является заполняемая таблица и порядок формирования ее элементов.
Алгоритм, основанный на динамическом программировании, решает каждую из подзадач только один раз и запоминает ответы в специальной таблице. Это позволяет не вычислять заново ответ к уже встречавшейся подзадаче. Типичными для динамического прогр?/p>