Отправляет email-рассылки с помощью сервиса Sendsay

RFpro.ru: Консультации по дискретной математике

Подписаться Бесплатная «Серебряная» новостная рассылка . Подписчиков 106 RSS
←   Январь 2010   →
 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


За последние 60 дней ни разу не выходила


Сайт рассылки: http://rusfaq.ru/issues/8/19/525
Открыта: 17-04-2009

Автор
Калашников О.А.

Статистика

106 подписчиков
0 за неделю
←   Все выпуски   →

RFpro.ru: Дискретная математика


Хостинг портала RFpro.ru:
Московский хостер
Профессиональный платный хостинг на базе Windows 2008

РАССЫЛКИ ПОРТАЛА RFPRO.RU

Чемпионы рейтинга экспертов в этой рассылке

Гордиенко Андрей Владимирович
Статус: Профессор
Рейтинг: 3959
∙ повысить рейтинг » 		_Ayl_
Статус: Студент
Рейтинг: 1408
∙ повысить рейтинг » 		Гаряка Асмик
Статус: Практикант
Рейтинг: 1059
∙ повысить рейтинг »

/ НАУКА И ОБРАЗОВАНИЕ / Точные и естественные науки / Дискретная математика

Номер выпуска:157
Дата выхода:09.01.2010, 20:30
Администратор рассылки:Alexey G. Gladenyuk, Управляющий
Подписчиков / экспертов:113 / 45
Вопросов / ответов:1 / 1

Вопрос № 175823: Здравствуйте Уважаемые эксперты! Требуется ваша помощь Транспортная задача Исходные данные транспортной задачи приведены в таблице. Требуется: 1.Определить тип задачи. 2.В...

Вопрос № 175823:

Здравствуйте Уважаемые эксперты! Требуется ваша помощь

Транспортная задача
Исходные данные транспортной задачи приведены в таблице.
Требуется:
1.Определить тип задачи.
2.В случае необходимости привести задачу к каноническому виду.
3.Сформулировать экономико-математическую модель задачи.
4.Представить схему решения задачи.



Отправлен: 04.01.2010, 20:16
Вопрос задал: kot31, Посетитель
Всего ответов: 1
Страница вопроса »

Отвечает Гаряка Асмик, Практикант :
Здравствуйте, kot31.

Транспортная задача: Пусть некоторый, однородный товар (продукт) хранится на M складах и потребляется в N пунктах (например, магазинах). Известны следующие параметры: ai - запас продукта на -ом складе, ai>0, i=1,….,m, bj- потребность в продукте в j-ом пункте, bj>0,j=1,….,n, Cij - стоимость перевозки единичного количества товара с i-го склада в j-й пункт. Планируется полностью перевезти товар со складов и полностью удовлетворить потребности в пунктах назначения.
Существуют два типа транспортной задачи: открытая и закрытая. Транспортная задача называется открытой если сумма запасов товара на складах отличается от суммы потребностей товаров у магазинов. Транспортная задача называется закрытой, если сумма запасов товара на складах равняется сумме потребностей магазинов. В данном случае ∑ai=1630, ∑bj =2250, то есть потребность превышает запасы, задача открытая. Решение сущес твует только для закрытой транспортной задачи, поэтому если транспортная задача открытая, то ее надо привести к закрытому типу. Для этого в случае, если запас товара на складах превышает потребность магазинов, то вводят фиктивного потребителя, который выбирает весь избыток товара. В случае же, если существует дефицит товара, т.е. потребность магазинов больше, чем запас товаров на складах, то вводят фиктивного поставщика, с фиктивным запасом товара на складе. В обоих случаях в матрице тарифов перевозок |C| данному складу или магазину проставляется нулевая цена перевозки. Запас товара у этого фиктивного поставщика - 2250-1630=620.
Транспортная задача ставится как каноническая задача ЛП следующего специального вида:
m n
E E CijXij → min
i=1j=1

при условиях:

n
E xij=ai,i=1,…,m
J=1

n
E xij=bj,j=1,….,n
I=1

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

Алгоритм метода минимального эле мента состоит в следующем.

Просматривается вся матрица тарифов перевозок, и из нее выбирается позиция с наименьшим значением тарифа C, затем просматриваются значения наличия запасов на складе A и потребности у потребителя B, затем в данную клетку записывается величина D=MIN(A,B). Из запасов соответствующего склада и потребностей магазина вычитается величина D . Если запас товара на складе исчерпан, то эта строка исключается из дальнейшего рассмотрения.
Если потребность магазина в товаре удовлетворена полностью, то этот столбец исключается из дальнейшего рассмотрения. Может быть случай , когда одновременно исключаются и строка и столбец, этот случай называется вырожденным. В дальнейшем весь процесс повторяется до тех пор , пока не будет исчерпан весь запас товаров на складах и не будет удовлетворена потребность всех магазинов. По полученной матрице перевозок вычисляется целевая функция задачи Z.

Метод Фогеля

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

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

В начальной своей стадии этот метод похож на метод минимального элемента , но для столбцов. Просматривается первый столбец матрицы тарифов, в нем находится наименьший элемент. Затем проверяется , минимален ли этот элемент в своей строке. Если элемент минимален в своей строке, то по методу минимального элемента в эту клетку заносится значение D=MIN(A,B), соответствующие запас и потребность уменьшаются на эту величи ну.
Обнулившаяся строка или столбец исключаются из рассмотрения и процесс повторяется, начиная с первого неисключенного столбца. Если н айденный минимальный элемент не минимален в своей строке, то происходит переход к следующему столбцу и так до тех пор, пока не будет найден такой элемент. По полученной матрице перевозок вычисляется целевая функция Z. Этот метод требует интенсивных операции обмена с памятью , поэтому более громоздок по сравнению с остальными и требует больших вычислительных ресурсов.

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

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

Метод состоит в следующем. Просматривается матрица тарифов перевозок C , начиная с левого верхнего угла (клетки). В эту клетку записывается величина
D=MIN(A,B). Она вычитается из запасов и потребностей соответствующего склада и магазина. Обнулившаяся строка или столбец исключаются из рассмотрения, затем процесс опять повторяется для левой вер хней клетки оставшейся матрицы и так до тех пор пока весь запас товаров не будет исчерпан. Полученный опорный план не оптимален, поэтому его дальнейшее решение продолжают одним из вышерассмотренных методов.

-----
Я ни от чего, ни от кого не завишу.

Ответ отправил: Гаряка Асмик, Практикант
Ответ отправлен: 09.01.2010, 03:33

Как сказать этому эксперту "спасибо"?
  • Отправить SMS #thank 258492 на номер 1151 (Россия) | Еще номера »
  • Отправить WebMoney:
    • Вам помогли? Пожалуйста, поблагодарите эксперта за это!

    Оценить выпуск »
    Нам очень важно Ваше мнение об этом выпуске рассылки!

    Задать вопрос экспертам этой рассылки »

    Скажите "спасибо" эксперту, который помог Вам!

    Отправьте СМС-сообщение с тестом #thank НОМЕР_ОТВЕТА
    на короткий номер 1151 (Россия)
    Номер ответа и конкретный текст СМС указан внизу каждого ответа.

    Полный список номеров »

    * Стоимость одного СМС-сообщения от 7.15 руб. и зависит от оператора сотовой связи. (полный список тарифов)
    ** При ошибочном вводе номера ответа или текста #thank услуга считается оказанной, денежные средства не возвращаются.
    *** Сумма выплаты эксперту-автору ответа расчитывается из суммы перечислений на портал от биллинговой компании.

    © 2001-2010, Портал RFpro.ru, Россия
    Авторское право: ООО "Мастер-Эксперт Про"
    Автор: Калашников О.А. | Программирование: Гладенюк А.Г.
    Хостинг: Компания "Московский хостер"
    Версия системы: 2009.6.13 от 28.12.2009
    В избранное