close

Вход

Забыли?

вход по аккаунту

?

Информатизация обучения дисциплине «Исследования операций» на основе применения модельных операций.

код для вставкиСкачать
УДК 51: 372.8
ИНФОРМАТИЗАЦИЯ ОБУЧЕНИЯ ДИСЦИПЛИНЕ
«ИССЛЕДОВАНИЯ ОПЕРАЦИЙ»
НА ОСНОВЕ ПРИМЕНЕНИЯ МОДЕЛЬНЫХ ОПЕРАЦИЙ
© 2010 В. Г. Гетманов
докт. техн. наук, профессор
профессор каф. информатики и прикладной математики
e-mail: vgetm@starnet.ru
ГОУ ВПО «Московский городской педагогический университет»
Рассмотрена система модельных операций, ориентированная на повышение эффективности обучения дисциплине «Исследование операций» для студентов – будущих учителей информатики. Реализация указанной системы направлена на обеспечение информатизации образования.
Ключевые слова: информатизация образования, исследование операций, информатика
Предлагаемая система модельных операций ориентирована на повышение эффективности преподавания дисциплины «Исследование операций» для студентов – будущих учителей информатики. Применение указанной системы обеспечивает необходимую степень информатизации обучения.
Благодаря системе модельных операций данная дисциплина реализуется в четырѐх разделах. В первом разделе описываются собственно модельные операции, каждая
из которых иллюстрирует применение одного из возможных методов оптимизации.
Сюжеты модельных операций соответствуют предметной области, привычной для студентов, специализирующихся в области информатики. Во втором разделе в краткой
форме рассматриваются основные математические сведения, необходимые для дисциплины «Исследование операций» и адекватные модельным операциям. В третьем разделе приводятся необходимые определения операций, описываются виды операций, намечаются общие подходы к исследованию операций, обеспечивающие формирование
оптимальных операций. В четвѐртом разделе рассматриваются оптимизационные методы для модельных операций, описанных в первом разделе; применение методов оптимизации доводится до получения численных результатов. Таким образом, осуществляется сквозная и замкнутая методика преподавания данной дисциплины, основанная на
модельных операциях. Все материалы, сформированные в первом, втором и третьем
разделах, используются в четвѐртом разделе дисциплины.
Предлагаемая система модельных операций предназначена для иллюстрации методов безусловной оптимизации, методов оптимизация с ограничениями -равенствами,
методов линейного программирования, численных методов оптимизации, методов нелинейного программирования, а также распространяется на многокритериальную оптимизацию, методы теории игр, методы динамического программирования и частично
методы массового обслуживания.
Рассмотрим примеры модельных операций.
1.Модельная операция планирования поездки в учебное заведение. Рассмотрим упрощѐнную модельную операцию поездки утром из дома, расположенного в
пункте А, в школу, расположенную в пункте Б [Вентцель 1972]. Положим, что пункты
А и В связывают n различных транспортных маршрутов; i – номер маршрута,
i  1,..., n . Будем полагать, что на каждом из маршрутов с любым номером возможны по
m различных транспортных комбинаций, которыми можно воспользоваться для поездки, j – номер варианта транспортной комбинации, j  1,..., m . Переменные i, j выступают в качестве параметров операции.
Например, маршрут №1 состоит из следующих вариантов транспортных комбинаций: вариант 1: метро–трамвай–такси, вариант 2: троллейбус–электричка–речной
трамвай–такси, вариант 3: автобус–троллейбус; маршрут №2 включает: вариант 1: метро–метро–автобус–трамвай, вариант 2: такси–автобус, вариант 3: трамвай–троллейбус–
такси–метро.
Планирование для модельной операции в данном случае состоит в выборе оптимального номера маршрута i  и оптимального номера варианта транспортной комбинации j  .
Для маршрута с номером i и транспортной комбинации с номером j время перемещения из А в Б составляет величину t ij , i  1,..., n , j  1,..., m . Вполне естественным выглядит ограничение
t ij  t 0
– время поездки не должно быть больше заданной величины t 0 . Индексы i, j ,
для которых обеспечивается ограничение (1), будем определять как допустимые. Введѐм обозначение для множества допустимых индексов S
S  {i, j : (t ij  t 0 )} .
Любой поездке с параметрами i, j может быть поставлена в соответствие еѐ
стоимость Wij . Фактически, величины t ij и Wij представляют собой прямоугольные
таблицы с размерами m  n . Множество допустимых индексов S представляет собой
часть прямоугольной таблицы индексов размеров m  n .
Задача состоит в выборе оптимальных индексов i  , j  – соответствующего номера маршрута и номера варианта транспортной комбинации, которые обеспечивают минимальное значение стоимости поездки Wij среди множества S допустимых индексов
i, j . Минимизация критерия эффективности Wij по множеству допустимых индексов
i, j  S условно может быть записана следующим образом
(i  , j  )  arg{ min Wij } .
i , jS
На основе данного примера следует отметить, что операция характеризуется четырьмя составляющими: параметрами, ограничениями для параметров (допустимыми
множествами), критерием эффективности и соответствующей процедурой оптимизации.
2. Модельная операция планирования местоположения учебного заведения.
Рассмотрим упрощѐнную операцию планирования местоположения учебного заведения
[Ширяев 2007].
2.1. Пусть заданы n населѐнных пунктов с координатами x i  ( x1i , x2i ) , i  1,..., n .
Школа находится в точке с координатами x T  ( x1 , x2 ) . Требуется выбрать координаты
местоположения школы таким образом, чтобы суммарные транспортные расходы на
перемещение учащихся из населѐнных пунктов были бы минимальными.
Возможны два варианта критериев, связанных с транспортными расходами. Первый критерий записывается очевидным образом:
T
n
F1 ( x1 , x2 )   ( x1i  x1 ) 2  ( x2i  x2 ) 2 .
i 1
(1)
Целевая функция F1 ( x1 , x2 ) соответствует случаю, когда транспортные затраты,
например связанные с расходом бензина, растут пропорционально суммарной длины
маршрута. Второй критерий, который можно трактовать как обобщѐнное расстояние,
записывается следующим образом
n
F2 ( x1 , x2 )   (( x1i  x1 ) 2  ( x2i  x2 ) 2 ) .
i 1
Целевая функция F2 ( x1 , x2 ) соответствует случаю, когда транспортные затраты
нелинейно зависят от длины маршрута, что достаточно часто имеет место в действительности; здесь принята упрощѐнная модель для целевой функции, зависящей от расстояний по квадратичному закону.
В обоих случаях координаты x T  ( x1 , x2 ) ничем не ограничены, что означает,
что точка x  R 2 может быть расположена в любом месте плоскости R 2 . В данном
случае допустимое множество S совпадает с R 2 ( S  R 2 ) . Задача отыскания оптимального расположения школы x  по критериями F1 ( x1 , x2 ) , F1 ( x1 , x2 ) может быть представлена выражениями (2)
x   arg{ min2 F1 ( x1 , x2 )} , x   arg{ min2 F2 ( x1 , x2 )} .
xR
(2)
xR
Таким образом, операция планирования местоположения школы сводится к задаче безусловной оптимизации
2.2. Пусть снова заданы n населѐнных пунктов с координатами x i  ( x1i , x2i ) ,
i  1,..., n , и между населѐнными пунктами проложена прямолинейная дорога. Школа
должна быть расположена на указанной дороге в точке с координатами x T  ( x1 , x2 ) . В
предложенных координатах уравнение прямой линии дороги имеет вид
ax1  bx2  c  0 .
Также как и для случая 1, возможны два варианта критериев транспортных расходов, которые записываются аналогично:
T
n
n
F1 ( x1 , x2 )   ( x1i  x1 ) 2  ( x2i  x2 ) 2 , F2 ( x1 , x2 )   (( x1i  x1 ) 2  ( x2i  x2 ) 2 ) .
i 1
i 1
Однако для данного случая координаты школы x  ( x1 , x2 ) подвержены ограничению: они лежат на прямой линии, уравнение которой задано. Можно утверждать,
что предлагаемые критерии должны быть минимизированы на множестве точек S ,
удовлетворяющих условию S  {x1 , x2 : (ax1  bx2  c  0)}
T
Задачи отыскания оптимального расположения школы x  по критериям
F1 ( x1 , x2 ) , F2 ( x1 , x2 ) могут быть представлены следующими выражениями:
x   arg{ min F1 ( x1 , x2 )} , x   arg{ min F2 ( x1 , x2 )} .
xS
xS
Таким образом, (3) представляет собой задачу условной оптимизации с ограничением типа равенство.
3. Модельная операция планирования работы учебного предприятия. Операция планирования работы предприятия реализуется с учѐтом ограничений на ресурсы
[Вентцель 2004]. Положим, что некоторое учебное предприятие выпускает продукцию
в виде изделий двух видов, которая обозначается как изделие №1 и изделие №2. Рыночная стоимость изделия №1 составляет 2 единицы (например, в $), стоимость изделия №2 – 3 единицы.
(3)
На изготовление изделий расходуются материалы трѐх видов. Количество материалов (в условных единицах), расходуемых на изготовление изделия №1 и №2, приведены в следующей таблице.
Материал
№1
Изделие №1
Изделие №2
Материал
№2
Материал №3
1
1.5
9
2
1
4
Запасы материала №1 – 200 единиц, материала №2 – 150 единиц и материала
№3 – 810 единиц.
Пусть план выпуска составляет х1 - число изделий №1, х 2 - число изделий №2.
Требуется максимизировать суммарную стоимость продажи продукции при ограничениях на количества материалов
f ( x)  2 x1  3x2
1. x1  2 x2  200 . 4. х1  0 .
2. 1.5x1  x2  150 . 5. х2  0 .
3. 9 x1  4 x2  810 .
Сформулирована типичная задача линейного программирования, для которой
показатель эффективности – суммарная стоимость продажи продукции – является линейной функцией и ограничения представляют собой линейные неравенства (равенства). Введѐнные неравенства определяют ограничения на ресурсы.
Множество точек x  S , удовлетворяющих введѐнным неравенствам, называется
допустимым
S  {x : ( x1  2 x2  200 , 1.5x1  x2  150 , 9 x1  4 x2  810 , х1  0 , х2  0)} .
Задача планирования работы учебного заведения состоит в назначении оптиТ
мального плана х   ( х1 , х2 ) выпуска продукции – количества изделий №1 и №2 с
учѐтом имеющихся ограничений на ресурсы и обеспечивающей максимальное значение
суммарной стоимост. продажи продукции. Максимальное значение критерия эффективности
х   arg{ min f ( x)  2 x1  3x2} .
xS
4. Модельная операция планирования транспортировки школьных завтраков. Рассмотрим простейший пример планирования операции транспортировки школьных завтраков, являющейся так называемой транспортной задачей [Вентцель 2004].
Пусть в пунктах с номерами i  1,..., n находятся фабрики-кухни, в которых производятся стандартные школьные завтраки в количествах (веса) X 1 ,..., X n за одну смену. В пунктах c номерами j  1,..., m находятся школы, в которые необходимо доставить завтраки в количествах, соответствующих сделанным заявкам Y1 ,..., Ym .
Обозначим через хij количество завтраков в килограммах, перевозимых из фабрики-кухни c номером i в школу с номером j . Очевидно, что величины хij не могут
быть отрицательными
хij  0 , i  1,..., n , j  1,..., m .
(4)
С фабрики-кухни с номером i нельзя вывезти завтраки в количестве большем,
чем там было их произведено в смену. Это означает, что величины хij должны удовлетворять системе неравенств (5)
m
x
j 1
ij
 X i , i  1,..., n .
(5)
Условие выполнения заказов школ состоит в том, чтобы величины хij удовлетворяли системе неравенств
n
x
i 1
ij
 Y j , j  1,..., m .
(6)
Следует заметить, что должно выполняться неравенство
n
m
i 1
j 1
 X i  Y j ,
имеющее вполне очевидный физический смысл.
Задание величин хij , удовлетворяющих неравенствам (4)–(6), фактически означает определение плана транспортировки и составляет предмет операции транспортировки. Величины (параметры) хij i  1,..., n , j  1,..., m могут быть сведены в вектор
х Т  ( x11,..., x1n, ,..., xm1 ,..., xmn ) размерности mn . Векторы х , удовлетворяющие условиям (4), (5), составляют допустимое множество Х 0 ; допустимый вектор х принадлежит
допустимому множеству х  Х 0
Х 0  {x : (
m
n
j 1
i 1
 xij  X i ; i  1,..., n , ;  xij  Y j , j  1,..., m ; хij  0 , i  1,..., n ,
j  1,..., m)}.
Через  ij будем обозначать стоимость перевозки единицы груза между фабрикой-кухней i и школой j . Тогда стоимость транспортировки, обозначаемая как F (x) ,
соответствующая вектору х , может быть определена формулой
n
m
F (x)   xij ij .
i 1 j 1
Функция F (x) может служить в качестве показателя эффективности операции
транспортировки. Операции транспортировки отличаются стоимостью. Наиболее эффективная операция транспортировки х  может быть сформулирована следующим образом
x   arg{ min
xX 0
n
m
 x 
i 1 j 1
ij
ij
}.
5. Модельная операция составления меню школьного завтрака. Рассмотрим
упрощѐнную операцию составления набора продуктов (меню) для школьного завтрака
[Вентцель 2004]. Положим, что предполагаемый школьный завтрак состоит из n продуктов, включая, например, хлеб, мясо, молоко, рыба, овощи, фрукты и т.д.; номер
продукта будем обозначать индексом i , 1  i  n . Каждый из продуктов содержит набор из m полезных веществ (составляющих); такими веществами могут быть белки,
жиры, углеводы, в качестве составляющих могут быть калории. Номера полезных веществ будем обозначать индексом j , 1  j  m .
(7)
Пусть удельное содержание перечисленных полезных веществ в указанных продуктах определяется коэффициентом  ji , где i – номер продукта, j – номер полезного
вещества;  ji – количество мг полезного вещества в единице веса рассматриваемого
продукта. Данные по коэффициентам могут быть сведены в прямоугольную матрицу А
a11 a12 . a1n
a
a 22 . a 2 m
.
A  21
.
. . .
a m1 a n 2 . a mn
Весовые количества продуктов с номерами 1  i  n , входящих в школьный завтрак, определяются величинами х Т  ( x1 , x 2 ,…, x n ) . Основываясь на значениях xi и
коэффициентах  ji , можно вычислить количества полезных веществ в завтраке; очевидно, количество y j полезного вещества с номером j в предлагаемом завтраке может
быть определено суммированием
n

i 1
ji
xi  y j .
Введѐм нормы b j на содержание полезных веществ в завтраке, 1  j  m ,
b  (b1 , b2 ,..., bm ) . Очевидно, что величины х1 , х2 ,..., хn должны быть такими, чтобы
были выполнены неравенства, физический смысл которых очевиден: количество j -ого
полезного вещества в завтраке должно быть не меньше, чем величина b j
T
n

i 1
ji
xi  b j , 1  j  m .
Приведѐнные неравенства могут быть переписаны в векторно-матричном виде
А х  b.
Дополнительно следует учесть, что величины х1 , х2 ,..., хn должны быть положительными: хi  0 , 1  i  n или в векторном виде x  0 . Окончательно следует обозначить множество S  R n , к которому должны принадлежать векторы x
S  {x : ( Ax  0, x  0)} .
Введѐм удельные стоимости продуктов в виде коэффициентов с i , 1  i  n .
Стоимость завтрака, очевидно, может быть вычислена на основе следующей формулы
n
f ( x )   ci xi  c T x .
i 1
Оптимальное по стоимости меню – набор продуктов, удовлетворяющий нормам
содержания питательных веществ и минимальный по стоимости, – может быть найден
на основе задачи минимизации
x   arg{ min f (x)} .
xS
6. Модельная операция планирования работы учебного с/х предприятия.
Рассмотрим упрощѐнную модельную операцию планирования работы учебного с/х
предприятия [Моисеев 1981]. Пусть площадь участка, занятая посевом i -ой культурой,
составляет величину x i , i  1,..., n . Общая располагаемая площадь, которая может быть
отведена под посевы, равняется величине X 0 . Величины площадей x i и общая площадь участка X 0 удовлетворяют очевидным неравенствам
xi  0 , i  1,..., n ,
n
x
i 1
i
 X0 .
Обозначим через z i  0 количество удобрений, вносимых на единицу площади,
занятой i -ой культурой, i  1,..., n . Для данной операции параметрами будут величины
xi , z i , i  1,..., n . Указанные параметры требуют своего определения с учѐтом максимизации задаваемого критерия эффективности.
Суммарное количество удобрений, которое может быть внесено, ограничено
общим запасом Z 0
n
x z
i 1
i i
 Z0 .
Векторы x, z , входящие в задачу, принадлежат допустимому множеству S , образованному системой нелинейных неравенств
S  {x, z : ( xi  0, z i  0 , i  1,..., n ,
n
 xi  X 0 ,
i 1
n
x z
i 1
i i
 Z0 ) } .
Допустим, что урожайность единицы площади, занятой i -ой культурой, реализуемая от внесения z i удобрений, описывается функцией известного вида f i ( z i ) . Тогда
урожай i -ой культуры на площади xi будет равен величине xi f i ( z i ) .
Положим, что продажная стоимость единицы веса собранной i -ой культуры
принимает значение р i , i  1,..., n . Стоимость единицы веса удобрений равняется величине q . Введѐм показатель эффективности F ( x, z ) , равный разности средств, полученной от реализации урожая и средств, затраченных на удобрения
n
n
i 1
i 1
F ( x, z )   pi xi f ( z i )  q  xi z i .
Стандартная запись данной задачи, связанной с распределением площадей и
удобрений, выглядит следующим образом: отыскивается минимум функции F ( x, z )
при условии, что векторы x, z принадлежат множеству S
( x  , z  )  arg{ min F ( x, z )} .
x , zS
Сформулирована типичная задача нелинейного программирования, для которой
показатель эффективности является нелинейной функцией и ограничения представляют собой систему нелинейных неравенств и равенств.
7. Система модельных операций может расширяться по содержанию и совершенствоваться методологически. Еѐ применение способствует обеспечению информатизации обучения (образования) в рассматриваемой предметной области. В дальнейшем эту систему целесообразно дополнить модельной операцией распределения ресурсов для иллюстрации метода динамического программирования, модельной игровой
операцией и модельной операцией массового обслуживания. В процессе преподавания
в МГПУ дисциплины «Исследование операций» данная методология модельных операций позволила обеспечить хорошее усвоение материала и оказалась успешной при подготовке студентов – будущих учителей информатики.
Библиографический список
Вентцель Е. С. Исследование операций. М.: Советское радио, 1972. 485 с.
Вентцель Е. С. Исследование операций: задачи, принципы, методики. М.: Высшая школа, 2004. 208 с.
Моисеев Н. Н. Математические задачи системного анализа. М.: Наука, 1981.
488 с.
Ширяев В. И. Исследование операций и численные методы оптимизации. М.:
Комкнига, 2007. 216 с
Документ
Категория
Без категории
Просмотров
5
Размер файла
392 Кб
Теги
дисциплины, модельный, обучения, информатизация, применению, основы, операция, исследование
1/--страниц
Пожаловаться на содержимое документа