Методика проведения факультативного курса "Линейное программирование с учащимися старших классов"

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

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

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

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

Тема «Линейное программирование» основывается на одной из центральных тем школьного курса алгебры, а именно «Решение систем линейных уравнений и неравенств». Данная тема опирается также на такие темы школьного курса геометрии, как «Многоугольники» и «Многогранники» (при решении систем линейных уравнений или неравенств графическим методом).

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

Изучая линейное программирование, учащиеся познакомятся с математическим моделированием. Они получат представление о математической модели задачи, научатся ее составлять.

Курс включает в себя следующие темы:

1. История развития теории экстремальных значений величин.
2. Построение моделей задач линейного программирования.
3. Графический метод решения задач линейного программирования.
4. Транспортная задача.
5. Задача составления производственного плана.
6. Задача составления смеси.
7. Линейное программирование в спортивных задачах.
8. Понятие о многомерных пространствах.

Приведу методические разработки занятий по темам №2, 3.

Тема № 2. Построение моделей задач линейного программирования.

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

Математическая модель транспортной задачи.

Задача. На трех складах имеются соответственно 90, 70, 50 тонн муки, которую надо перевезти в 4 магазина, соответственно в количестве 80, 60, 40, 30 тонн. Необходимо составить оптимальный план перевозки, если стоимость перевозки одной тонны в магазины с 1-го склада равна соответственно 2, 1, 3, 2 руб., со 2-го склада – 2, 3, 3, 1 руб., с 3-го склада – 3, 3, 2, 1 руб.

Представим эту задачу в виде таблицы:

Через Xij обозначено количество муки в тоннах, перевозимое с i-ого склада в j-ый магазин.
Естественно считать, что значения переменных неотрицательны. Переменные Xij, , где i = 1, 2, 3, j = 1,2, 3, 4, удовлетворяют следующей системе уравнений и неравенств:

Эта система называется системой ограничений данной задачи. Обозначив черезF все транспортные расходы, имеем

F = 2 Х₁₁ + Х₁₂+ 3 Х₁₃ + 2 Х₁₄ + 2 Х₂₁+ 3 Х₂₂ + 3Х₂₃ + Х₂₄ + 3 Х₃₁ + 3 Х₃₂ + 2Х₃₃ + X₃₄

Функция F называется целевой функцией. Каждое решение системы будет являться одним из возможных вариантов решения. Каждое такое решение носит название допустимого плана. Задача линейного программирования состоит в отыскании из множества допустимых планов такого плана, который обращал бы в минимум целевую функцию F. Такой допустимый план называют оптимальным. Сформулируем теперь задачу математически: найти оптимальный план, определяемый системой и целевой функцией.

Математическая модель задачи составления производственного плана

Задача. Некоторому заводу требуется составить оптимальный план выпуска двух видов изделий при определенных возможностях четырех видов машин. План выпуска этих изделий надо составить так, чтобы от реализации изготовленной продукции завод получил наибольшую прибыль. Оба вида изделий последовательно обрабатываются этими машинами. В плане должно быть предусмотрено, первая машина ежедневно может обрабатывать эту продукцию в течение 8 часов, вторая – 12 часов, третья – 12 часов, четвертая – 9 часов.
Запишем условие задачи в виде таблицы.

Завод от реализации одного изделия 1-го вида получает 4 руб., а от реализации одного изделия 2-го вида – 6 руб. прибыли.
Построим математическую модель этой задачи. Пусть X₁– число изделий 1-го вида, а X₂ – число изделий 2-го вида. Так как машины каждого вида (1, 2, 3, 4) могут обрабатывать продукцию не более (18, 12, 12, 9) часов соответственно, то получаем следующую систему ограничений:

Общая прибыль может быть выражена как F = 4 X₁ + 6 X₂, где Х₁ и Х₁удовлетворяют условиям задачи.

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

Задача. Требуется составить смесь, содержащую три химических вещества А, В, С. Известно, что составляемая смесь должна содержать вещества А не менее 6-ти единиц, вещества В не менее 8-ми единиц, вещества С не менее 12-ти единиц. Вещества А, В, С содержатся в трех видах продуктов – 1, 2, 3 – в концентрации, указанной в таблице.

Стоимость единицы продуктов 1, 2, 3 различна: единица продукта 1 стоит 2 руб., 2 – 3 руб., 3 – 2,5 руб. Смесь надо составить так, чтобы общая стоимость продуктов была наименьшей.
Построим математическую модель этой задачи.
Число единиц продукта 1, входящего в смесь, обозначим через Х₁, продукта 2 – через Х₂, продукта 3 – через Х₃.
Составляемая смесь должна содержать вещество А. Вещество А содержится во всех трех продуктах. На каждую единицу продукта 1 приходится две части концентрации вещества А. Следовательно, если использовано Х₁ единиц продукта 1, то в смеси будет 2 Х₁ частей вещества А и т.д.
Так как общее количество вещества А в смеси должно быть не меньше 6, то 2 Х₁ + Х₂ + 3 Х₃ > 6.
Смесь должна содержать и вещество В, которое также содержится в трех продуктах. Аналогично получаем неравенство:
Х₁ + 2 Х₂ + 1,5 Х₃ > 8.
Общее количество вещества С смеси должно быть не менее 12:
3 Х₁ + 4 Х₂ + 2 Х₃ > 12.
Стоимость смеси слагается из 2 Х₁ руб., 3 Х₂ руб., 2,5 Х₃ руб. Следовательно, общая стоимость смеси будет равна 2Х₁ + 3 Х₂ + 2,5 Х₃.
Из условия следует, что число единиц продукта всегда неотрицательно.
Таким образом, математическая модель задачи представлена системой линейных неравенств:

на множестве решений которой надо найти наименьшее значение целевой функции: F = 2 Х₁ + 3 Х₂+ 2,5 Х₃.

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

Постройте математическую модель задачи: содержание витаминов А и В в одном килограмме фруктов задано таблицей:

Сколько граммов вишни и сколько граммов абрикосов следует включить в дневной рацион, чтобы в нем оказалось не менее 6 мг витамина А и не менее 75 мг витамина В при минимальных затратах, если 1 кг вишни стоит 0,25 руб., а 1 кг абрикосов – 0,3 руб. ?

Тема № 3. Графический метод решения задач линейного программирования

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

Рассмотрим задачу составления производственного плана. Найдем максимальное значение целевой функции F = 4х₁ + 6х₁ при условиях:

Решение.

1) Найдем множество допустимых планов (Рисунок 1).

Неравенства (1) и (2) показывают, что многоугольник расположен в первом квадранте. Неравенства (5) и (6) ограничивают прямоугольник D₂ O C₁ C₂ . Неравенства (3) и (4) еще более суживают искомую область до многоугольника OD₂P₁P₂C₁, являющегося многоугольником допустимых планов.

2) Среди точек многоугольника OD₂P₁P₂C₁ выберем такую, в которой целевая функция F достигает максимального значения. Для этого по уравнению 4 Х₁ + 6 Х₂ = С строим несколько прямых. С увеличением значения С прямая 4 Х₁ + 6 Х2 = С будет двигаться вверх направо. Последней вершиной, к которой прикоснется прямая при выходе за границу многоугольника, будет вершина Р₂. Определим ее координаты. Точка Р₂ образована пересечением трех прямых: Х₁ + Х₂ = 18, 0,5 Х₁ + Х₂ = 12, 2 Х₁ = 24. Получаем Р₂ (12; 6). Fmax = 4 x 12 + 6 x 6 = 84 руб.

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

Найдем минимальное значение целевой функции F = 20 Х₁ + 20 Х₂ + 10 Х₃ при условиях:

Решение.

Неравенства (1), (2), (3) показывают, что область решений лежит в положительном октанте (Рисунок 2)

Уравнение 4 Х₁ + 3 Х₂ + 2 Х₃ = 33 определяет плоскость ( P₁ P₂ P₃), уравнение 3 Х₁ + 2 Х₂ + Х₃ = 23 определяет плоскость (Q₁ Q₂ Q₃), уравнение Х₁ + Х₂ + 2 Х₃ = 12 определяет плоскость (R₁ R₂ R₃). Эти три плоскости ограничивают снизу множество решений задачи. Система ограничений (1) – (6) определяет выпуклую неограниченную многогранную область X₁ R₁ A C Q₃ X₃ Q₃ B R₂ X₂. Целевая функция достигает своего наименьшего значения в одной из вершин многогранника. Найдем координаты вершин R₁, A, C, Q₃, B, R₂.

Функция F достигает своего наименьшего значения в двух соседних вершинах А и С, а следовательно, и во всех точках отрезка АС.

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

Сформулировать задачу о диете по таблице и решить ее графическим методом:

Литература

1. Беляева Э. С., Монахов В. М. Экстремальные задачи. М., Просвещение, 1977.
2. Волков В.А. Элементы линейного программирования. М., Просвещение, 1975.
3. Гаас С. Путешествие в страну линейного программирования.М., Мир, 1973.
4. Гаас С. Линейное программирование. М., Физматгиз, 1961.
5. Монахов В. М. Векторные пространства и решение задач линейного программирования. Выпуск 3. М., 1968.
6. Фирсов В. В., Шварцбурд С. И. Факультативные занятия в средней школе. М., Просвещение , вып. 1, 1973, вып. 2, 1976, вып. 3, 1978.