Студопедия — Методы построения опорных решений
Студопедия Главная Случайная страница Обратная связь

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

Методы построения опорных решений






 

Метод северо-западного угла.

Начинаем заполнение с клетки (1,1) – С-З угол, либо удовлетворяя потребность, либо исчерпывая запасы в этом пункте. Затем переходим в следующий столбец или строку, что зависит от наличия потребности и запасов, идя как бы по диагонали таблицы заканчиваем заполнение в клетке (m,n), таким образом, будет получено опорное решение.

Метод минимального элемента

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

Замечание: Если заполненных клеток оказалось меньше чем m+n-1, то к полученному набору дописывают в некоторых клетках «0», так чтобы общее количество заполненных клеток стало m+n-1.

Алгоритм решения транспортной задачи методом потенциалов.

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

2. Найти потенциалы заполненных клеток.

3. Для незаполненных клеток проверить условие оптимальности. Если условие оптимальности выполняется, то полученное решение оптимально.

4. В противном случае выбирают клетку (k,s), для которой Uk+Vs>Cks и строим цикл транспортной таблицы, приписывая клетке знак «+» и чередуя знаки во всех остальных клетках цикла.

5. Проводим пересчет таблицы по следующему правилу. Необходимо выбрать число r=min xij из цикла со знаком «-». В клетках цикла, помеченных знаком «+», это число прибавляем. В клетках цикла, помеченных знаком «-», это число отнимаем. Остальные клетки цикла не изменяем и ту клетку, в которой было найдено r, не заполняем.

6. Возвращаемся к пункту 2.

Пример:

Составим опорное решение методом С-З угла:

  B1 B2 B3 B4 Потребности
A1 270 1 140 4 100 7    
A2     90 8    
A3     10 4 110 8  
Запасы          

 

ƒ(α1)=270+560+700+720+40+880=3170

Составим опорное решение методом минимального элемента

 

  B1 B2 B3 B4 Потребности
A1 270 1 20 4 110 7 110 3  
A2     90 8    
A3   120 2      
Запасы          

ƒ(α2)=270+80+770+330+720+240=2410

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

  B1 B2 B3 B4 Потребности Ui
A1 270 1
+ -     - +  
20 4

110 7 110 3    
A2     90 8      
A3   120 2       -2
Запасы            
Vj            

Условие оптимальности не выполняется в клетке (3;3). Производим пересчет.

 

  B1 B2 B3 B4 Потребности Ui
A1 270 1 130 4   110 3    
A2     90 8      
A3   10 2 110 4     -2
Запасы            
Vj            

 

 







Дата добавления: 2015-04-19; просмотров: 366. Нарушение авторских прав; Мы поможем в написании вашей работы!



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

ТЕОРЕТИЧЕСКАЯ МЕХАНИКА Статика является частью теоретической механики, изучающей условия, при ко­торых тело находится под действием заданной системы сил...

Теория усилителей. Схема Основная масса современных аналоговых и аналого-цифровых электронных устройств выполняется на специализированных микросхемах...

Логические цифровые микросхемы Более сложные элементы цифровой схемотехники (триггеры, мультиплексоры, декодеры и т.д.) не имеют...

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

Типовые примеры и методы их решения. Пример 2.5.1. На вклад начисляются сложные проценты: а) ежегодно; б) ежеквартально; в) ежемесячно Пример 2.5.1. На вклад начисляются сложные проценты: а) ежегодно; б) ежеквартально; в) ежемесячно. Какова должна быть годовая номинальная процентная ставка...

Выработка навыка зеркального письма (динамический стереотип) Цель работы: Проследить особенности образования любого навыка (динамического стереотипа) на примере выработки навыка зеркального письма...

Ведение учета результатов боевой подготовки в роте и во взводе Содержание журнала учета боевой подготовки во взводе. Учет результатов боевой подготовки - есть отражение количественных и качественных показателей выполнения планов подготовки соединений...

Сравнительно-исторический метод в языкознании сравнительно-исторический метод в языкознании является одним из основных и представляет собой совокупность приёмов...

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

Studopedia.info - Студопедия - 2014-2024 год . (0.01 сек.) русская версия | украинская версия