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

Описание алгоритма решения Т-задачи

Читайте также:
  1. FAST (Методика быстрого анализа решения)
  2. I. 2.1. Графический метод решения задачи ЛП
  3. I.5.5. Просмотр и анализ результатов решения задачи
  4. IDL-описаниеи библиотека типа
  5. II Съезд Советов, его основные решения. Первые шаги новой государственной власти в России (октябрь 1917 - первая половина 1918 гг.)
  6. II. ОПИСАНИЕ МАССОВОЙ ДУШИ У ЛЕБОНА
  7. III этап: Анализ решения задачи
  8. MathCad: способы решения системы уравнений.
  9. V2: ДЕ 53 - Способы решения обыкновенных дифференциальных уравнений первого порядка
  10. XI. Описание заболевания
  11. Алгоритм метода покоординатного спуска решения задачи многомерной минимизации. Геометрическая иллюстрация.
  12. Алгоритм метода скорейшего спуска решения ЗММ.

 

10. Предварительный этап:

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

 

20. Первый шаг:

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

 

30. Итерации:

* я итерация. Если в оценочной матрице все элементы неотрицательны, то план - оптимальный, в противном случае следует приступить к его улучшению;

* выбирается наибольший по абсолютной величине отрицательный элемент оценочной матрицы и, начиная с соответствующего ему элемента , в матрице строится замкнутая цепочка[11], в которую входят элементы ;

* строится новый план , прибавляя: (минимальный элемент выбирается из только из тех элементов, которые связаны цепочкой) ко всем четным элементам цепочки и вычитая из нечетных[12]. Элементы матрицы , не входящие в цепочку, переносятся в матрицу без изменения;

* далее с помощью эквивалентных преобразований (элементарные преобразования Гаусса) на основе матрицы строится матрица для нового плана . Для этого необходимо выделить в матрице все элементы, соответствующие ненулевым элементам плана (они обязательно равны нулю). В матрице вычеркивается строка, содержащая элемент . Если в этой строке имеются выделенные элементы, то вычеркиваются соответствующие этим элементам столбцы. Если в каждом вычеркнутом столбце присутствуют выделенные элементы, то далее вычеркиваются им соответствующие строки и так далее, до тех пор пока описанная процедура выполнима. После этого ко всем элементам вычеркнутых строк прибавляется величина равная , а из элементов вычеркнутых столбцов эта величина вычитается. Таким образом получается новая оценочная матрица. Если в матрице нет отрицательных элементов, то план на этом шаге оптимален. В противном случае необходимо выполнить еще одну итерацию.

На этом итерации завершаются.

 

ПРИМЕР: Пусть даны: матрица транспортных издержек , объемы производства и объемы потребления

 

          А
           
С          
           
           
В          

 

Решение начинаем с проверки баланса: Далее, строим начальный опорный план по методу северо-западного угла:


 

       
       
       
       

 

Приступаем к вычислению потенциалов. В таблице издержек для удобства выделим клетки соответствующие плану перевозок.

 

       
       
       
       

 

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

 

и так далее.

         
           
           
           
           
    -1 -6  

 

Далее рассчитываем элементы оценочной матрицы по соотношениям:

 

и так далее.

Таким образом

 

Поскольку в имеются отрицательные элементы, – план не является оптимальным.

Приступаем к итерациям. В матрице , начиная с элемента , соответствующего в оценочной матрице наибольшему по абсолютной величине отрицательному элементу, строим цепочку.

 

                 
               
        +    
               
               
    +        
               
                 

 

Изменяя элементы, входящие в цепочку, на величину строим новый план перевозок

 

       
       
       
       

 


 

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

         
           
           
           
           
    -1    

 

И далее строим оценочную матрицу:

 

 

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

 

 

На этом решение задачи завершается.

 

 

 


1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 | 18 | 19 | 20 | 21 | 22 | 23 | 24 | 25 | 26 | 27 | 28 | 29 | 30 | 31 |

Поиск по сайту:



Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав. Студалл.Орг (0.008 сек.)