 |
АвтоАвтоматизацияАрхитектураАстрономияАудитБиологияБухгалтерияВоенное делоГенетикаГеографияГеологияГосударствоДомДругоеЖурналистика и СМИИзобретательствоИностранные языкиИнформатикаИскусствоИсторияКомпьютерыКулинарияКультураЛексикологияЛитератураЛогикаМаркетингМатематикаМашиностроениеМедицинаМенеджментМеталлы и СваркаМеханикаМузыкаНаселениеОбразованиеОхрана безопасности жизниОхрана ТрудаПедагогикаПолитикаПравоПриборостроениеПрограммированиеПроизводствоПромышленностьПсихологияРадиоРегилияСвязьСоциологияСпортСтандартизацияСтроительствоТехнологииТорговляТуризмФизикаФизиологияФилософияФинансыХимияХозяйствоЦеннообразованиеЧерчениеЭкологияЭконометрикаЭкономикаЭлектроникаЮриспунденкция
Транспортная задача. Представим транспортную задачу по критерию стоимости в виде таблицы Поставщики ПОТРЕБИТЕЛИ Запас груза B1 B2 Bn А1
Представим транспортную задачу по критерию стоимости в виде таблицы
| Поставщики | ПОТРЕБИТЕЛИ | Запас груза | |||
| B1 | B2 | … | Bn | ||
| А1 | X11 c11 | X12 c12 | … | X1n c1n | a1 |
| … | … | … | |||
| Аm | … | an | |||
| Потребность в грузе | b1 |
В таблице указаны поставщики А1…, у которых имеется в наличии соответственно а1… единиц однородного груза. Данный груз должен быть доставлен n потребителям, в количествах в1… единиц, заданы стоимости сij перевозок груза от i поставщика j потребителю. Требуется спланировать перевозки(указать, сколько единиц груза должно быть отправлено от I того поставщика j потребителю, так чтобы максимально удовлетворить спрос потребителя и чтобы суммарные затрата на перевозки были при этом минимальными).
c1 – цена.
Задачи, где суммарные запасы грузов поставщиков равны суммарным потребностям, называются закрытыми.
I!= 
I – то задача открытая.
При решении транспортных задач важное значение имеет теорема о ранге матрицы:
Ранг матрицы транспортной задачи на 1 меньше числа уравнений(r=m+n-1).
Столько должно быть занятых иксами клеток в транспортной задаче. Решение транспортной задачи проводится с помощью общего приема последовательного улучшения плана, что включает этапы:
1.Определение исходного опорного плана.
2.Оценка этого плана.
3.Переход к следующему плану путем однократной замены одной из базисных переменных на свободную.
Существуют различные способы реализации этапов решения транспортной задачи:
1.Правило северо-западного угла.
Пример:
| Поставщики | ПОТРЕБИТЕЛИ | Запас груза | |||
| B1 | B2 | B3 | B4 | ||
| А1 | 4 \ 40 | 3 \10 | 2 \- | 6 \ - | |
| A2 | 2 \- | 4 \50 | 5 \20 | 1 \ - | |
| А3 | 3 \- | 6 \- | 7 \30 | 5 \70 | |
| Потребность в грузе |
2.Правило минимального элемента.
Пример:
| Поставщики | ПОТРЕБИТЕЛИ | Запас груза | |||
| B1 | B2 | B3 | B4 | ||
| А1 | 4 - | 3 0 | 2 50 | 6 - | |
| A2 | 2 0 | 4 - | 5 - | 1 70 | |
| А3 | 3 40 | 6 60 | 7 - | 5 - | |
| Потребность в грузе |
3.Метод Фогеля.
| А/B | В1(40) | В2(60) | В3(50) | В4(70) | |||
| А1(50) | 2\50 | 6\- | |||||
| А2(70) | 1\70 | ||||||
| А3(100) | 5\- | ||||||
Пример:
| Поставщики | ПОТРЕБИТЕЛИ | Запас груза | |||
| B1 | B2 | B3 | B4 | ||
| А1 | 5\230 | 1\70 | 2\- | 3\- | |
| A2 | 6\- | 3\200 | 7\- | 1\- | |
| А3 | 4\- | 5\150 | 3\350 | 2\- | |
| А4 | 2\- | 4\- | 6\300 | 4\400 | |
| Потребность в грузе |
4+4-1=7
4.Метод потенциалов и др.
Перейдем к построению оптимального плана перевозок. По данному опорному плану, у которого число занятых клеток m+n-1. Каждому поставщику и каждому потребителю передается число, называемое потенциалом. Потенциалы выбираются так, чтобы их сумма для каждой загруженной грузом клетки была равна тарифу перевозки единицы груза. Так если клетка (I,k) – базисная(занятая), то ui +vk=Cik где у итое поьенцтал итого поставщика.
Тогда вычисляем оценки свободных клеток по формуле: Sij=Cij-(Ui+Vj)
Если для свободных клеток все оценки Sij больше или ровны 0, то полученный план перевозок оптимален. При наличии хотя бы одной оценки Sij < 0 число базисных вводят в клетку, для которой оценка Sij минимальной. Для такой клетки строится цикл и производится перемещение груза так, чтобы баланс цикла сохранялся.
| A/B | B1(80) | B2(170) | B3(150) | B4(180) | B5(70) |
| A1(300) | 4/80 | 7/- | 1/150 | 5/- | 2/70 |
| A2(150) | 6/- | 2/- | 4/- | 1/150 | 3/0 |
| A3(200) | 5/- | 6/170 | 7/- | 4/30 | 8/- |
U1=0
U2=
U3=
В заполненой клетке таріф равен сумме потенциалов
| A/B | B1(80) | B2(170) | B3(150) | B4(180) | B5(70) |
| A1(300) | 4/80 | 7/- | 1/150 | 5/- | 2/70 |
| A2(150) | 6/- | 2/- | 4/- | 1/150 | 3/0 |
| A3(200) | 5/- | 6/170 | 7/- | 4/30 | 8/- |
V1=4
V2=2
V3=1
V4=0
V5=2
S12=5
S14=5
S21=1
S22=-1
S23=2
S31=-2
S33=2
S35=2
| A/B | B1(80) | B2(170) | B3(150) | B4(180) | B5(70) |
| A1(300) | 4/80 | 7/- | 1/150 | 5/- | 2/70 |
| A2(150) | 6/- | 2/- | 4/- | 1/150 | 3/- |
| A3(200) | 5/0 | 6/170 | 7/- | 4/30 | 8/- |
F=320+150+140+150+1020+120=1900
| A/B | B1(80) | B2(170) | B3(150) | B4(180) | B5(70) |
| A1(300) | 4/80 | 7/- | 1/150 | 5/- | 2/70 |
| A2(150) | 6/- | 2/- | 4/- | 1/150 | 3/- |
| A3(200) | 5/0 | 6/170 | 7/- | 4/30 | 8/- |
-2
4 5 1 3 2
| A/B | B1(80) | B2(170) | B3(150) | B4(180) | B5(70) |
| A1(300) | 4/80 | 7/- | 1/150 | 5/- | 2/70 |
| A2(150) | 6/- | 2/150 | 4/- | 1/- | 3/- |
| A3(200) | 5/0 | 6/20 | 7/- | 4/180 | 8/- |
-3
4 5 1 3 2
S12=7-0-5=2
S14=5-0-3=2
S21=6+3-4=5
S23=4+3-1=6
S24=1+3-3=1
S25=3+3-2
S31=5-1-4=0
S33=7-1-1=5
S35=8-1-2=5
F=1750
| A/B | B1() | B2(170) | B3(150) | B4(180) |
| A1(40) | 6/- | 4/10 | 2/30 | 7/- |
| A2(36) | 8/24 | 10/10 | 14/- | 12/2 |
| A3(24) | 16/- | 12/- | 6/- | 13/24 |
2 4 2 6
S11=4
S14=1
S23=6
S31=7
S32=1
S33=-3
Min(30,10,24)
| A/B | B1() | B2(170) | B3(150) | B4(180) |
| A1(40) | 6/- | 4/20 | 2/20 | 7/- |
| A2(36) | 8/24 | 10/- | 14/- | 12/12 |
| A3(24) | 16/- | 12/- | 6/10 | 13/14 |
5 4 2 9
S11=1
S14=-2
S22=3
S23=9
s31=7
s32=4
min(14,20)=14
| В1(50) | В2(55) | В3(70) | В4(45) | В5(10) | ||
| А1(60) | 4\15 | 10\- | 5\- | 3\45 | 0\- | |
| А2(100) | 6\30 | 7\- | 2\70 | 8- | 0\- | |
| А3(70) | 8\5 | 9\55 | 12\- | 11\- | 0\10 | |
| -4 |
230-220 = 10 ЗНАЧИТ ДОБАВИМ В5
S12=10-0-5=5 S13=-5 S15=4 S22=0 S24=3 S25=3 S33=8 S34=4
F=60+135+180+140+40+495=1050
Теория графов. Основные понятия и определения
1.Графом G=(V,E) (или G=(p,q))называется пара множеств, где V – непустое, конечное множество, состоящее из р элементов(вершин графа G), E – множество неупорядоченных пар элементов q(ребра).
Отрезки, соединяющие вершины, называются дугами, если указано, какая вершина является начальной, и ребрами, если ориентация не указана.
Граф, состоящий из дуг, называется ориентированным (оргрфом). Образованный ребрами – неориентированный.
Если Е – пустое множество, то граф G – пустой граф. Мультиграф – между двумя вершинами можно нарисовать 2 и более ребра.
Если имеются вершины V1 и V2 и ребро е образовано ими, то говорят, что ребро е инцедентно вершинам V1 и V2. V1 и V2 – смежные.
Степенью вершины называется число ребер инцидентных данной вершине(количество выходящих из нее ребер). Вершина, степень которой равна 1, называется висящей.
Вершина, степень которой равна 0, называется изолированной.
Последовательность ребер V0, V1… называется маршрутом. Если в маршруте не указаны ребра, то такой маршрут называется цепью. Если V0=Vn, то цепь называют циклом. Если в цепи не повторяются вершины, то такая цепь называется простой.
Граф называется связным, если любая пара его вершин соединена маршрутом.
Если в связном графе имеется цикл, проходящий через все ребра графа, то граф называется Эйлеровым.
Связный граф, не имеющий циклов – дерево.
Поиск по сайту: