Студопедия

Главная страница Случайная страница

Разделы сайта

АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника






  • Как продвинуть сайт на первые места?
    Вы создали или только планируете создать свой сайт, но не знаете, как продвигать? Продвижение сайта – это не просто процесс, а целый комплекс мероприятий, направленных на увеличение его посещаемости и повышение его позиций в поисковых системах.
    Ускорение продвижения
    Если вам трудно попасть на первые места в поиске самостоятельно, попробуйте технологию Буст, она ускоряет продвижение в десятки раз, а первые результаты появляются уже в течение первых 7 дней. Если ни один запрос у вас не продвинется в Топ10 за месяц, то в SeoHammer за бустер вернут деньги.
    Начать продвижение сайта
  • Переход от открытой ТЗ к закрытой ТЗ






    Если задача является открытой, то необходимо провести процедуру закрытия задачи. С этой целью при a < b добавляем фиктивного поставщика A'm+1 с запасом груза a' m+1 = b – a. Если же a > b, то добавляем фиктивного потребителя B' n+1 с заказом груза b'n+1 = a – b. В обоих случаях соответствующие фиктивным объектам тарифы перевозок c'ij полагаем равными нулю. В результате суммарная стоимость перевозок z не изменяется.

    Решение ТЗ разбивается на два этапа:

    1. Определение начального допустимого базисного решения (первоначального опорного плана) – первоначального распределения поставок.

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

    Существует несколько способов нахождения опорного плана (исходного решения).

    1) Метод «северо-западного» угла (диагональный метод) за­ключается в заполнении клеток таблицы таким образом, чтобы последовательно закрывались столбцы таблицы.

    Заполнение таблицы начнем с клетки (1, 1). Так как х11 = min{300, 200} = 200, то первый столбец закрыт, при этом оста­ток на базе А составляет 100 единиц.

    Рассмотрим заполнение второго столбца таблицы. Так как потребности пункта № 2 со­ставляют 250 единиц, то они могут быть удовлетворены поставкой из базы А 100 единиц и из базы В 150 единиц. Таким образом, x12=min{300-200, 250} = 100, a х22 = min{250-x12, 250} = min{150, 250} = 150. Заполнение второго столбца закончено.

    Переходим к заполнению третьего столбца. Потребности пункта № 3 составляют 250 единиц, наличие на базе В составляет 350 - х22 = 200 единиц, поэтому удовлетворение потребности пункта № 3 возможно поставками с базы В 200 единиц и с базы С 50 единиц, т. е. х23=200, а х33 = min{250-x23, 250] = 50, остаток на базе С 400 - х33 = 400 - 50 = 350 единиц. Заполнение третьего столбца закончено.

    Переходим к заполнению четвертого столбца. Так как потребности пункта № 4 — 350 единиц, то они полно­стью удовлетворяются поставкой с базы С, поэтому х34 = 350 (табл. 1).

    Таблица 1

    Остатки по столбцам и строкам равны нулю, следовательно, опорное решение построено. Этому опорному решению соответ­ствуют затраты:

    L = 1∙ 200 + 2∙ 100 + 8∙ 150 + 4∙ 200 + 9∙ 50 +1∙ 350 = 3200 (денежных единиц).

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

    Этот недостаток может быть устранен методом «минималь­ного элемента», который заключается в том, что при построении опорного решения (плана) учитывается величина затрат. Постро­им опорное решение данной задачи, применяя метод «минималь­ного элемента».

     

    2) Метод «минимального элемента»

    Построение опорного решения начнем с клетки, имеющей наименьшую стоимость. Таких клеток две: (1, 1) и (3, 4), значение стоимости в каждой из них равно 1. Рассмотрим клетку (1, 1). В эту клетку заносим значение х11 = 200, тем самым полностью закрывая первый столбец. В клетку (3, 4) заносим значение х34 = 350, закрывая четвертый столбец.

    Остатки по первой и третьей строкам равны соответственно 100 и 50 единицам (табл. 2).

      Таблица 2 Рассмотрим следующие клетки с наименьшей стоимостью: это клетка (1, 2) со стоимостью в две денежных единицы, клетка (2, 3) со стоимостью в четыре денежных единицы. Рассмотрим клетку (1, 2). Так как остаток по первой строке равен 100, то зна­чение х 12 = 100. Рассмотрим клетку (2, 3), значение х23 = 250. Таким образом, первая строка и третий столбец закрыты полно­стью (табл. 3).
    Таблица 3     Из таблицы 3 видно, что необходимо закрыть второй столбец, что достигается значениями х22 = 100 и х32 = 50. Теперь закрыты все строки и столбцы, и найдено опорное решение (ис­ходный план) (табл. 4).  
             

     

    Таблица 4   Этому плану соответствуют затраты: L = 1∙ 200 + 2∙ 100 + 8∙ 100 + 10∙ 50 + 4∙ 250 +1∙ 350 = 3050 (д. ед).  
    Таким образом, найдены два опорных решения (опорных плана) (см. табл. 1 и 4). Перейдем к нахождению оптималь­ного плана, что достигается построением новых опорных реше­ний, улучшающих друг друга.





    © 2023 :: MyLektsii.ru :: Мои Лекции
    Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав.
    Копирование текстов разрешено только с указанием индексируемой ссылки на источник.