рефераты конспекты курсовые дипломные лекции шпоры

Реферат Курсовая Конспект

Открытая (не сбалансированная) модель ТЗ.

Открытая (не сбалансированная) модель ТЗ. - Лекция, раздел Науковедение, Курс лекций по дисциплине: МЕТОДЫ ИССЛЕДОВАНИЯ ОПЕРАЦИЙ Открытая Модель Сводится К Закрытой. Если Суммарная Мощность Поставщика Больш...

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

 

Например:

Nj Mi
 
 
 

 

Суммарная мощность поставщиков:

40+60+50=150

Суммарный спрос потребителей:

30+40+60=130

Модель открытая(несбалансированная). Вводим фиктивный потребитель, которому присваиваем спрос: 150-130=20.

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

 

Nj Mi
 
 
 

 

 

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

2.6 Задача о назначениях.

Эта задача является частным случаем ТЗ, в этом случае число поставщиков равно числу потребителей. Мощность каждого поставщика и спрос каждого потребителя равен 1. Решается задача венгерским методом. Различают задачи:

-минимизация целевой функции;

-максимизация целевой функции;

Минимизация целевой функции:

Алгоритм решения задачи:

1) В каждой строке матрицы задачи находим минимальных элемент и вычитаем его из всех элементов строки;

2) В каждом столбце полученной матрицы находим минимальный элемент и вычитаем его из всех элементов столбца.

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

4) Находим столбец с одним нулем и отмечаем этот элемент, а в строке, где находится отмеченный нуль, все остальные нули зачеркиваются.

5) Если после шагов (3) и (4) еще есть неотмеченный нули, то отмечаем любой из них, и в строке и в столбце с отмеченным нулем, все остальные нули зачеркиваются.

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

7) Если в какой- нибудь строке или столбце отсутствует отмеченный нуль, проводим минимальное число пересекающихся горизонтальных и вертикальных прямых через все отмеченные нули. Среди не зачеркнутых этими прямыми чисел находим минимум. Этот минимум вычитается из всех не зачеркнутых чисел и прибавляется ко всем числам на пересечении прямых. К полученной матрице применяется выше описанный алгоритм, начиная с шага (3).

 

Пример:

 

Существует 4 базы А1, А2 , А3 , А4 и 4 потребителя B1, B2, B3, B4. Расстояние от баз до потребителей задано матрицей:

 

 

 

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

Решение:

П1 П2 П3 П4

0 2 0 0 (по строкам) (по столбцам)

 
 
10 20 12 5 5 5 15 7 0 5 13 7 0 5 13 7 0

3 14 9 1 1 2 13 8 0 2 11 8 0 2 11 8 0

 
 
13 8 6 9 6 7 2 0 3 7 0 0 3 7 0 0 3

 
 
7 15 8 10 7 0 8 1 3 0 6 1 3 0 6 1 3

Больше нет нулей.

 

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

 

                                   
   
     
           
         
 
 
 
 
 
 

 
 
5 13 7 0 6 14 7 0 8 13 7 0

 
 
2 11 8 0 применим 2 11 8 0 применим 2 11 5 0 применим

 
 
7 0 0 3 алгоритм с П3,П4. 7 0 0 2 алгоритм с П3,П4 7 0 0 0 алгоритмП3,П4

 
 
0 6 1 3 0 6 0 2 0 6 0 0

min(8,3,1,3)=1 min (7,2,2)=2; min=5

 
       
   
 
 

 
13 21 7 0

 
2 11 0 0

 
7 0 0 0

0 6 0 0

       
   


Это оптимальное решение, возможно не единственное.

А1 прикрепляется к В4 -5

А2 прикрепляется к В3 -9

А3 прикрепляется к В2 -8

А4 прикрепляется к В1 -7

 

 

Для нахождения суммарного расстояния надо сложить числа из исходной матрицы на месте нулей:

5+9+8+7=29

Максимизация целевой функции:

В этом случае задача сводится к задаче минимизации для матрицы, полученной из исходной матрицы, умноженной на -1.

 

Тема III. Динамическое программирование.

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

Динамическое программирование применяется для решения задач мелкого масштаба (по сравнению с методами линейного программирования).

 

– Конец работы –

Эта тема принадлежит разделу:

Курс лекций по дисциплине: МЕТОДЫ ИССЛЕДОВАНИЯ ОПЕРАЦИЙ

ФЕДЕРАЛЬНОЕ АГЕНСТВО ПО ОБРАЗОВАНИЮ... МОСКОВСКИЙ ГОСУДАРСТВЕННЫЙ СТРОИТЕЛЬНЫЙ УНИВЕРСИТЕТ... Курс лекций по дисциплине...

Если Вам нужно дополнительный материал на эту тему, или Вы не нашли то, что искали, рекомендуем воспользоваться поиском по нашей базе работ: Открытая (не сбалансированная) модель ТЗ.

Что будем делать с полученным материалом:

Если этот материал оказался полезным ля Вас, Вы можете сохранить его на свою страничку в социальных сетях:

Все темы данного раздела:

Экономико-математическая модель. ТЗ
Транспортные задачи(ТЗ)- частный случай задачи линейного программирования. В ТЗ существуют поставщики и потребители грузов. У каждого поставщика имеется определенное количест

Метод северо-западного угла.
С помощью метода северо-западного угла реализуется первоначальный план поставок.   Таблица 2.1   Nj M

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

Постановка задачи динамического программирования.
Рассматривается управляемый процесс. В результате управления система (объект управления) приводится из начального состояния S0 в конечное S(S0 → S). Предположим, что упр

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

Задачи замены оборудования без приведения затрат к текущему моменту времени.
1) Постановка задачи: В эксплуатации находятся оборудование, цена нового оборудования S. Известны затраты на эксплуатацию оборудования С t зависящие от времени. В результ

Задачи замены оборудования с учетом приведения затрат к текущему моменту времени.
  1) Постановка задачи: В эксплуатация находится с первоначальной ценой S. Известны затраты на эксплуатацию оборудования в периоды 1, 2, 3 . . . t - С1, С

Детерминированные задачи упорядочивания.
  1) Постановка задачи: Имеется несколько изделий, каждое из которых надо обработать на двух машинах последовательно (сначала на первой, потом на второй). Известны вре

Решение игры с седловой точкой.
  B1 B2 А1 -4 А2

Смешанные стратегии.
Рассмотрим пример;   В1 В2 min А1

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

Решение игры 2хn.
Самым удобным способом для определения оптимальной стратегии игроков в игре 2хn является графическим способом.   Пример:  

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

Простейший пуассоновский поток событий.
Для простейшего потока справедливы три свойства: 1) Стационарность потока λ = const. Интенсивность λ – частота появления события или среднее число событий, поступающих в СМО в ед

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

Уравнение Колмогорова для простейшего потока событий.
Особый интерес представляют вероятности системы Рi(t) в предельном стационарном режиме, т.е. при t→∞, которые называются предельными вероятностями состояний. Т.к. пр

Системы массового обслуживания с отказом.
В качестве показателей эффективности СМО с отказами будет рассматривать: А – абсолютную пропускную способность СМО, т.е. среднее число заявок, обслуживаемых системой в единицу времени;

Системы массового обслуживания с ожиданием
В качестве показателей эффективности СМО с ожиданием, кроме уже известных показателей – абсолютной А и относительной Q пропускной способности, вероятности отказа ρотк, среднего числ

Хотите получать на электронную почту самые свежие новости?
Education Insider Sample
Подпишитесь на Нашу рассылку
Наша политика приватности обеспечивает 100% безопасность и анонимность Ваших E-Mail
Реклама
Соответствующий теме материал
  • Похожее
  • Популярное
  • Облако тегов
  • Здесь
  • Временно
  • Пусто
Теги