Пример выбора оптимального маршрута

Пусть задана схема возможных маршрутов движения из пункта А в пункт Б (рис.4). Каждый квадратик на схеме изображает один из населенных пунктов. Стоимость переезда из пункта i в пункт j известна и равна c_ij. Требуется определить такой путь из пункта А в пункт Б, общая стоимость передвижения по которому будет минимальной.

Решение. Из представленной схемы видно, что весь путь от пункта А до пункта Б можно разбить на 4 этапа. Т.е. число шагов в решении n =4.

Запишем уравнения Беллмана (4.8) для случая минимизации целевой функции.

(4.10)

Применительно к данной задаче рекуррентные соотношения (4.10) можно записать немного проще. Минимальная стоимость последующего пути из пункта i до пункта Б, начиная с шага k, находится по формуле:

(4.10)

где - минимальная стоимость пути от пункта j до конечного пункта Б, c_ij – стоимость переезда из пункта i в пункт j.

Начинаем поиск оптимального маршрута с последнего шага:

k =4

Переходим к предыдущему шагу, определяем оптимальные решения на двух последних шагах:

k =3

Переходим к предыдущему шагу, определяем оптимальные решения на трех последних шагах:

k =2

Для первого шага получаем:

k =1

Минимальная суммарная стоимость пути из пункта А в пункт Б равна . В процессе решения получены две последовательности оптимальных решений и соответствующих состояний (пунктов), т.к. при k =2 существует 2 оптимальных дальнейших маршрута.

Первое оптимальное решение (маршрут А-2-4-6-Б):

.

Второе оптимальное решение (маршрут А-2-5-7-Б):

.

Заключение

Рассмотренные методы решения могут быть применены для решения большого круга различных по физической и экономической природе задач.

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

Литература

1. Исследование операций в экономике: Учеб.пособие для вузов / Н.Ш.Кремер, Б.А.Путко, И.М.Тришин, М.Н.Фридман; Под ред.проф. Н.Ш.Кремера. – М.: ЮНИТИ, 2005.

2. Экономико-математические методы и модели. Задачник: уч.-метод. пособие / кол.авторов; под ред. С.И.Макарова, С.А.Севастьяновой. – М.: КНОРУС, 2008. – 208 с.

3. Вентцель, Е.С. Исследование операций. /Е.С.Вентцель. – М.: Сов. радио, 1972.

4. Просветов, Г.И. Методы оптимизации. Учебно-практическое пособие / Г.И.Просветов. - М.: Изд-во «Альфа-Пресс», 2009. - 168 с.

Содержание

Введение. 3

Тема 1. Основы исследования операций. 3

1.1. Основные определения. 3

1.2. Типичные задачи исследования операций. 4

1.3. Общая постановка задачи исследования операции. 6

1.4. Классификация задач исследования операций. 7

Тема 2. Задачи линейного программирования. 9

2.1. Общая задача линейного программирования. 9

2.2. Допустимые базисные решения и многогранник решений. 10

2.3. Симплексный метод. 12

2.4. Решение задачи отыскания максимума линейной функции. 13

2.5. Отыскание минимума линейной функции. 17

2.6. Определение первоначального допустимого базисного решения. 20

2.7. Особые случаи симплексного метода. 22

2.8. Метод искусственного базиса (М-метод) 26

2.9. Двойственные задачи. 28

2.10. Экономическая интерпретация двойственной задачи. 31

2.11. Решение двойственной задачи и определение интервалов устойчивости двойственных оценок оптимального решения. 33

2.12. Задачи целочисленного программирования. 35

Тема 3. Транспортная задача. 39

3.1. Экономико-математическая модель транспортной задачи. 39

3.2. Первоначальное распределение поставок методом наименьших затрат. 42

3.3. Метод «северо-западного угла». 45

3.4. Проверка плана на оптимальность. Метод потенциалов. 48

Тема 4. Задачи динамического программирования. 53

4.1. Общая постановка задачи. 53

4.2. Принцип оптимальности и уравнения Беллмана. 55

4.3. Пример выбора оптимального маршрута. 59

Заключение. 61

Литература. 61

Содержание. 62

Учебное издание

Лукиных Ирина Григорьевна

МЕТОДЫ ОПТИМАЛЬНЫХ РЕШЕНИЙ

КУРС ЛЕКЦИЙ

Учебное пособие

Подписано в печать. Печать цифровая. Бумага для офисной техники.

Усл. печ. л.. Тираж 50 экз. Заказ

Федеральное государственное бюджетное образовательное учреждение высшего профессионального образования «Вятский государственный университет»

610000, Киров, ул. Московская, 36, тел.: [phone], http://vyatsu.ru

[1] Institute of Electrical and Electronics Engineers (I triple E — «Ай трипл и») — международная некоммерческая ассоциация специалистов в области техники, мировой лидер в области разработки стандартов по радиоэлектронике и электротехнике

Дата добавления: 2014-01-06