Сетевые модели

Математическая модель транспортной задачи с промежуточными пунктами. Определение кратчайших путей от пунктов с избытком к пунктам с недостатками ресурсов. Построение математической модели для симметрической задачи коммивояжера. Определение маршрутов.

Рубрика Программирование, компьютеры и кибернетика
Вид контрольная работа
Язык русский
Дата добавления 28.09.2017
Размер файла 198,5 K

Отправить свою хорошую работу в базу знаний просто. Используйте форму, расположенную ниже

Студенты, аспиранты, молодые ученые, использующие базу знаний в своей учебе и работе, будут вам очень благодарны.

Размещено на http://www.allbest.ru/

Томский межвузовский центр дистанционного образования

Томский государственный университет

систем управления и радиоэлектроники (ТУСУР)

Кафедра компьютерных систем в управлении и проектировании

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

«Автоматизированные информационно-управляющие системы»

«Автоматизированное управление в технических системах»

г. Ноябрьск 2012

СЕТЕВЫЕ МОДЕЛИ

Транспортная задача.

Записать математическую модель транспортной задачи с промежуточными пунктами, заданной сетью на рис.1 и таблицей 1.

Размещено на http://www.allbest.ru/

Рис. 1 Сеть транспортной задачи с промежуточными пунктами

Таблица 1

Данные варианта

i

1

2

3

4

5

6

7

8

A1

A2

A3

A4

A5

A6

A7

c12

5

8

4

5

7

5

1

7

i

9

10

11

12

13

14

15

16

c13

c14

c23

c25

c26

c34

c35

c36

6

6

2

4

8

6

4

5

i

17

18

19

20

21

22

23

24

c37

c46

c47

c56

c58

c67

c68

c78

6

3

2

4

9

3

8

5

Найти оптимальное решение задачи из п.1.1.

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

1.3. Произвести анализ на чувствительность задачи из п.1.1.

1.3.1. Найти наименьшее значение каждого из коэффициентов C25 и C47 в исходной сети с промежуточными пунктами, при которых прежнее решение остается оптимальным.

1.3.2. Допустим, что один избыток запасов Ai (i=1,3,5,7) увеличился на . Найти приращение целевой функции при =1, а также предельное значение , при котором прежнее решение остается оптимальным.

Примечание. Для каждого Ai (i=1,3,5,7) показать цикл перераспределения на матрице условий.

1.3.3. Допустим, что один избыток запасов Ai (i=1,3,5) увеличился на одновременно с таким же увеличением потребности Ai+1. Найти приращение целевой функции при =1, а также предельное значение , при котором прежнее решение остается оптимальным.

Примечание. Для каждой пары Ai и Ai+1 (i=1,3,5) показать цикл перераспределения на матрице условий.

2. Задача коммивояжера.

2.1. Записать математическую модель для симметричной (cij=cji) задачи коммивояжера, заданной сетью на рис.1 и таблицей 1 (параметры Ai во внимание не принимаются).

2.2. Найти оптимальное решение модели из п.2.1.

1. Формулируем модель. В соответствии с заданной сетью, с учетом исходных данных она имеет вид:

1.2. Находим кратчайшие пути от пунктов с избытком к пунктам с недостатками ресурсов и записываем в матрицу тарифов. Сюда же запишем исходный базис, построенный методом северо-западного угла.

ПН

Поставки

ПО

2

4

6

1

7

5

6

9

5

3

2

3

6

1

5

4

5

4

7

4

4

3

7

7

8

2

3

1

1

8

13

7

8

1

1

Спрос

8

5

5

Проверяем условие разрешимости задачи, заключающееся в равенстве количества поставок и спроса: 5+4+7+1+1=8+5+5; 18=18.

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

Подсчитаем значение целевой функции:

Проверим оптимальность опорного плана. Найдем предварительные потенциалы ui, vi по занятым клеткам таблицы, в которых ui + vi = cij, полагая, что u1 = 0.

7

5

6

9

2

3

6

1

5

4

7

4

4

3

8

2

3

1

13

7

8

1

Составляем матрицу оценок:

ПН

ПО

2

4

6

u i

1

7

0

6

5

9

-1

0

3

2

0

6

0

5

-2

-5

5

4

-1

7

0

4

0

-4

7

8

-6

2

4

3

0

-5

8

13

-6

7

4

8

0

0

v j

7

11

8

Опорный план не является оптимальным, так как существуют оценки свободных клеток, для которых ui + vi > cij.

Выбираем максимальную оценку свободной клетки (1;4)=5

Для этого в перспективную клетку (1;4) поставим знак «+», а в остальных вершинах многоугольника чередующиеся знаки «-», «+», «-».

ПН

Поставки

ПО

2

4

6

1

7

5-

6

+

9

5

3

2

3+

6

1-

5

4

5

4

7

4

4

3

7

7

8

2

3

1

1

8

13

7

8

1

1

Спрос

8

5

5

Цикл в таблице (1,4; 1,2; 3,2; 3,4; ).

Из грузов хij стоящих в минусовых клетках, выбираем наименьшее, т.е. у = min (3, 4) = 1. Прибавляем 1 к объемам грузов, стоящих в плюсовых клетках и вычитаем 1 из хij, стоящих в минусовых клетках и получим новый опорный план.

ПН

Поставки

ПО

2

4

6

1

7

4

6

1

9

5

3

2

4

6

5

4

5

4

7

4

4

3

7

7

8

2

3

1

1

8

13

7

8

1

1

Спрос

8

5

5

Значение целевой функции для этого опорного плана равно:

Проверим оптимальность опорного плана. Найдем предварительные потенциалы ui, vi по занятым клеткам таблицы, в которых ui + vi = cij, полагая, что u1 = 0.

7

4

6

1

9

2

4

6

5

4

7

4

4

3

8

2

3

1

13

7

8

1

Составляем матрицу оценок:

ПН

ПО

2

4

6

u i

1

7

0

6

0

9

-6

0

3

2

0

6

-5

5

-5

5

4

4

7

0

4

0

1

7

8

-1

2

4

3

0

0

8

13

-1

7

4

8

0

5

v j

7

6

3

Опорный план не является оптимальным, так как существуют оценки свободных клеток, для которых ui + vi > cij.

Выбираем одну из максимальных оценок свободной клетки (5;2)=4

Для этого в перспективную клетку (5;2) поставим знак «+», а в остальных вершинах многоугольника чередующиеся знаки «-», «+», «-».

ПН

Поставки

ПО

2

4

6

1

7

4-

6

1+

9

5

3

2

4

6

5

4

5

4

+

7

4-

4

3

7

7

8

2

3

1

1

8

13

7

8

1

1

Спрос

8

5

5

Цикл в таблице (5,2; 5,4; 1,4; 1,2; ).

Из грузов хij стоящих в минусовых клетках, выбираем наименьшее, т.е. у = min (1, 2) = 4. Прибавляем 4 к объемам грузов, стоящих в плюсовых клетках и вычитаем 4 из хij, стоящих в минусовых клетках и получим новый опорный план.

ПН

Поставки

ПО

2

4

6

1

7

6

5

9

5

3

2

4

6

5

4

5

4

4

7

0

4

3

7

7

8

2

3

1

1

8

13

7

8

1

1

Спрос

8

5

5

Значение целевой функции для этого опорного плана равно:

Проверим оптимальность опорного плана. Найдем предварительные потенциалы ui, vi по занятым клеткам таблицы, в которых ui + vi = cij, полагая, что u1 = 0.

7

6

5

9

2

4

6

5

4

4

7

0

4

3

8

2

3

1

13

7

8

1

Составляем матрицу оценок:

ПН

ПО

2

4

6

u i

1

7

-4

6

0

9

-6

0

3

2

0

6-1

5

-3

-1

5

4

0

7

0

4

0

1

7

8

-5

2

4

3

0

0

8

13

-5

7

4

8

0

5

v j

3

6

3

Опорный план не является оптимальным, так как существуют оценки свободных клеток, для которых ui + vi > cij.

Выбираем оценку свободной клетки (7;4)=4

Для этого в перспективную клетку (7;4) поставим знак «+», а в остальных вершинах многоугольника чередующиеся знаки «-», «+», «-».

ПН

Поставки

ПО

2

4

6

1

7

6

5

9

5

3

2

4

6

5

4

5

4

4

7

0-

4

3+

7

7

8

2

+

3

1-

1

8

13

7

8

1

1

Спрос

8

5

5

Цикл в таблице (7,4; 5,4; 5,6; 7,6; ).

Из грузов хij стоящих в минусовых клетках, выбираем наименьшее, т.е. у = min (5, 4) = 0. Прибавляем 0 к объемам грузов, стоящих в плюсовых клетках и вычитаем 0 из хij, стоящих в минусовых клетках и получим новый опорный план.

ПН

Поставки

ПО

2

4

6

1

7

6

5

9

5

3

2

4

6

5

4

5

4

4

7

4

3

7

7

8

2

0

3

1

1

8

13

7

8

1

1

Спрос

8

5

5

Значение целевой функции для этого опорного плана равно:

Проверим оптимальность опорного плана. Найдем предварительные потенциалы ui, vi по занятым клеткам таблицы, в которых ui + vi = cij, полагая, что u1 = 0.

7

6

5

9

2

4

6

5

4

4

7

4

3

8

2

0

3

1

13

7

8

1

Составляем матрицу оценок:

ПН

ПО

2

4

6

u i

1

7

0

6

0

9

-2

0

3

2

0

6

-5

5

-3

-5

5

4

0

7

-4

4

0

-3

7

8

-5

2

0

3

0

-4

8

13

-5

7

0

8

0

1

v j

7

6

7

Опорный план является оптимальным, так как все оценки свободных клеток удовлетворяют условию ui + vi <= cij.

Минимальные затраты для поставленной задачи составят:

Запишем конечный результат для исходной задачи:

5ед. транспортируются из пункта 1 в пункт 4 без промежуточных пунктов;

4ед. транспортируются из пункта 3 в пункт 2 без промежуточных пунктов;

4ед. транспортируются из пункта 5 в пункт 2 без промежуточных пунктов;

3ед. транспортируются из пункта 5 в пункт 6 без промежуточных пунктов;

0ед. транспортируется из пункта 7 в пункт 4 без промежуточных пунктов;

1ед. транспортируется из пункта 7 в пункт 6 без промежуточных пунктов;

1ед. транспортируется из пункта 7 в пункт 8 без промежуточных пунктов;

Покажем решение на графе:

1.3. Проанализируем задачу на чувствительность.

1.3.1. Коэффициент C25=4 является расстоянием между пунктами 5 и 2,то есть его значение может быть использовано только при оценке клетки (5,2):

Так как при найденном оптимальном решении , то при C52<4 значение оценки станет положительным, значит, решение уже не будет оптимальным. Таким образом, наименьшее значение коэффициента C52=4.

Коэффициент C47=9 является расстоянием между пунктами 7 и 4, его значение может быть использовано только при оценке клетки (7,4):

Так как при найденном оптимальном решении , то при C47<2 значение оценки станет положительным, значит, решение уже не будет оптимальным. Таким образом, наименьшее значение коэффициента C47=2.

1.3.2. Приращение запасов одного из поставщиков.

1. При увеличении S1 на единицу с 5 до 6 целевая функция уменьшится на 1. Цикл перераспределения в матрице условий:

ПН

Поставки

ui

ПО

2

4

6

1

7

6

5+1

9

5+1

0

3

2

4

6

5

4

-5

5

4

4

7

4

3

7

-3

7

8

2

0-1

3

1+1

1

-4

8

13

7

8

1-1

1-1

1

Спрос

8

5

5

vj

7

6

7

Целевая функция:

Предельное значение определяется клеткой (8,6) и

2. При увеличении S3 на единицу с 4 до 5 целевая функция уменьшится на 2. Цикл перераспределения в матрице условий:

ПН

Поставки

ui

ПО

2

4

6

1

7

6

5

9

5

0

3

2

4+1

6

5

4+1

-5

5

4

4-1

7

4

3

7-1

-3

7

8

2

0

3

1

1

-4

8

13

7

8

1

1

1

Спрос

8

5

5

vj

7

6

7

Целевая функция:

Предельное значение определяется клеткой (5,2) и

3. При увеличении S5 на единицу с 4 до 5 целевая функция увеличится на 2. Цикл перераспределения в матрице условий:

ПН

Поставки

ui

ПО

2

4

6

1

7

6

5

9

5

0

3

2

4-1

6

5

4-1

-5

5

4

4+1

7

4

3

7+1

-3

7

8

2

0

3

1

1

-4

8

13

7

8

1

1

1

Спрос

8

5

5

vj

7

6

7

Целевая функция:

Предельное значение определяется клеткой (3,2) и

4. При увеличении S7 на единицу с 0 до 1 целевая функция уменьшится на 4. Цикл перераспределения в матрице условий:

ПН

Поставки

ui

ПО

2

4

6

1

7

6

5-1

9

5-1

0

3

2

4

6

5

4

-5

5

4

4

7

4

3

7

-3

7

8

2

0+1

3

1

1+1

-4

8

13

7

8

1

1

1

Спрос

8

5

5

vj

7

6

7

Целевая функция:

Предельное значение определяется клеткой (1,4) и

5. При увеличении S8 на единицу с 1 до 2 целевая функция увеличится на 1. Цикл перераспределения в матрице условий:

ПН

Поставки

ui

ПО

2

4

6

1

7

6

5-1

9

5-1

0

3

2

4

6

5

4

-5

5

4

4

7

4

3

7

-3

7

8

2

0+1

3

1-1

1

-4

8

13

7

8

1+1

1+1

1

Спрос

8

5

5

vj

7

6

7

Целевая функция:

Предельное значение определяется клеткой (1,4) и

1.3.3 Одновременное увеличение запасов и спроса.

При одновременном увеличении запасов поставщика Si и потребителя Di получаем:

1) Пусть S1 и D2 увеличатся на . При приращение целевой функции будет равно Невозможно составить цикл перераспределения только через базисные клетки, поэтому при любом оптимальное решение будет меняться:

ПН

Поставки

ui

ПО

2

4

6

1

7

6

5

9

5+

0

3

2

4

6

5

4

-5

5

4

4

7

4

3

7

-3

7

8

2

0

3

1

1

-4

8

13

7

8

1

1

1

Спрос

8+

5

5

vj

7

6

7

2) Пусть S3 и D4 увеличатся на . При приращение целевой функции будет равно Невозможно составить цикл перераспределения только через базисные клетки, поэтому при любом оптимальное решение будет меняться:

ПН

Поставки

ui

ПО

2

4

6

1

7

6

5

9

5

0

3

2

4

6

5

4+

-5

5

4

4

7

4

3

7

-3

7

8

2

0

3

1

1

-4

8

13

7

8

1

1

1

Спрос

8

5+

5

vj

7

6

7

3) Пусть S5 и D6 увеличатся на . При приращение целевой функции будет равно Составим цикл перераспределения, в данном случае он будет состоять из одной клетки (5,6), поэтому может принимать любые значения, прежнее решение останется оптимальным:

ПН

Поставки

ui

ПО

2

4

6

1

7

6

5

9

5

0

3

2

4

6

5

4

-5

5

4

4

7

4

3+1

7+

-3

7

8

2

0

3

1

1

-4

8

13

7

8

1

1

1

Спрос

8

5

5+

vj

7

6

7

2. Задача коммивояжера.

2.1. Математическая модель.

Математическая модель задачи коммивояжера в общем виде выглядит так:

решение есть цикл.

Для графа

задача коммивояжера описывается следующей моделью:

Целевая функция:

В каждый пункт назначения входит один и только один путь:

Из каждого пункта отправления выходит только один маршрут:

,

решение есть цикл.

2.2. Решение.

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

X0 = (1,2);(2,3);(3,4);(4,5);(5,6);(6,7);(7,8);(8,1)

Тогда F(X0) = 7 + 2 + 6 + ? + 4 + 3 + 5 + ? = 27

Для определения нижней границы множества приведем матрицу по строкам, для этого находим в каждой строке матрицы минимальный элемент.

i j

1

2

3

4

5

6

7

8

min

1

?

7

6

6

?

?

?

?

6

2

7

?

2

?

4

8

?

?

2

3

6

2

?

6

4

5

6

?

2

4

6

?

6

?

?

3

2

?

2

5

?

4

4

?

?

4

?

9

4

6

?

8

5

3

4

?

3

8

3

7

?

?

6

2

?

3

?

5

2

8

?

?

?

?

9

8

5

?

5

Затем вычитаем найденные минимумы из элементов рассматриваемой строки.

i j

1

2

3

4

5

6

7

8

1

?

1

0

0

?

?

?

?

2

?

?

0

?

2

6

?

?

3

4

0

?

4

2

3

4

?

4

4

?

4

?

?

1

?

?

5

?

0

?

?

?

0

?

5

6

?

5

2

0

1

?

0

5

7

?

?

?

0

?

?

?

3

8

?

?

?

?

4

3

0

?

Далее приводим по столбцам, для чего в каждом столбце находим минимальный элемент:

i j

1

2

3

4

5

6

7

8

1

?

1

0

0

?

?

?

?

2

?

?

0

?

2

6

?

?

3

4

0

?

4

2

3

4

?

4

4

?

4

?

?

1

?

?

5

?

0

?

?

?

0

?

5

6

?

5

2

0

1

?

0

5

7

?

?

?

0

?

?

?

3

8

?

?

?

?

4

3

0

?

min

4

0

0

0

1

0

0

3

После вычитания минимальных элементов получаем новую матрицу.

i j

1

2

3

4

5

6

7

8

1

?

1

0

0

?

?

?

?

2

1

?

0

?

1

6

?

?

3

0

0

?

4

1

3

4

?

4

0

?

4

?

?

1

?

?

5

?

0

?

?

?

0

?

2

6

?

5

2

0

0

?

0

2

7

?

?

?

0

?

?

?

0

8

?

?

?

?

3

3

0

?

Сумма найденных минимальных элементов определяет нижнюю границу Q:

Q(0)=( 6+2+2+2+4+3+2+5)+(4+0+0+0+1+0+0+3) = 34

Определяем ребро ветвления и разобьем все множество маршрутов относительно этого ребра на два подмножества (i,j) и (i*,j*).

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

i j

1

2

3

4

5

6

7

8

1

?

1

0(0)

0(0)

?

?

?

?

2

1

?

0(1)

?

1

6

?

?

3

0(0)

0(0)

?

4

1

3

4

?

4

0(0)

?

4

?

?

1

????

?


Подобные документы

  • Решение задачи линейного программирования симплекс-методом: постановка задачи, построение экономико-математической модели. Решение транспортной задачи методом потенциалов: построение исходного опорного плана, определение его оптимального значения.

    контрольная работа [118,5 K], добавлен 11.04.2012

  • Построения математической модели с целью получения максимальной прибыли предприятия, графическое решение задачи. Решение задачи с помощью надстройки SOLVER. Анализ изменений запасов ресурсов. Определение пределов изменения коэффициентов целевой функции.

    курсовая работа [2,4 M], добавлен 17.12.2014

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

    курсовая работа [79,2 K], добавлен 25.06.2011

  • Особенности решения транспортной задачи распределительным методом и анализ результатов. Построение математической модели, алгоритма. Создание программы для решения транспортной задачи распределительным методом в программной среде Borland Delphi 7.

    курсовая работа [1000,7 K], добавлен 23.06.2012

  • Математическая модель задачи: расчет объема производства, при котором средние постоянные издержки минимальны. Построение графика функции с помощью графического редактора MS Excel. Аналитическое исследование функции, зависящей от одной переменной.

    курсовая работа [599,7 K], добавлен 13.02.2010

  • Решение в среде Microsoft Excel с помощью программной модели "Поиск решения" транспортной задачи, системы нелинейных уравнений, задачи о назначениях. Составление уравнения регрессии по заданным значениям. Математические и алгоритмические модели.

    лабораторная работа [866,6 K], добавлен 23.07.2012

  • Методы решения задач линейного программирования: планирования производства, составления рациона, задачи о раскрое материалов и транспортной. Разработка экономико-математической модели и решение задачи с использованием компьютерного моделирования.

    курсовая работа [607,2 K], добавлен 13.03.2015

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

    курсовая работа [603,3 K], добавлен 21.10.2012

  • Построение математической модели корпуса судна. Изучение работы последней версии программы FastShip6. Построение теоретической поверхности корпуса теплохода, проходящего ремонт на судостроительном предприятии. Процесс построения поверхности по ординатам.

    дипломная работа [656,0 K], добавлен 24.03.2010

  • Алгоритм симплекс-метода. Задача на определение числа и состава базисных и свободных переменных, построение математической модели. Каноническая задача линейного программирования. Графический метод решения задачи. Разработки математической модели в Excel.

    курсовая работа [1,1 M], добавлен 18.05.2013

  • Разработка математической модели системы. Моделирование работы конвейера сборочного цеха в течении 8 часов. Определение вероятности пропуска секции. Расчет количества скомплектованных изделий за 8 часов. Исследование системы на имитационной модели.

    контрольная работа [98,3 K], добавлен 24.09.2014

  • Понятие математической модели, свойства и классификация. Характеристика элементов системы Mathcad. Алгоритмический анализ задачи: описание математической модели, графическая схема алгоритма. Реализация базовой модели и описание исследований MathCAD.

    реферат [1,0 M], добавлен 20.03.2014

  • Построение математической модели, описывающей процесс распространения пассивных загрязняющих веществ от сосредоточенных источников. Использование аппарата сопряженных задач для определения безопасных зон размещения объектов, загрязняющих атмосферу.

    дипломная работа [711,0 K], добавлен 18.07.2014

  • Метод решения математической модели на примере решения задач аналитической геометрии. Описание согласно заданному варианту методов решения задачи. Разработка математической модели на основе описанных методов. Параметры окружности минимального радиуса.

    лабораторная работа [310,6 K], добавлен 13.02.2009

  • Нахождение высоты конуса наименьшего объема, описанного около данного шара радиуса. Определение исследуемой функции, зависящей от одной переменной. Составление математической модели задачи. Построение графика заданной функции с помощью MS Excel.

    задача [3,2 M], добавлен 15.02.2010

  • Построение математической модели. Выбор, обоснование и описание метода решений прямой задачи линейного программирования симплекс-методом, с использованием симплексной таблицы. Составление и решение двойственной задачи. Анализ модели на чувствительность.

    курсовая работа [100,0 K], добавлен 31.10.2014

  • Критерий эффективности и функции в системе ограничений. Общая постановка задачи линейного программирования. Составление математической модели задачи. Алгоритмы решения задачи симплексным методом. Построение начального опорного решения методом Гаусса.

    курсовая работа [232,4 K], добавлен 01.06.2009

  • Краткий обзор решения транспортных задач. Экономическая интерпретация поставленной задачи. Разработка и описание алгоритма решения задачи. Построение математической модели. Решение задачи вручную и с помощью ЭВМ. Анализ модели на чувствительность.

    курсовая работа [844,3 K], добавлен 16.06.2011

  • Оптимизационные модели на производстве. Компьютерное моделирование и программные средства. Трехмерное моделирование в T-Flex. Инженерный анализ в ANSYS. Интерфейс табличного процессора MS Excel. Построение математической модели задачи, ее реализация.

    курсовая работа [5,2 M], добавлен 13.04.2014

  • Математическое программирование. Линейное программирование. Задачи линейного программирования. Графический метод решения задачи линейного программирования. Экономическая постановка задачи линейного программирования. Построение математической модели.

    курсовая работа [581,5 K], добавлен 13.10.2008

Работы в архивах красиво оформлены согласно требованиям ВУЗов и содержат рисунки, диаграммы, формулы и т.д.
PPT, PPTX и PDF-файлы представлены только в архивах.
Рекомендуем скачать работу.