Интегрированный урок математики и информатики "МЕТОДЫ РЕШЕНИЯ ЗАДАЧ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ"
план-конспект урока по информатике и икт (11 класс) на тему

МУНИЦИПАЛЬНОЕ БЮДЖЕТНОЕ ОБЩЕОБРАЗОВАТЕЛЬНОЕ УЧРЕЖДЕНИЕ «ШКОЛА №15 Г. ФЕОДОСИИ РЕСПУБЛИКИ КРЫМ»

Тема урока:    МЕТОДЫ РЕШЕНИЯ ЗАДАЧ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ

Подготовила:

Сулейманова Л.А.

учитель математики

первой квалификационной категории

Феодосия, 2015.

Конспект урока

Тема урока:    МЕТОДЫ РЕШЕНИЯ ЗАДАЧ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ

Тип урока: комбинированный урок.

Цель урока:  Исследовать основные методы решения задач оптимизации и их применение в процессе работы над проектом.

Задачи урока:

• познакомить учеников с понятием графический метод решения задач оптимизации,  познакомить учеников с понятием симплекс метод решения задач оптимизации
•  сформировать навыки и умения решать задачи оптимизации в MS Excel и использовать их на практике
• научить анализировать и сравнивать, задавать вопросы.

Оборудование:

• компьютеры
• проектор
• компьютерная презентация
• раздаточные листы

Ход урока

Учитель 1: Здравствуйте ребята и уважаемые гости. Сегодня мы проводим бинарный урок математики и информатики в рамках исследовательского проекта «Эффективность планирования производства кирпичного завода г. Феодосия». Этот проект был начат во II семестре.

Учитель 2: Проблема проекта поставлена на курсе по выбору «Информационные технологии в бизнесе».

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

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

На первом этапе был построен план реализации проекта:

1. Постановка задачи
2. Исследование теоретических аспектов
3. Применение математического программирования к задачам оптимизации
4. Апробация методов решения задач линейного программирования
5. Применение методов оптимизации к поставленной задаче эффективности планирования производства кирпичного завода
6. Презентация полученных результатов в виде сложенного бизнес плана

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

Учитель 1: И к этому занятию  мы находимся на этапе апробации методов решения задач линейного программирования. А для работы сегодня нам необходимо вспомнить некоторые теоретические вопросы, изученные на предыдущих этапах.

1. Что изучает математическое программирование?
2. Что изучает линейное программирование?
3. Какую функцию называют целевой?
4. Что понимают под математической моделью?
5. Что такое электронная таблица и каково ее назначение?
6. С какими типами данных работает MS Excel?
7. Каково назначение формул в MS Excel? Что может входить в формулу?
8. В чем суть автоматического пересчета в MS Excel?

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

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

Постановка задачи:

             Для изготовления цемента двух видов используется сырье трех видов. Запасы сырья известны и равны соответственно: 264, 136 и 266 т. Количество сырья каждого вида, необходимое для производства единицы цемента первого вида соответственно равны:  12, 4 и 3. Для цемента второго вида: 3, 5 и 14. Прибыль от реализации цемента первого вида составляет 6 у.е., от цемента второго вида  - 4 у.е. Составить план, обеспечивающий наибольшую прибыль производству:

Кто справился с работой? Прошу записать математическую модель на доске, а ребятам необходимо записать модель в рабочие листы.
Математическая модель; 

(учащиеся на доске записывают составленную дома модель к задаче)
x1 – производство цемента первого вида;
x2 – производство цемента второго вида;
12x1 + 3x2 ≤ 264
4x1 + 5x2 ≤ 136
3x1 + 14x2 ≤ 266
x1 ≥ 0, x2 ≥ 0
Целевая функция:
6x1 + 4x2 → max

        Над графическим методом решения задачи линейного программирования работала Дживанова  Суваде .

Айше (показывает работу над проектом под таким названием)

Графический способ решения задачи ЛП состоит из трех этапов:

1. Построение пространства допустимых решений, удовлетворяющих всем ограничениям модели.
2. Построение линий уровня целевой функции.
3. Нахождение оптимального решения среди всех точек пространства допустимых решений.

Найдите первый метод – графический. Вы увидите координатную плоскость, где необходимо выполнить графики.

 (Ученики работают в рабочих листах).

Решим задачу графическим методом

Необходимо найти максимальное значение целевой функции:

F = 6X1+4X2 => max,

при системе ограничений:

12x1+3x2≤264 (1)

4x1+5x2≤136 (2)

3x1+14x2≤266 (3)

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

Обозначим границы области многоугольника решений.

Рассмотрим целевую функцию задачи F = 6X1+4X2 => max.
Построим прямую, отвечающую значению функции F = 0: F = 6X1+4X2 = 0. Будем двигать эту прямую параллельным образом. Поскольку нас интересует максимальное решение, поэтому двигаем прямую до последнего касания обозначенной области. На графике эта прямая обозначена пунктирной линией.

                Прямая F(x) = const пересекает область в точке D. Так как точка D получена в результате пересечения прямых 1 и 2, то ее координаты удовлетворяют уравнениям этих прямых: 12x1+3x2≤264 4x1+5x2≤136
                Решив систему уравнений, получим:
x1 = (264-3x2)/12
4(264-3x2)/12+5x2 = 136
x1 = 19, x2 = 12
                 Откуда найдем максимальное значение целевой функции:
F(X) = 6*19 + 4*12 = 162
                 Таким образом, чтобы получить максимальную прибыль необходимо выпускать 19 т. цемента 1-го вида, и 12 т. цемента 2-го вида.

Переходим рассмотрению следующего метода, над которым  работал Акпеисов Руслан.

Акпеисов: (решить задачу симплекс-методом) 

Симплекс-метод – это алгебраический метод решения задач линейного программирования. Авторы этого метода…

                 Решим прямую задачу линейного программирования  симплексным методом, с использованием симплексной таблицы.
                Определим максимальное значение целевой функции F(X) = 6x1+4x2 при следующих условиях-ограничений.
 12x1+3x2≤264
 4x1+5x2≤136
 3x1+14x2≤266

                    Для построения первого опорного плана систему неравенств, приведем к системе уравнений путем введения дополнительных переменных (переход к канонической форме).
 12x1 + 3x2 + 1x3 + 0x4 + 0x5 = 264
 4x1 + 5x2 + 0x3 + 1x4 + 0x5 = 136
 3x1 + 14x2 + 0x3 + 0x4 + 1x5 = 266
                     Матрица коэффициентов A = a(ij) этой системы уравнений имеет вид:

               Базисные переменные это переменные, которые входят только в одно уравнение системы ограничений и притом с единичным коэффициентом.
                Решим систему уравнений относительно базисных переменных:
 x3, x4, x5,
                Полагая, что свободные переменные равны 0, получим первый опорный план:  
 X1 = (0,0,264,136,266)

Переходим к основному алгоритму симплекс-метода.

 Итерация №0.
               Текущий опорный план неоптимален, так как в индексной строке находятся отрицательные коэффициенты.
                В качестве ведущего выберем столбец, соответствующий переменной x1, так как это наибольший коэффициент по модулю.
                Вычислим значения Di по строкам как частное от деления

 и из них выберем наименьшее:

                  Следовательно, 1-ая строка является ведущей.
                   Разрешающий элемент равен 12 и находится на пересечении ведущего столбца и ведущей строки.
                    Формируем следующую часть симплексной таблицы.
                   Вместо переменной x3 в план 1 войдет переменная x1 .
                   Строка, соответствующая переменной x1 в плане 1, получена в результате деления всех элементов строки x3 плана 0 на разрешающий элемент РЭ=12.
                   На месте разрешающего элемента в плане 1 получаем 1.
                   В остальных клетках столбца x1 плана 1 записываем нули.
                   Таким образом, в новом плане 1 заполнена строка x1  и столбец x1.
                   Все остальные элементы нового плана 1, включая элементы индексной строки, определяются по правилу прямоугольника.
                   Для этого выбираем из старого плана четыре числа, которые расположены в вершинах прямоугольника и всегда включают разрешающий элемент РЭ.
                               НЭ = СТЭ - (А*В)/РЭ
                     СТЭ - элемент старого плана, РЭ - разрешающий элемент (12),   А и В - элементы старого плана, образующие прямоугольник с элементами СТЭ и РЭ.

 Итерация №1.
                Текущий опорный план неоптимален, так как в индексной строке находятся отрицательные коэффициенты.
               В качестве ведущего выберем столбец, соответствующий переменной x2, так как это наибольший коэффициент по модулю.
               Вычислим значения Di по строкам как частное от деления

 и из них выберем наименьшее:

                Следовательно, 2-ая строка является ведущей.
               Разрешающий элемент равен 4 и находится на пересечении ведущего столбца и ведущей строки.
                Формируем следующую часть симплексной таблицы.
               Вместо переменной x4 в план 2 войдет переменная x2
               Строка, соответствующая переменной x2 в плане 2, получена в результате деления всех элементов строки x4 плана 1 на разрешающий элемент РЭ=4.
                На месте разрешающего элемента в плане 2 получаем 1.
                В остальных клетках столбца x2  плана 2 записываем нули.
               Таким образом, в новом плане 2 заполнены строка x2  и столбец x2 .
                Все остальные элементы нового плана 2, включая элементы индексной строки, определяются по правилу прямоугольника.
                  Конец итераций: индексная строка не содержит отрицательных элементов - найден оптимальный план

 Окончательный вариант симплекс-таблицы:

 Оптимальный план можно записать так:
 x1 = 19
 x2 = 12
 x5 = 41
 F(X) = 6*19 + 4*12 = 162

Абиев: (решение задачи  в MS Excel):

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

Универсальность компьютеров – это способность к целенаправленной переработке различных видов информации. Этим и объясняется стремительный процесс внедрения компьютеров в самые разные сферы деятельности человека в современном обществе.

Сегодня вы убедитесь, как использование компьютеров облегчает вашу работу в ходе решения различных задач.

В MS Excel для решения задачи линейного программирования используется надстройка ПОИСК РЕШЕНИЯ

Сначала надстройку «Поиск решения» необходимо подключить (до первого использования):

В MS Excel 2003:
Сервис /
Надстройки /
Поиск решения /

OK

После этого команда «Поиск решения» включена в меню «Сервис»

В окне «Надстройки» установить флажок и нажать ОК

1. Создадим область переменных.
2. Ячейки В2:В3 будут играть роль переменных

(пока они пусты)

3. Введем формулу вычисления значений целевой функции. Например, в ячейку А5
4. Создадим область ограничений. В ячейках А7:А9 будем вычислять левые части ограничений в системе
5.  В ячейках В7:В9 введем правые части ограничений системы.
6. Создадим область ограничений.
7. Вызовем окно диалога «Поиск решения». При этом удобно, если активной ячейкой является ячейка со значением целевой функции.
8. Устанавливаем целевую ячейку А5 (там где вычисляется значение целевой функции).
9. Указываем направление оптимизации – минимизация (по условию).
10.  В поле, изменяя ячейки, указываем ячейки переменных А2:А3
11.  Укажем ограничения.
12.  Нажимаем кнопку «Добавить» .
13.  Появится окно «Добавление ограничения».
14.  Укажем ограничения.
15.  Неотрицательность переменных В2иВ3.
16.  Нажать кнопку «Добавить».
17.  Остальные ограничения.
18.  Нажать OK.
19. Осталось нажать кнопку «Выполнить».
20.  Результаты.

Итог урока.

Учитель 1:

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

Конечная наша цель в работе над проектом «Получить практическую направленность методов мат. программирования, разработать бизнес-план производства». Для закрепления сегодняшнего этапа реализации проекта решите дома задачу:

Предприятие выпускает два вида продукции: Изделие 1 и Изделие 2. На изготовление единицы Изделия 1 требуется затратить a11 кг сырья первого типа, a21 кг сырья второго типа, a31 кг сырья третьего типа.

На изготовление единицы Изделия 2 требуется затратить a12 кг сырья первого типа, a22 кг сырья второго типа, a32 кг сырья третьего типа.

Производство обеспечено сырьем каждого типа в количестве b1 кг, b2 кг, b3 кг соответственно.

Рыночная цена единицы Изделия 1 составляет c1 тыс. руб., а единицы Изделия 2 - c2 тыс.руб.

Требуется:

1) построить экономико – математическую модель задачи;

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

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

4) составить план производства изделий, обеспечивающий максимальную выручку от их реализации, используя надстройку «Поиск решения» в среде MS EXCEL.

Учитель 2:

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

Спасибо за работу! До свидания!