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

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

Алгоритм метода потенциалов

Алгоритм метода потенциалов - раздел Экономика, Конспект лекций Имитационное моделирование экономических процессов   Наиболее Распространенным Методом Решения Транспортных Задач ...

 

Наиболее распространенным методом решения транспортных задач является метод потенциалов.

Решение задачи методом потенциалов включает следующие этапы:

1. разработку начального плана (опорного решения);

2. расчет потенциалов;

3. проверку плана на оптимальность;

4. поиск максимального звена неоптимальности (если условие
п. 3 не было достигнуто);

5. составление контура перераспределения ресурсов;

6. определение минимального элемента в контуре перераспределения и перераспределение ресурсов по контуру;

7. получение нового плана.

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

Для транспортной задачи существует несколько методов отыс­кания начального плана (опорного решения):

- метод северо-западного угла;

- метод минимальной стоимости;

- метод двойного предпочтения и т. д.

Вычислительный алгоритм метода потенциалов рассмотрим на примере решения конкретной задачи прикрепления пунктов от­правления i = к пунктам назначения j = . В соответствии с принятыми обозначениями исходные данные задачи при­ведены в табл. 7.2

 

 

Таблица 7.2 – Исходные данные задачи

Начальный план можно составить одним из перечисленных вы­ше методов. Воспользуемся наиболее простым методом — методом северо-западного угла. В соответствии с этим методом загрузка кле­ток (распределение объемов пунктов отправления по пунктам на­значения) начинается с верхней левой клетки («северо-западная» часть таблицы) и продолжается вниз и вправо (по диагонали).

По указанному правилу загружаем первую клетку (i-j) = (1-1) на основании следующего условия:

Таким образом, первый пункт назначения загружен, а первый пункт отправления имеет остатки груза Δa1 = 60 - 40 = 20, кото­рые и распределяем на второй пункт назначения:

Продолжая преобразования аналогичным образом, получаем:

 

Результаты начального плана и расчета потенциалов представ­лены в табл. 8.3.

Таблица 7.3 – Начальный план перевозок

 

В процессе решения после каждой итерации (в том числе и по­сле получения допустимого решения) по загруженным клеткам про­веряется выполнение следующего условия:

N=m+n-1 (7)

 

В нашем примере m = 3, n=4, а число загруженных клеток равно 6, т. е. соответствует условию (7): N=3 + 4-1=6. Если условие (7) не выполняется, план называется вырожденным. В этом случае в любые свободные клетки надо поставить столько ну­лей, чтобы с их учетом выполнялось условие (7). Клетка, в кото­рой стоит ноль, считается занятой. Значение целевой функции по результатам расчета допустимого плана

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

(8)

где αi, – потенциал i-и строки; βj — потенциал j-го столбца.

Вычисляя потенциалы по выражению (8), принимаем для пер­вой строки

α1 = 0. Используя загруженные клетки (i-j) = (1-1), (1 - 2), получаем:

Далее по загруженным клеткам (2 — 2), (2 — 3) определяем дру­гие потенциалы:

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

(9)

Если для незагруженных клеток условие (9) выполняется, то план — оптимальный. По табл. 3 осуществляем проверку началь­ного плана на оптимальность:

Итак, по трем клеткам условие (9) не выполняется, следова­тельно, начальный план требует улучшения. Характеристики Δcij показывают размер экономии транспортных издержек на 1 ед. пе­ревозимого груза. В нашем примере наибольшую экономию можно получить по клетке (i -j) = (3-1), где Δc31 = 2 > { Δc24; Δc32}. Сле­довательно, клетку (3-1) необходимо загрузить за счет перераспре­деления ресурсов из других загруженных клеток. В табл. 3 клетку (3-1) помечаем знаком «+», так как здесь в начальном плане нахо­дится вершина максимальной неоптимальности.

Контур перераспределения ресурсов составляют по следующим правилам:

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

- ломаная линия должна быть связанной в том смысле, что из лю­бой ее вершины можно попасть в любую другую вершину по
звеньям ломаной цепи (по строке или по столбцу);

- в каждой вершине контура встречаются только два звена, одно
из них располагается по строке, другое — по столбцу;

- число вершин контура четное, все они в процессе перераспреде­ления делятся на загружаемые и разгружаемые;

- в каждой строке (столбце) имеются две вершины: одна — загру­жаемая, другая — разгружаемая.

В этой клетке намечаем одну из вершин контура и далее по вы­шеизложенным правилам строим контур, вершины которого будут находиться в клетках (3—1) — (1—1) — (1—2) — (2—2) — (2—3) — (3—3). Вершины контура последовательно подразделяем на за­гружаемые (З) и разгружаемые (Р), начиная с вершины максималь­ной неоптимальности «+» (табл. 8.3).

Перераспределение ресурсов по контуру осуществляется с це­лью получения оптимального плана. В процессе перераспределе­ния ресурсов по контуру в соответствии с условием неотрицатель­ности переменных xij ни одно из этих значений не должно превра­титься в отрицательное число. Поэтому анализируют только клет­ки, помеченные знаком Р, из которых выбирают клетку с минимальным объемом перевозок. В нашем примере Xmin = min{40; 40; 40} = 40. Следовательно, клетки (1 — 1), (2—2), (3—3) полностью разгружаются. В клетке (1—2) загрузка увеличится на 40 и достиг­нет 60, в клетке (2—3) загрузка составит 40 + 40 = 80, и клетка (3—1) загрузится на 40 (табл. 4).

Проверяем условие N = m + n - 1. В нашем примере m = 3, n =4, а число загруженных клеток равно 4, т. е. условие не выпол­няется и 6 ≠ 4. В процессе перераспределения ресурсов произошла полная разгрузка трех клеток, а мы должны освободить только од­ну клетку. В этом случае следует в две клетки проставить нули (ну­левой ресурс) и считать условно их загруженными. Например, в клетки (1 — 1) и (3—3) проставим нулевой ресурс (табл. 14.4). Получе­ние нового плана (итерации) осуществляется в том же порядке, ко­торый был рассмотрен выше, т. е.

- по загруженным клеткам (в соответствии с новой загрузкой) вычисляются потенциалы αi, и βj ;

- по незагруженным клеткам производится проверка плана на оп­тимальность;

- находится вершина максимальной неоптимальности и строится новый контур перераспределения, и т. д., до тех пор, пока не бу­дет найдено оптимальное решение, удовлетворяющее неравенст­ву (9).

 

 

Таблица 7.4 – Первый план перевозок

 

По результатам первой итерации имеем

Ниже приведены расчеты по второй итерации и оптимальный план.

Поиск потенциалов следующий:

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

Клетку (2-4) необходимо загрузить.

В соответствии с перераспределением ресурсов по контуру по­лучаем табл. 7.5, для которой вновь рассчитываем потенциалы αi, и βj, и последовательность вычислений повторяется.

 

Таблица 7.5 – Оптимальный план перевозок

Для распределения, полученного в табл. 7.5, условие выполняется, следовательно, план — оптимальный.

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

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


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

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

Конспект лекций Имитационное моделирование экономических процессов

ГОУ ВПО Кубанский государственный технологический.. Универсистет Кафедра вычислительной техники и АСУ..

Если Вам нужно дополнительный материал на эту тему, или Вы не нашли то, что искали, рекомендуем воспользоваться поиском по нашей базе работ: Алгоритм метода потенциалов

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

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

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

Понятие имитационного моделирования
  Имитационное моделирование (ИМ) – распространённая разновидность аналогов моделирования, реализуемого с помощью набора математических инструментальных средств, специальных имитирующ

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

Типовые задачи, решаемые средствами компьютерного моделирования
  - моделирование процессов логистики для определения временных и стоимостных параметров; - управление процессом реализации инвестиционного проекта на различных этапах его жи

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

Определение параметров линейного однофакторного уравнения регрессии
Пусть у нас имеются данные о доходах ( x ) и спросе на некоторый товар ( y ) за ряд лет ( n ): Год i Доход x

Оценка величины погрешности линейного однофакторного уравнения
  1. Обозначим разность между фактическим значением результативного признака и его расчетным значением как u i :

Проблема автокорреляции остатков. Критерий ДарбинаУотсона
  Часто для нахождения уравнений регрессии используются динамические ряды, т.е. последовательность экономических показателей за ряд лет (кварталов, месяцев), следующих друг за другом.

Двухфакторные и многофакторные уравнения регрессии
  Линейное двухфакторное уравнение регрессии имеет вид где a , b 1 , b

Конструирования целевой функции
  Допустим, объект оптимизации описывается следующей системой уравнений: х2 + у2 = 1 х + у = 1 Графически эту систему можно представит

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

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

Оптимизационные задачи с линейной зависимостью между переменными
  Пусть: b i количество ресурса вида i ( i = 1, 2, ..., m ); a i , j норма расхода

Геометрическая интерпретация ОЗЛП
  Пусть необходимо найти оптимальный план производства двух видов продукции ( x 1 и x 2 ), т.е. такой план, при котором целевая функция (общая приб

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

Решение двойственной задачи ЛП
  Оптимизационная модель прямой задачи линейного программирования выглядит так: В системе неравенств должны

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

Одноканальная смо с ожиданием
Система массового обслуживания имеет один канал. Входящий поток заявок на обслуживание — простейший поток с интенсивно­стью λ,. Интенсивность потока обслуживания равна μ, (т. е. в сред­не

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

Непрерывное моделирование
  Непрерывное моделирование — это моделирование системы по времени с помо­щью представления, в котором переменные состояния меняются непрерывно по отношению ко времени. Как правило, в

Теоретические основы метода
  Метод статистического моделирования (или метод Монте-Кар­ло) — это способ исследования поведения вероятностных систем (экономических, технических и т. д.) в условиях, когда не извес

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

Постановка задачи
  Компании, продающей один вид продукции, необходимо определить, какое коли­чество товара она должна иметь в запасе на каждый из последующих n мес. (n — заданный входной параметр). Пр

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

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

Принятие решений в условиях риска
  Основными критериями оценки принимаемых решений в усло­виях риска являются: - ожидаемое значение результата; - ожидаемое значение результата в сочетании с минимиза

Принятие решений в условиях неопределенности
    Неопределенность является характеристикой внешней среды (природы), в которой принимается управленческое решение о раз­ витии (или функционировании) экономиче

Критерий Лапласа
Этот критерий опирается на «принцип недостаточного основания» Лапласа, согласно которому все состояния «природы» Si, i = 1,n полагаются равновероятными. В соответствии с этим прин­ципом каждому сос

Теория игр
8.5.1 Общие понятия   В конфликт­ных ситуациях имеются противодействующие стороны, интересы которых противоположны. При конфликтных ситуациях решения принима

Метод линейного программирования для нахождения оптимальных стратегий в играх двух лиц с нулевой суммой
  Пусть игра m×n не имеет оптимального решения непосредст­венно в чистых стратегиях, т. е. отсутствует седловая точка (α ≠ β). Оптимальное решение необходимо иск

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