Математические модели решения транспортной задачи и задачи о назначениях Теория

принятия решений
[Номер и название специальности]
Институт МБЭ, кафедра ММ
Мазелис А.Л.

количествах ai (i=1…m)
Множество J, включающее n пунктов потребления, в каждом

из которых имеется спрос на данный груз в количестве bj (j=1…n)
Затраты cij на перевозку единицы груза между пунктами i и j

пунктов отправления перевозится в пункты потребления с минимальными издержками, а

спрос удовлетворяется полностью

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

симплексным методом,
Однако есть более эффективные способы её решения.

перераспределения)
3.Проверка оптимальности
5.Конец
Нет
Да

n+m–1
В оптимальном плане все переменные, кроме n+m–1, будут свободными

=>равными нулю
Метод северо-западного угла
Не использует данных о затратах
Обычно приводит к распределению, требующему много корректировок

то i ← i+1; иначе j ← j+1

4. Если i>m, то

процесс завершён; иначе переход к 2

Начальное распределение получено!

Ещё не вывезенный остаток

Ещё не удовлетво-рённый спрос

= vj – ui
Расчёт потенциалов:
подобрать такие vj и ui,

чтобы уравнение потенциалов выполнялось для всех базисных клеток (перевозок)

множество столбцов J’ с ненулевыми перевозками и нерассчитанными потенциалами
Для всех

j  J’ выполняем vj  ui + cij
В столбце j находим множество строк I’ с ненулевыми перевозками и нерассчитанными потенциалами.
Для всех i  I’ выполняем ui  vj – cij
Выполняем (2)
Процесс закончен, когда I’ или J’ оказывается пустым

Начальное распределение получено!

у потребителя j и у поставщика i равна стоимости перевозки

(это следует из способа расчёта потенциалов)
Неиспользуемая перевозка cij выгодна, если разница в «ценах» (потенциалах) у потребителя j и у поставщика i больше стоимости перевозки
Условие оптимальности
Разница в потенциалах потребителя и поставщика по всем неиспользуемым перевозкам не больше стоимости перевозки

для 1  2.
Значит, требуется переход к п.4. – корректировка

плана

Проверка оптимальности

над стоимостью транспортировки как правило, с наибольшим.
2.Строим контур (см. схему),

начиная с данной клетки
3.Помечаем вершины контура знаками «+» и «–»
начинаем со знака «+» в выбранной свободной клетке.
4.Находим наименьшую из величин в клетках со знаком «–»
5.Вычитаем её из всех клеток «–» и прибавляем ко всем клеткам «+»
6.Одну из клеток, в которых оказался нуль, объявляем свободной.
Переходим к проверке критерия оптимальности

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

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

принимается равным потерям, возникающих из-за неудовлетворённого спроса.
«Перевозки» от фиктивного поставщика

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

работе j
Оптимальное назначение работников на работы, максимизирующее добавленную стоимость

поставщиков, располагающих ед. ресурсами
=> работники
имеется n потребителей с единичным спросом

=> работы
стоимость перевозок равна добавленной стоимости, взятой со знаком «-» ( чтобы добавленная стоимость максимизировалась)
Решается методом потенциалов: «Перевозки единичного объёма груза» интерпретируются как назначение работника i на работу j (Все базисные переменные в этом случае могут принимать только единичные значения)

указать соответствующие диапазоны, можно воспользоваться кнопками свертывания, расположенными справа от

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

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

Поиск решения. Надстройка в Excel, которая может оптимизировать табличные модели ЛП.
Ограничения. Математические выражения в форме неравенства или равенства, которому должны удовлетворять переменные модели.
Переменные решения. Переменные, значениями которых управляет человек, принимающий решение.

составляет план перевозок на следующий месяц. Цены перевозок, заказы и

запасы показаны в таблице. Видно, что запасы продукции на складах фирмы в следующем месяце превысят заказы так, что часть продукции останется на складах.S1, S2 .. S4.

перевозок, минимизирующий издержки и найдите остатки товаров на каждом из

складов фирмы в конце месяца. Учтите, перевозки по маршруту S2-D9 в это время будут невозможны.

на 5 типовых операций (D1,D2,... D5) 5 из 7 рабочих

(S1,S2..S7). Время, которое каждый рабочий тратит на выполнение каждой операции приведено в таблице. Определите оптимальную расстановку рабочих по операциям, при которой суммарное время на выполнение работ будет минимально, принимая во внимание, что рабочий S1 не может выполнять операцию D1 в течение некоторого времени в связи с травмой.

маркетеров. – М.: Ассоциация авторов и издателей "Тандем". Изд-во "Гном-пресс",

1997. – 256 с.
2. Арнольд И.В. Лексикология современного английского языка: Учебник для вузов – Ленинград: Ленинградская школа английской лингвистики, 1959. – 312 с.
3. Новоселов М.М. Логика // Философский энциклопедический словарь. – М.: Сов. энциклопедия, 1983. – C. 310–319.

соблюдения требований законов РФ об авторском праве и интеллектуальной собственности,

а также с учетом требований настоящего Заявления.

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