litceysel.ru
добавить свой файл
1
Серия уроков по теме: "Линейное программирование"



Урок №1 (математика).


Вводный урок.

Учитель формирует задачу:

Найти наибольшее значение величины , если известно, что:


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






Теперь нужно построить прямую . При она касается нашего многоугольника. При увеличении z прямая перемещается вверх и при , "покидает" многоугольник. – таков ответ.

Далее учащимся предлагается самостоятельно решить аналогичную задачу: найти наименьшее значение при условиях

Разница в том, что вместо x стоит x1, а вместо y стоит x2. Уже минут через 5 следует ответ: при .

Вторая половина урока посвящена разбору одной практической задачи.


Требуется составить план выпуска двух видов изделий на четырех участках цеха, чтобы получить максимальную прибыль от сдачи этих изделий. При этом накладываются следующие ограничения: время работы на 1-м участке не превышает 16 часов, на втором – 30 часов, на третьем – 16 часов и на четвертом – 12 часом. В таблице указано время, необходимое на изготовление каждого из этих двух видов изделий на каждом из участков. Нуль означает, что изделие на данном участке не изготавливается.


Изделия

участки

1

2

3

4

1 вид

4

3

0

4

2 вид

2

6

4

0

возможное время работы

16

30

16

12


Цеху начисляется прибыль: 3 рубля при реализации одного изделия первого вида и 4 рубля при реализации одного изделия второго вида.


Решение достаточно простое. Обозначим через x1 число изделий первого вида, а через x2 – число изделий второго вида.

Учащиеся без труда создают математическую модель задачи:

на множестве решений системы:


Требуется найти наибольшее значение линейной формы .

Опять решая эту задачу геометрическим способом:




при .


На дом дается следующая задача:

Садовод сказал Вам, что для повышения урожайности участка необходимо внести в почву не менее 13 кг калийных и не менее 12 кг фосфорных удобрений. Вам поручено купить эти удобрения так, чтобы потратить как можно меньше денег. Вы пришли в магазин и узнали, что самих этих удобрений в чистом виде нет, но есть их смеси №1 и №2. Известно, что килограмм смеси №1 содержит 70% калийных удобрений и 30% фосфорных, а килограмм смеси №2 содержит 40% калийных и 60% фосфорных удобрений. Смесь №1 стоит 10 руб. за 1 кг, смесь №2 – 18 руб. за 1 кг. Сколько надо купить каждой смеси?

Решить эту же задачу, если цена смеси №1 – 12 руб./кг, №2 – 25 руб./кг.


Урок №2 (математика).


Вначале идет обзор домашнего задания. Учащиеся сообщают, что в первом случае ; во втором случае (он нам в дальнейшем пригодиться) .

Далее на уроке рассматривается транспортная задача.

На двух станциях отправления A1 и A2 сосредоточено соответственно a1 и a2 единиц некоторого однородного груза. Этот груз следует доставить в три пункта назначения B1, B2, B3, причем в каждый из них должно быть завезено b1, b2, b3 единиц этого груза. При этом


. Стоимость перевозки единицы груза из пункта Ai (i = 1, 2) в пункт Bj (j = 1, 2, 3) равна Cij. Все данные сведены в таблицу:



пункты

отправления

пункты назначения

запасы груза

B1

B2

B3

A1

C11

C12

C13

a1

A2

C21

C22

C23

a2

потребность в грузе

b1

b2

b3





Требуется составить такой план перевозок, при котором их общая стоимость была бы наименьшей.

Обозначив через xij количество единиц груза, предназначенного к отправке из пункта Ai в пункт Bj, получим следующую систему условий:




Требуется при условии найти минимум формы .

И учащиеся понимают, что геометрически задачу решить нельзя, так как для этого необходимо перейти в шестимерное пространство. Значит, нужно искать алгебраическое решение.

Далее следует иметь в виду, что ситуация с двумя станциями A, тремя станциями B и одним видом груза, практически не реальна. На практике речь идет о сотнях станций и многих видах груза. Значит, требуемый алгоритм должен быть реализован на ЭВМ.

В конце урока целесообразно вернуться к домашней задаче о калийных и фосфорных удобрениях, а точнее, к ее второй части. Там мы получили руб. Но давайте подсчитаем, сколько же мы купили калийных и фосфорных удобрений. Купив 40 кг смеси №1, а там 70% калия и 30% фосфора, мы получили 28 кг калийных и 12 кг фосфорных удобрений. Дедушка заказал купить не менее 13 кг калийных и не менее 12 кг фосфорных удобрений. Вместо 13 кг у нас получилось 28 кг. Что произойдет с почвой, и тем что садовод выращивает, если вместо 13 кг внести 28 кг? Думаем, что ничего не вырастет. Мы подошли к решению задачи с формально-математической точки зрения, а садовод вкладывал в фразу "не менее 13 кг" совсем иной смысл. Вывод, который нужно сделать учащимся:

1) чтобы грамотно составить математическую модель, нужно быть специалистом в данной области (садоводстве, транспортных перевозках и т. д.);

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


Красивый вывод, исходя из простейшей задачи.

На дом учащимся предлагается:

1) догадаться, какие трудности на практике могут возникнуть при реализации транспортной задачи. Как это повлияет на записанные уравнения?

2) на заранее подготовленных листках раздать формулировки задач:

– об использовании сырья;

– об использовании мощностей оборудования;

– о питании

(можно и другие)

Необходимо написать систему условий и линейную форму.


Урок №3 (математика).


На основе домашнего задания учащиеся сами формулируют единую общую модель: при заданной системе условий



Найти минимум и максимум линейной формы (и, возможно, ).

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

Аналогично линейную форму свести к минимуму. Если дана задача найти максимум , то это то же самое, что найти минимум .

Таким образом, формулируется основная задача линейного программирования:

Задана система m линейных уравнений с n неизвестными:


и линейная форма .


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

Сразу рассматривать симплекс-метод в общем виде бесполезно. Вначале на двух примерах нужно показать учащимся идею метода, а затем 2-3 урока решать соответствующие задачи. Покажем лишь один пример.

Пусть система ограничений приведена к виду:



а форма.

Поскольку система трех уравнений (и они явно линейно независимы) с пятью неизвестными, то две переменные будут свободными. Выберите в качестве свободных переменных x4 и x5. Получим систему:





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

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




Мы видим, что, если станет больше 2, то станет меньше нуля, а и будут положительными. Поэтому наиболее выгодно придать значение . Тогда:

.

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


.


Мы видим, что всякое увеличение и приводит лишь к увеличению формы F. Так что найденное нами допустимое решение: , является оптимальным.


Уроки №4 и №5 (математика).


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


Уроки №6 (математика).


Рассматривается симплекс-метод в общем (буквальном0 виде.


Уроки №7 – 9 (10) (информатика).


Вначале на основе главных идей метода строится общая схема алгоритма:

procedure LP opt basic solution (start, new, work, fin);

procedure start, new, work, fin;

begin boolean optimum;

start;

mk1: new (optimum); if optimum then go to mk2;

work; go to mk1;

mk2: fin

end LP obs.

Здесь: start – процедура подготовки данных для вычислений (начальное заполнение массивов, построение начального допустимого базисного решения), new – процедура проверки решения на оптимальность (optimum = "решение оптимально") и выработки вводимой в базис переменной при optimum = false; work – процедура нахождения выводимой из базиса переменной и изменения записи в соответствии с новым базисом; fin – процедура оформления в нужном виде окончательного решения.

И вот, наконец, рождается программа симплекс-метода

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



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

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