Контрольная работа по "Методы оптимального решения"

Министерство образования и науки Российской Федерации

Государственное образовательное учреждение высшего профессионального образования

Российский государственный торгово-экономический университет

(РГТЭУ)

Контрольная  работа по дисциплине:

Методы оптимального решения

Вариант №5

Выполнил студент:

Проверил:

Дата:

Москва 2012

Вариант № 5.

Задача 1. Потоки в сетях.

Задана такая сеть:

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

1. Сначала зададим значение пропускной способности сети равным нулю: V=0. Выберем верхний (по принципу левостороннего движения) путь: 0 – 1 – 4 – 7. Его пропускная способность равна 3. Прибавим к пропускной способности это значение (V=3) и уменьшим на 3 пропускные способности ветвей пути. Насыщенную ветвь (4 – 7)в дальнейшем учитывать не будем и обозначим ее пунктиром.

2. Следующий верхний путь будет таким: 0 – 1 – 4 – 5 – 7. Его пропускная способность равна 1. Увеличим на 1 значение пропускной способности сети: V=4. Получим такой граф:

3. Следующий путь: 0 – 1 – 4 – 2 – 5 – 7. Его пропускная способность равна 2. V=6.

4. 0 – 1 – 2 – 5 – 7. Пропускная способность равна 1. V=7.

5. 0 – 2 – 5 – 7. Пропускная способность равна 2. V=9.

6. 0 – 3 – 6 – 5 – 7. Пропускная способность равна 1. V=10.

7. 0 – 3 – 6 – 7. Пропускная способность равна 5. V=15.

Как видим, больше путей нет. Следовательно, максимальный поток V=15, а путь транспортировки будет таким:

Задача 2. Задача о назначениях.

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

Решение.

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

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

Этап 2. Осуществляем назначения.