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

Нахождение исходного опорного решения транспортной задачи

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

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

Ввиду того, что r = p+q-1, опорное решение не может иметь отличных от нуля координат более p+q-1. Число отличных от нуля координат невырожденного опорного решения равно p+q-1, а для вырожденного опорного решения меньше.

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

2. Метод минимальной стоимости

3. Метод двойного предпочтения

1. Начинают с того, что приписывают переменной x11, стоящей в северо-западном углу таблицы, минимальное из значений a1 и b1.

x11=min a1b1

Двигаются в соседнюю клетку по строке вправо, если a1>b1, или по столбцу вниз если a1<b1, полагая x12=a1-b1b2(min), x21=b1-a1a2(min). Это продолжают до тех пор, пока не исчерпаются ресурсы и потребности. Последняя заполненная клетка окажется pq. Решение, получаемое по методу сз угла – опорное решение.

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

2. Из всей таблицы стоимостей выбирают наименьшую и в клетку, которая ей соответствует, помещают меньшее из чисел ai и bi. Затем из рассмотрения исключают или строку, соответствующую поставщику, запасы которого полностью израсходованы, либо столбец, соответствующий потребителю, потребности которого полностью удовлетворены, либо строку и столбец, если израсходованы запасы поставщика и удовлетворены потребности потребителя. Из оставшейся таблицы стоимостей снова выбирают наименьшую стоимость, и процесс распределения запасов продолжают, пока все запасы не будут распределены, а потребности удовлетворены.

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

Цикл – набор клеток вида (i1k2,i2k1), в котором только две соседние клетки расположены в одном столбце или одной строке распределительной таблицы, причем последняя клетка находится в том же столбце или в той же строке, что и первая.

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

 


1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |

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



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