- •Системный анализ и исследование операций
- •В 2 частях
- •Часть II Гомель 2005
- •Содержание
- •Введение
- •Практическая работа n1 транспортные задачи
- •Решение транспортной задачи
- •Метод северо-западного угла
- •Метод наименьшей стоимости
- •Метод Фогеля
- •Оптимизация плана транспортной задачи
- •Распределительный метод
- •Метод потенциалов
- •Практическая работа n2 транспортная задача на min времени
- •Метод запрещённых клеток.
- •Практическая работа №3 задача о назначениях
- •Решение через нуль-базис
- •Практическая работа №4 определение кратчайшего маршрута
- •Определение кратчайшего пути на сети без циклов
- •Определение кратчайшего пути на сети с циклами
- •Практическая работа № 5 пропускная способность сети
- •Алгоритм нахождения максимального потока
- •Тестовый пример
- •Практическая работа №6 календарное планирование
- •Сетевое представление программы (сетевая модель)
- •Правила построения сетевой модели
- •Расчет сетевой модели
- •Определение критического пути
- •Определение резервов времени
- •Практическая работа №7 антагонистические игры
- •Чистые и смешанные стратегии
- •Упрощение игры
- •Игровые модели. Графоаналитический метод решения
- •Практическая работа №8 игровые модели. Решение методом итераций
- •Практическая работа №9 решение задач линейного программирования с помощью игровых моделей
- •Литература
- •Приложение
- •Давыдов владимир семёнович системный анализ и исследование операций Практическое пособие
- •Часть II в авторской редакции
- •246019, Г. Гомель, ул. Советская, 104
- •246019, Г. Гомель, ул. Советская, 104
министерство образования республики беларусь
Учреждение образования
«Гомельский государственный университет имени Франциска Скорины»
В.С. Давыдов
Системный анализ и исследование операций
Практическое пособие
В 2 частях
Часть II Гомель 2005
УДК 519. 7+ 519. 8 (075. 8)
ББК 22.183 Я73
Д138
Рецензенты:
кафедра автоматизированных систем обработки информации учреждения образования «Гомельский государственный университет имени Франциска Скорины»,
В.Д. Левчук, доцент, кандидат технических наук.
Рекомендовано к изданию научно-методическим советом учреждения образования «Гомельский государственный университет имени Франциска Скорины» 30 марта 2005 года, протокол № 7.
Давыдов В. С.
Д138 Системный анализ и исследование операций: Практическое пособие. В 2 частях. Ч.II. / В. С. Давыдов; Министерство образования РБ, учреждение образования «Гомельский государственный университет имени Франциска Скорины». - Гомель, ГГУ им Ф. Скорины, 2005. – 91 c.
Практическое пособие «Системный анализ и исследование операций» адресовано студентам специальности 1-53 01 02 “АСОИ” и включает теоретические сведения, задания и требования по выполнению практических работ.
УДК 519. 7+ 519. 8 (075. 8)
ББК 22.183 Я73
Давыдов В. С., 2005
Учреждение образования
«Гомельский государственный университет
имени Франциска Скорины», 2005
Содержание
ВВЕДЕНИЕ 4
Практическая работа N1 5
ТРАНСПОРТНЫЕ ЗАДАЧИ 5
Практическая работа N2 16
ТРАНСПОРТНАЯ ЗАДАЧА НА MIN ВРЕМЕНИ 16
Практическая работа №3 19
ЗАДАЧА О НАЗНАЧЕНИЯХ 19
Практическая работа №4 24
ОПРЕДЕЛЕНИЕ КРАТЧАЙШЕГО МАРШРУТА 24
Практическая работа № 5 29
ПРОПУСКНАЯ СПОСОБНОСТЬ СЕТИ 29
Практическая работа №6 33
КАЛЕНДАРНОЕ ПЛАНИРОВАНИЕ 33
Практическая работа №7 41
АНТАГОНИСТИЧЕСКИЕ ИГРЫ 42
Практическая работа №8 52
ИГРОВЫЕ МОДЕЛИ. РЕШЕНИЕ МЕТОДОМ ИТЕРАЦИЙ 52
Практическая работа №9 56
РЕШЕНИЕ ЗАДАЧ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ С ПОМОЩЬЮ ИГРОВЫХ МОДЕЛЕЙ 56
ЛИТЕРАТУРА 63
ПРИЛОЖЕНИЕ 64
Таблица П1. Варианты заданий транспортной модели 64
Таблица П2. Варианты заданий задачи о назначениях 68
Таблица П3. Варианты задач определения кратчайшего пути 73
Таблица П4. Задания по определению максимального потока 77
Таблица П5. Варианты задач календарного планирования 82
Таблица П6. Варианты задач игровых моделей 87
Введение
Выполнение практических работ по курсу "Системный анализ и исследование операций" призвано помочь студентам в овладении теоретическими знаниями и их применении при решении практических задач
Выполнение практических работ включает:
Изучение студентами необходимого теоретического материала по теме работы.
Построение алгоритма решения задачи.
Составление программы.
Решение контрольного примера.
Номер варианта определяется порядковым номером в списке группы.
Каждая работа оформляется отдельно и подшивается в папку.
В данном пособии рассмотрены модели: транспортные, сетевые, антогонистическиe игры.
Практическая работа n1 транспортные задачи
Цель работы: Изучение теоретических и практических приёмов решения транспортных задач
Транспортные задачи составляют класс задач линейного программирования, специфика математической модели которых позволяет применять для их решения наряду с общими методами линейного программирования специальные методы, значительно сокращающие процесс вычислений.
Транспортная модель используется при разработке плана перевозок одного вида продукции из нескольких пунктов отправления в пункты назначения. При построении модели используются:
1) величины, характеризующие объем производства в каждом исходном пункте и спрос в каждом пункте назначения;
2) стоимость перевозки единицы продукции из каждого исходного пункта в каждый пункт назначения.
Компактный способ представления транспортной модели предполагает использование транспортной таблицы, имеющей вид матрицы, в которой строки соответствуют исходным пунктам, а столбцы — пунктам назначения. Коэффициенты стоимости cij расположены в правом верхнем углу каждой ячейки (i, j), в правом столбце отмечают имеющиеся запасы ai, а в нижней строке - величины спроса bj. Обычно в ячейках таблицы записывают и решения задачи в виде Xij, а также отмечают вспомогательные вычисления.Пусть xji – количество продукции перевозимой из i-го пункта в j-ый пункт; cij – стоимость перевозки из i-го пункта в j-ый пункт. Тогда модель будет следующей:
Найти min при условии
, запасы, , запросы,
.
Таблица 1.1. Транспортная таблица
Пункты отправления |
Пункты назначения |
Запасы |
||||
B1 |
...... |
Bi |
...... |
Bn |
||
A1 |
Сi,1 Xi,1 |
...... |
С1,i X1,j |
|
С1,n X1,n |
a1 |
...
|
…
|
…
|
...
|
…
|
...
|
…
|
Ai |
Сi,1 Xi,1 |
...... |
Сi,j Xi,j |
|
Сi,n Xi,n
|
ai |
...
|
...
|
…
|
...
|
…
|
...
|
...
|
Am |
Сm,1 Xm,1 |
...... |
Сm,j Xm,j |
|
Сm,n Xm,n |
am |
Потребности |
b1 |
… |
bi |
.... |
bn |
|
Если общая потребность в грузе в пунктах назначения равна запасу груза в пунктах отправления, = ,
то модель такой транспортной задачи называется закрытой (сбалансированной). Если же указанное условие не выполняется, то модель транспортной задачи называется открытой (несбалансированной). Сбалансированная модель отличается от вышеприведенной модели лишь тем, что все ограничения превращаются в равенства,
, , xij0 для всех i и j,
то есть весь продукт из i-го пункта поставки должен быть вывезен и запросы всех пунктов j потребления удовлетворены полностью.
В реальных условиях не всегда объем производства равен спросу или превосходит его. Однако транспортную модель всегда можно сбалансировать. Помимо того, что баланс делает удобным моделирование определенных практических ситуаций, он полезен для разработки метода решения, который полностью учитывает особую структуру транспортной модели.