ой способ решения (метод потенциалов).

ой способ решения (метод потенциалов).

Задачка №2

Тема: Транспортная задачка

Задание

Имеются три пт отправления А1, А2, А3 однородного груза и 5 пт В1, В2, В3, В4, В5 его предназначения. На пт А1, А2, А3 груз находится в количестве а1=90, а2=30, а3=110 тонн соответственно. В пункты В1, В2, В3, В4, В5 требуется доставить соответственно b1=10, b2=60, b3=50, b4=40, b ой способ решения (метод потенциалов).5=70 тонн груза.

Расстояния в сотках км меж пт отправления и предназначения сij приведены в соответственных клеточках таблицы. Известна цена перевозки единицы груза из каждого пт отправления в каждый пункт предназначения (матрица D).

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

Указания: 1. Считать цена перевозок пропорциональной количеству груза и расстоянию, на которое груз перевозится. 2. Для решения задачки использовать способы: малой цены и потенциалов.

Решение.

Пункты отправления Пункты предназначения Припасы
В1 В2 В3 В4 В5
А1 а1=90
А2 а2=30
А3 а3=110
b1=10 b ой способ решения (метод потенциалов).2=60 b3=50 b4=40 b5=70
Потребности

Ой метод решения (способ малой цены).

Сущность способа заключается в том, что из всей таблицы стоимостей выбирают меньшую и в эту клеточку помещают наименьшее из чисел аiилиbj.Потом из рассмотрения исключают или строчку (если припасы аi выбраны), или столбец (если потребитель Bjполностью удовлетворён). Из оставшейся ой способ решения (метод потенциалов). части таблицы стоимостей опять выбирают меньшую цена, и процесс рассредотачивания припасов длится таким же образом, пока все припасы будут распределены.

Поначалу избрали клеточку А1В2, потом клеточку А1В3 (из рассмотрения исключается 1-ая строчка), позже клеточку А3В1( из рассмотрения исключается 1-ый столбец). Дальше рассматриваем клеточки А3В ой способ решения (метод потенциалов).3 и А3В5.

В оставшихся 2-ой строке и четвёртом столбце распределяем груз так, чтоб удовлетворить оставшихся потребителей.

Пункты Отправ- ления Пункты предназначения Запа- сы
В1 В2 В3 В4 В5
А1 а1=90
А2 а2=30
А3 а3= =110
b1=10 b2=60 b3=50 b4=40 b5=70
Потребности

Найдём общую цена составленного плана как сумму произведений объёмов перевозок ой способ решения (метод потенциалов). на надлежащие цены в этих же клеточках:

(ед. цены).

Ответ: план представлен таблицей, общая цена всех перевозок 670(ед.цены).

ой метод решения (способ потенциалов).

В качестве начального плана возьмём план, приобретенный способом малой цены

Пункты Отправ- ления Пункты предназначения Запа- сы
В1 В2 В3 В4 В5
А1 а ой способ решения (метод потенциалов).1=90
А2 а2=30
А3 а3= =110
b1=10 b2=60 b3=50 b4=40 b5=70
Потребности

Аспект оптимальности. Чтоб план был хорошим, нужно выполнение последующих критерий:

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

;

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

либо

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

Таким макаром, для проверки плана на оптимальность нужно выстроить систему потенциалов.

1) Построение системы потенциалов для плана.

Для построения системы потенциалов используем условие для каждой ой способ решения (метод потенциалов). занятой клеточки. Систему потенциалов можно выстроить для невырожденного опорного плана, который содержит (m+n-1)занятых клеток, где m-число поставщиков, n-число потребителей. Для каждой занятой клеточки можно составить уравнение ( ; ). Таких уравнений будет (m+n-1), а неведомых (m+n). Уравнений на одно меньше, чем число неведомых, потому система ой способ решения (метод потенциалов). имеет бессчетное огромное количество решений и одному неведомому присваивают случайное значение (обычно нулевое). После чего определяются другие потенциалы.

В таблице 7 занятых клеток (m+n-1=3+5-1=7), потому план невырожденный.

Избираем строчку, в какой имеется наибольшее число занятых клеток. Такая строчка А3, потому полагаем в этой строке потенциал u3=0. Клеточка А3В ой способ решения (метод потенциалов).1 содержит цена с31=2, для неё должно производиться условие u3+v1=2, откуда следует потенциал v1=2.Дальше клеточка А3В3: u3+v3=3, откуда v3=3. Последующая клеточка по этой строке А3В4, в какой u3+v4=5, с учетом u3=0 имеем v4=5 . В клеточке А3В5u3+v5=3,отсюда v5=3. Для последующей занятой клеточки ой способ решения (метод потенциалов). А2В4:u2+v4=u2+5=8, потому u2=3. Дальше.А1В3 : : u1+v3=u1+3=1, отсюда : u1=-2.

Таким макаром, системы потенциаловпостроена.

Поставщики Потребители Припасы
В1 В2 В3 В4 В5
v1=2 v2= 3 v3= 3 v4=5 v5=3
A1 u1=-2 а1=90
A2 u2=3 а2=30
A3 u3=0 а3=110
Потребности

2) Проверка выполнения условия оптимальности.

Для каждой ой способ решения (метод потенциалов). незанятой клеточки проверяем выполнение условия

Если для всех незанятых клеток производится это условие, то план лучший. Если для неких клеток , то план не является хорошим. Тогда для этих клеток находим величину разности

и записываем в нижний левый угол этой клеточки.

В клеточке А2В2 нарушено условие оптимальности:

(в этой клеточке цифра 2 в ой способ решения (метод потенциалов). квадратике).

Итак, опорный план не является хорошим.

3) Выбор клеточки, в которую нужно отправить перевозку.

В транспортной задачке загрузке подлежит клеточка, в какой не производится условие оптимальности. Потому клеточку А2В2 нужно сделать занятой.

4) Построение цикла и определение величины перераспределения.

Поставщики Потребители Припасы
В1 В2 В3 В4 В5
v ой способ решения (метод потенциалов).1=2 v2= 3 v3= 3 v4=5 v5=3
A1 u1=-2 601 301 а1=90
A2 u2=3 308 а2=30
A3 u3=0 20 105 а3=110
Потребности

Отмечаем знаком (+) незанятую клеточку А2В2 . Ранее в таблице было (m+n-1=3+5-1=7) занятых клеток, которые составляли базис. Сейчас в таблице стало (m+n=3+5=8) занятых клеток (линейно зависимых), потому должен существовать замкнутый цикл. Намечаем его ой способ решения (метод потенциалов). пунктиром, поочерёдно расставляем знаки (+) и (-) на поворотах, начиная с клеточки А2В2.Из клеточки А2В2 перемещаемся в клеточку А1В2 , потом в А1В3 , позже в А3В3 , дальше в А3В4 , следуем в А2В4 , и в конце концов возвращаемся в А2В2

Цикл замкнулся.

Потом находим ой способ решения (метод потенциалов). , где - перевозки, стоящие в верхушках цикла, отмеченные знаком . Величина определяет количество груза, которое нужно перераспределить по циклу. Величина прибавляется к перевозкам, отмеченным знаком , и вычитается от перевозок, отмеченным знаком . Имеем . Как следует, перевозку, равную 20 перемещаем в клеточку А2В2, из клеток со знаком (-) отнимаем 20, а в клеточки со знаком (+) прибавляем ой способ решения (метод потенциалов). 20.

В итоге получен новый опорный план, который опять подлежит проверке на оптимальность.

Поставщики Потребители Припасы
В1 В2 В3 В4 В5
v1=2 v2= 1 v3= 1 v4=5 v5=3
A1 u1=0 а1=90
A2 u2=3 а2=30
A3 u3=0 а3=110
Потребности

5) Изменение системы потенциалов.

Для клеточки А2В2 , в какой было нарушено условие ой способ решения (метод потенциалов). оптимальности, необходимо поменять систему потенциалов, но за ранее проверим третью строчку: в занятых клеточках потенциалы не трогаем, другими словами u3=0, v1=2, v4=5, v5=3. Перебегаем ко 2-ой строке: оставляем без конфигурации u2=3, чтоб не нарушить равенство в клеточке А2В4 ; сейчас разглядим клеточку А2В2 , для неё , откуда следует . Итак, 2-ая строчка ой способ решения (метод потенциалов). по занятым клеточкам выполнена. Сейчас разглядим первую строчку: клеточка А1В2 , отсюда ; осталась последняя клеточка А1В3

, откуда . Система потенциалов построена.

6) Проверка выполнения условия оптимальности

Дальше проверяем незанятые клеточки на оптимальность. Все клеточки удовлетворяют условию оптимальности ,

как следует, план лучший.

Найдём общую цена составленного плана как сумму произведений объёмов ой способ решения (метод потенциалов). перевозок на надлежащие цены в этих же клеточках:

(ед. цены).

Ответ: план представлен таблицей, общая цена всех перевозок 630(ед.цены).


ohlazhdenie-k-molitve-nebrezhnaya-i-speshnaya-molitva-kak-izbegat-etogo-chtenie-molitv-na-pamyat.html
ohode-rabot-po-realizacii-programmi-perehoda-rggu-na-urovnevuyu-sistemu-podgotovki-na-2010-2011-gg-doklad-nachalnika-upravleniya-kachestva-obrazovaniya-korchinskogo-anatoliya-viktorovicha.html
ohode-realizacii-trebovanij-direktivi-prezidenta-respubliki-belarus-ot-11-marta-2004-g-1-o-merah-po-ukrepleniyu-obshestvennoj-bezopasnosti-i-disciplini-v-chasti-obespecheniya-pozharnoj-bezopasnosti-na.html