Номинация: “Оригинальные сценарии уроков”

Дидактическая цель: Дать ученикам понятия “управление”, “оптимальное управление”. Поставить задачу оптимального управления. Выработать умения и навыки работы с учебным материалом. На основе ранее изученного материала и составленной программы закрепить навыки решения экономических задач.

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

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

Характеристика темы урока

С этой темы начинается решение информационно-логических задач с помощью ЭВМ и закладываются основы для использования компьютера в будущей профессиональной деятельности. Теоретическая часть темы – продолжение изучения экономики, математических методов решения задач линейного программирования. Работа по данной теме носит исследовательский характер, так как ребята учатся использовать один из математических методов исследования операций в экономике. Учитывая уровень математической подготовки школьников, изложение учебного материала ведется в быстром темпе, с использованием пошагового закрепления материала, с применением элементов самостоятельной работы.

Методы обучения

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

Структура урока

1. Объяснение нового материала.

2. Построение экономико-математической модели задачи.

3. Постановка задачи оптимального управления.

4. Повторение алгебры симплекс-метода.

5. Алгоритм решения поставленной задачи симплекс-методом.

6. Проверка результатов работы программы.

7. Домашнее задание.

Ход урока

1. Для лучшего понимания существа процесса управления рассмотрим пример кошки, преследующей мышку. Для того чтобы настичь мышь, кошка должна организовать свои действия. Следовательно, процесс преследования является процессом управления. Началу преследования должно предшествовать появление мышки. То есть должна быть создана ситуация, при которой возникает цель, достижение которой является необходимым или желательным. Прежде чем начать преследование, кошка должна оценить сложившуюся ситуацию и сопоставить ее со своими желаниями и возможностями. Оценка ситуации завершается принятием решения о том, следует пытаться догнать мышку или нет. Только после того, как принято решение о преследовании, кошка приступает к организации своего движения, ставя при этом цель догнать мышь за кратчайшее время или при наименьшей затрате сил. В этом примере можно отчетливо различить четыре этапа, характерные для любого процесса управления: появление цели, оценка ситуации, принятие решения и исполнение принятого решения. Однако этап появления цели предшествует началу процесса управления, и его мы исключим из рассмотрения. Учитывая также, что при управлении сложными процессами оценка ситуации производится на основе собранной и обработанной информации, приходим к следующим трем этапам процесса управления: сбор и обработка информации с целью оценки сложившейся ситуации, принятие решения о наиболее целесообразных действиях, исполнение принятого решения. Иногда бывает необходим еще четвертый этап – контроль исполнения решения.

Все этапы процесса управления находятся в тесной взаимосвязи. Этап принятия решения требует рассмотрения возможных способов реализации принятого решения. Так, для принятия решения об отказе от преследования нужно убедиться, что преследование бесполезно, а для этого нужно хотя бы грубо проанализировать возможные способы преследования. Иногда в подобных случаях процесс управления разбивается на несколько последовательных шагов. Примером может служить процесс управления ракетой при запуске ее с Земли на Луну. Можно выделить следующие шаги: вывод ракеты на околоземную орбиту, организация движения ракеты в направлении Луны, перевод ракеты на окололунную орбиту, прилунение. Однако во многих случаях разделение сложного процесса управления на шаги оказывается весьма сложной задачей. Так, в процессе преследования мышки приходится иметь дело с непрерывно меняющейся ситуацией, вызванной стремлением мышки уйти от преследования. Кошка должна непрерывно оценивать ситуацию и мгновенно принимать новые решения.

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

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

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

б) На крупных промышленных предприятиях осуществление административных функций одним человеком невозможно. Каждое отдельное специализированное подразделение крупной организации выполняет определенную часть общей работы, руководствуясь общими целями предприятия. Однако у каждого специализированного подразделения возникают и свои собственные цели. Эти цели не всегда согласуются, а иногда приходят в противоречие друг с другом. В качестве примера можно рассмотреть проблему обеспечения предприятия запасами. Отдельное подразделение может быть заинтересовано в значительном увеличении запасов на складе для обеспечения бесперебойного выпуска своей продукции. Но при ограниченном объеме складских помещений это приводит к снижению запасов для других подразделений. В результате возникает задача – выработка такой стратегии в отношении запасов, которая была бы наиболее благоприятна для всего предприятия в целом. При решении подобных задач необходимо очень тонкое понимание целей отдельных подразделений и такое их согласование, чтобы они не приходили в противоречие ни друг с другом, ни с общими целями предприятия. Неправильное решение в условиях крупного предприятия может принести немалый ущерб. Ясно, что в этом случае недостаточно базироваться только на своих знаниях, опыте, интуиции. Необходимы научные методы.

Специфическая особенность задач такого типа состоит в том, что решение может существенно отразиться на работе всего предприятия. Поэтому принятие окончательного решения всегда относится к компетенции ответственного лица.

Задачу управления мы будем рассматривать в дальнейшем как математическую задачу. В отличие от других математических задач она допускает не одно решение, а множество различных. Это связано с тем, что в задачах управления есть, как правило, много способов организации какого-либо процесса, которые приводят к достижению поставленной цели. В тех случаях, когда цель управления может быть достигнута несколькими различными способами, на способ управления можно наложить добавочные требования. Тогда задача управления состоит в том, чтобы из множества решений, обеспечивающих достижение цели, выбрать одно, которое требует наименьшей затраты ресурсов. Или основанием для предпочтения какого-либо способа управления могут служить иные требования, налагаемые на систему управления: стоимость обслуживания, надежность и т.д. Математическое выражение, дающее количественную оценку степени выполнения наложенных на способ управления требований, называется критерием качества управления. Наиболее предпочитаемым или оптимальным способом управления будет такой, при котором критерий качества управления достигает минимального (иногда максимального) значения. При выборе, например, режима полета за критерий качества управления можно принять или выражение для количества топлива, расходуемого на единицу пути, или путь, проходимый за счет единицы топлива. Наиболее экономичному, то есть оптимальному, режиму будет соответствовать или минимальное (в первом случае), или максимальное (во втором случае) значение критерия качества управления. Для того чтобы решить задачу управления, необходимо построить ее экономико-математическую модель.

2. Для построения экономико-математической модели требуется последовательное выполнение ряда работ: разработка экономико-математических моделей; подготовка соответствующих алгоритмов и вычислительных схем; программирование для компьютера; формирование необходимой информации (исходных данных), требующейся для проведения соответствующих расчетов; проведение вычислений на компьютере, анализ полученных результатов и их использование в практической деятельности. Экономико-математическая модель представляет собой выражение в математической форме (в виде систем уравнений, неравенств, функций и т.д.) количественных зависимостей в каком-либо реальном экономическом процессе. При этом должна обязательно формулироваться целевая функция. Определение цели – очень важный момент экономико-математического моделирования. Выражение экономического процесса в виде систем уравнений или неравенств осуществляется ради достижения какого-то экономического эффекта. Целевая функция отражает принятый критерий эффективного решения той или иной задачи. Поэтому от правильности выбора целевой функции зависит результат. Большинство задач в планировании производства относится к классу экстремальных, то есть таких, в которых отыскивается максимум или минимум некоторой целевой функции. Такое решение называется оптимальным. Другой составной частью экономико-математических моделей служат системы уравнений и неравенств, выражающие условия (или ограничения), которые должны соблюдаться при решении задачи. Нередко в моделях указываются формальные требования, такие, как неотрицательность в задачах линейного программирования. Важной характеристикой модели является размерность, то есть количество уравнений и неравенств, неизвестных и т.д. Размерность моделей в значительной мере обусловливает их разрешимость. При построении экономико-математических моделей нужно прежде всего правильно сформулировать цель и ограничительные условия, затем обосновать выбор критерия оптимальности. В теории оптимального программирования (линейного, динамического, стохастического) разработано несколько групп алгоритмов решения задач, формализованных той или иной экономико-математической моделью. Если в экономико-математической модели целевая функция и все ограничительные условия линейны, представлены линейными уравнениями и неравенствами, то для решения задачи применяются методы линейного программирования.

3. Рассмотрим одну из задач оптимального управления – задачу оптимального распределения ресурсов. Имеется m видов ресурсов в количестве b1, b2, …, bm единиц соответственно. Известно, что на основе имеющихся ресурсов можно выпускать n видов продукции. При этом на единицу j-го вида (j = 1, 2, …, n) расходуется aij единиц i-го ресурса (i = 1, 2, …, m). При выпуске каждого вида продукции получаем прибыль cj единиц. Как оценить имеющиеся ресурсы в зависимости от возможности нашего производства?

Производственную программу в данном случае можно охарактеризовать вектором a = (х1, х2, …, хn), где хj – план выпуска j-го вида продукции, причем

, i = 1, 2, …, m,

хj 0, j = 1, 2, …, n.

Пусть f(a) – прибыль, полученная при выполнении производственной программы a, тогда

. (max)

Перед нами задача линейного программирования. А любую такую задачу можно свести к задаче линейного программирования в канонической форме. Ограничения – неравенства

, где j = 1, …, n

преобразуются в ограничения – равенства путем прибавления к левым частям дополнительных (балансовых) ограничений xn+i 0:

, j = 1, …, n

В случае необходимости ограничение-равенство

, j = 1, …, n

можно записать в виде системы неравенств

j = 1, …, n

Вводимые дополнительные переменные имеют определенный экономический смысл, связанный с содержанием задачи. В задачах об использовании ресурсов они показывают величину неиспользованного ресурса. Поскольку число переменных n в этой системе больше числа уравнений m, то одно из возможных решений можно найти, если n-m каких-либо переменных положить равными нулю. Полученную при этом систему m уравнений с n неизвестными можно решить методами алгебры. Условие существования решения – определитель, составленный из коэффициентов при неизвестных, не должен обращаться в нуль. Полученное решение является базисным. Это решение должно быть допустимым, то есть значения всех базисных переменных, должно быть положительным. На решение задачи накладывается добавочное условие того, что линейная целевая функция Z = f(a) должна принимать при найденном решении максимальное значение.

4. Рассмотрим один из методов математического программирования, который представляет собой не аналитическую, а алгоритмическую форму решения задачи – указывает лишь вычислительную процедуру, которая приводит к решению. Существуют разные методы решения задач линейного программирования. Один из наиболее распространенных, когда рассматривается минимальное число базисных решений, – симплекс-метод. Итак, оптимальное решение задачи линейного программирования в канонической форме можно искать только среди ее опорных решений. Для такой задачи всегда можно составить симплекс-таблицу:

x1 x2 … … xn

a11 a12 … … a1n b1

a21 a22 … … a2n b2

. . . .

. . . .

. . . .

am1 am2 … … amn bm

-c1 -c2 … … -cn 0

Существо симплекс-метода. Прежде всего ищем какое-либо допустимое базисное решение. Его можно найти, приняв какие-либо n-m переменных за свободные, приравняв их к нулю и решив получившуюся систему уравнений. Если при этом некоторые из базисных переменных окажутся отрицательными, то нужно выбрать другие переменные, т.е. перейти к новому базису. После того как найдено допустимое базисное решение, проверяется, не достигнут ли максимум целевой функции. Если нет, то ищут новое допустимое базисное решение, но не любое, а такое, которое увеличивает значение целевой функции. Затем процедура повторяется.

5. Рассмотрим построение экономико-математической модели на примере задачи оптимизации распределения ресурсов. Требуется так распределить имеющиеся материалы между изготовителями, чтобы получить максимальную прибыль от реализации всей продукции, произведенной из данных материалов. Построим экономико-математическую модель.

Имеющийся фонд материалов bi (i=1, …, 3) нужно распределить так между изготовителями, чтобы получить максимальную прибыль от реализации всей продукции, произведенной из данных материалов. Нормы aij (i=1, …, 3; j=1, …, 5) расхода на единицу продукции и прибыль ci, получаемая от реализованной единицы продукции, представлены в таблице.

Материалы Продукция Объем

П1 П2 П3 П4 П5

b1 0.7 0.9 1.5 2.3 1.8 50000

b2 1.4 0.3 0.7 2.5 2.0 28000

b3 0.5 2.1 1.8 0.7 2.0 40000

Прибыль ci 5 7 6 9 8

План х х1 х2 х3 х4 х5

Материалы Продукция Объем

П1 П2 П3 П4 П5

b1 0.7 0.9 1.5 2.3 1.8 50000

b2 1.4 0.3 0.7 2.5 2.0 28000

b3 0.5 2.1 1.8 0.7 2.0 40000

Прибыль ci 5 7 6 9 8

План х х1 х2 х3 х4 х5

Решение. Математическая модель задачи

maxZ = 5х1 + 7х2 + 6х3 + 9х4 + 8х5

0.7х1 + 0.9х2 + 1.5х3 + 2.3х4 + 1.8х5 50000

1.4х1 + 0.3х2 + 0.7х3 + 2.5х4 + 2.0х5 28000

0.5х1 + 2.1х2 + 1.8х3 + 0.7х4 + 2.0х5 40000

хj 0 (j=1, …, 5).

Введя дополнительные переменные х6, х7, х8, получим ее каноническую форму

maxZ = 5х1 + 7х2 + 6х3 + 9х4 + 8х5 + 0х6 + 0х7 + 0х8;

0.7х1 + 0.9х2 + 1.5х3 + 2.3х4 + 1.8х5 + х6 50000

1.4х1 + 0.3х2 + 0.7х3 + 2.5х4 + 2.0х5 + х7 28000

0.5х1 + 2.1х2 + 1.8х3 + 0.7х4 + 2.0х5 + х8 40000

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

Разрешающиеся элементы выбираем по описанным выше правилам. Все вычисления производятся согласно правилам симплексных преобразований.

На втором шаге преобразований получаем оптимальный план – все оценки положительны. Итак, х* = (0; 15952; 0; 9286; 0; 14286; 0; 0), т.е. имеющиеся материалы нужно распределить на выпуск продукции П2, в объеме Х2 * = 15952 ед. и П4 в объеме Х4* = 9286 ед. Реализация этой продукции даст 195238 ден. ед.

Дополнительные переменные в оптимальном плане показывают объем неиспользованных материалов: первого материала остается 14286.4 ед., второй и третий материалы используются полностью. Описанный алгоритм решения экономических задач реализован на компьютере. Задачи управления сложны и разнообразны. Без применения компьютера их решение – сложный и трудоемкий процесс. Применение симплекс-метода, особенно реализованного на компьютере, сулит большие выгоды руководителям предприятий. Выигрыш во времени превосходит все ожидания. К тому же отпадают проблемы максимизации прибыли на производстве, оптимального использования ресурсов, минимизации затрат, оптимального плана.

6. Описание работы программы

Входные данные:

n – количество переменных; m – количество ограничений;

A(m, n) – массив коэффициентов системы ограничений;

B(m) – вектор правых частей ограничений;

X(n) – вектор коэффициентов линейной формы;

G(m) – вектор данных об ограничениях:

если ограничение вида , то gi = 1,

если ограничение вида =, то gi = 0,

если ограничение вида , то gi = -1.

Выходные данные:

F – максимальное значение линейной формы;

X(n) – оптимальное значение переменных (оптимальный план).

Остатки всех видов материалов.

Пример:

Найти максимальное значение линейной формы:

F = 5х1 + 7х2 + 6х3 + 9х4 + 8х5

при ограничениях:

0.7х1 + 0.9х2 + 1.5х3 + 2.3х4 + 1.8х5 50000

1.4х1 + 0.3х2 + 0.7х3 + 2.5х4 + 2х5 28000

0.5х1 + 2.1х2 + 1.8х3 + 0.7х4 + 2х5 40000

xj 0 (j=1, …, 5).

Входные данные: n = 5, m = 8,

0.7 0.9 1.5 2.3 1.8 50000 -1

1.4 0.3 0.7 2.5 2 28000 -1 5

0.5 2.1 1.8 0.7 2 40000 -1 7

А(8, 5) = 1 0 0 0 0, В(8) = 0, G(8)= 1, Х(5) = 6

0 1 0 0 0 0 1 9

0 0 1 0 0 0 1 8

0 0 0 1 0 0 1

0 0 0 0 1 0 1

Результат решения задачи:

Максимум линейной формы = 195238

Оптимальные значения переменных: 0, 15952, 0, 9286, 0

Первого материала остается 14286.4

Второго материала остается 0

Третьего материала остается 0.

7. Домашнее задание: Построить экономико-математическую модель задачи распределения выпуска продукции по предприятиям. Внести свои предложения.

Наталья ПУШКАРЕВА, преподаватель информатики 1-го лицея

Усолье-Сибирское,

Иркутская область