Урок: Оптимизационное
моделирование в экономике. Транспортные задачи
Контингент: 11 класс, профильный уровень.
Цели и задачи урока:
Тип урока: комбинированный
Обучающие задачи:
·
Обобщить и
систематизировать знания о задачах линейного программирования
·
Отработать навыки
построения математической модели транспортной задачи;
·
Сформировать навыки работы
в надстройке «Поиск решения» (Microsoft Excel).
Развивающие задачи:
·
Развитие логического
мышления, т.е. умения анализировать, обобщать, составлять формальные модели
·
Развитие познавательных
умений: выделять главное, планировать работу, вести поисковую деятельность при
определении функции цели, системы ограничений и граничных условий;
·
Критически оценивать
результаты своего труда, регулировать и контролировать свои действия при работе
на компьютере в надстройке «Поиск решения»
·
Развитие воли и
самостоятельности: развитие инициативы, уверенности в своих силах, умения
преодолевать трудности, развитие умения действовать самостоятельно.
Воспитательные задачи:
·
Воспитание
дисциплинированности и организованности при выполнении работы;
·
Воспитание эстетического
отношения к выполняемой работе;
·
Воспитание мотивов учения,
положительного отношения к полученным знаниям.
Педагогические технологии: технология сотрудничества,
проблемно-поисковый метод, информационно-компьютерные технологии
Оборудование:
·
Компьютерный класс;
·
Мультимедийный проектор;
·
Карточки с заданиями для
работы на компьютере.
Методы обучения:
·
Наглядный
·
Исследовательский
·
Проблемно-поисковый
Материал для актуализации
опорных знаний и умений учащихся:
·
Математическая модель
·
Сбалансированная задача
·
Целевая функция
·
Система ограничений
·
Граничные условия
·
Надстройка «Поиск решения»
Список литературы:
1. Попов А.А Excel:
практическое руководство/ А.Попов – ДЕСС КОМ, 2001. – 301с
2. Угринович Н. Д. Информатика
и ИКТ. Профильный уровень: учебник для 11 класса/ Н. Д. Угринович. –308 с. –
4-е изд. –БИНОМ. Лаборатория знаний, 2012.
3. Решение задач в EXCEL.
Методическое пособие по дисциплине “Информатика” для студентов I курса
инженерного факультета/ Нижегородская гос. с-х. академия. – Н.Новгород, 2012 г.
Ход урока
Организационный
момент, приветствие (1 мин)
Постановка проблемы.
Формулирование условия задачи и предложение решить её сразу. (10 мин)
Анализ проблемной
ситуации и возможные пути ее решения (15 мин)
Выполнение
практической работы на компьютере (15 мин)
Сохранение
выполненной работы в файле (1 мин)
Подведение итогов
урока (2 мин)
Домашнее задание (1
мин)
Транспортная задача
Транспортными задачами
называются задачи определения оптимального плана перевозок груза из данных,
пунктов отправления в заданные пункты потребления.
Простейшая формулировка транспортной
задачи, которая получила название задачи по критерию стоимости, следующая:
В m пунктах отправления
находится соответственно a1,…,aj, …an единиц однородного груза (ресурсы),
который должен быть доставлен n потребителям в количествах, b1,…, bi,…bn единиц
(потребности). Заданы стоимости cji перевозок единицы груза из j-го пункта
отправления i-му пункту потребления (коэффициенты затрат).
Требуется спланировать
перевозки, т. е. указать, сколько единиц груза должно быть отправлено из любого
j-го пункта отправления в любой i-й пункт потребления так, чтобы максимально
удовлетворить потребности и чтобы суммарные затраты на перевозки были
минимальными.
Различают задачи, где
выполняется равенство между суммарными ресурсами и суммарными потребностями:
и задачи с отсутствием баланса
между ресурсами и потребностями:
Математическая модель задач при
первом условии называется закрытой, сбалансированной моделью, а при втором
условии открытой, несбалансированной моделью транспортной задачи. Закрытая модель
служит для транспортной задачи как бы классической моделью. Поэтому мы будем рассмотрим
закрытую модель транспортной задачи.
Исходные данные описанной задачи
удобно располагать в следующей таблице, которую будем называть распределительной.
Пункты отправления
|
Пункты назначения
|
a
|
B1
|
…
|
Bi
|
…
|
Bn
|
A1
|
x11
|
c11
|
…
|
x1i
|
c1i
|
…
|
x1n
|
c1n
|
a1
|
|
|
|
…
|
…
|
…
|
…
|
…
|
…
|
…
|
Aj
|
xj1
|
cj1
|
…
|
xji
|
cji
|
…
|
xjn
|
cjn
|
aj
|
|
|
|
…
|
…
|
…
|
…
|
…
|
…
|
…
|
Am
|
xm1
|
cm1
|
…
|
xmi
|
cmi
|
…
|
xmn
|
cmn
|
am
|
|
|
|
b
|
b1
|
…
|
bi
|
…
|
bn
|
|
Для составления математической
модели задачи введем переменные xji >0 (j= 1, 2, ..., m, i= 1, 2, ...,n),
обозначающие количество единиц груза, перевозимого из j-ro склада i-му
потребителю. В отличие от обозначений, принятых в ранее, здесь удобно
переменные снабжать не одним, а двумя индексами.
Очевидно, что эти переменные
должны удовлетворять следующим ограничительным условиям:
(1)
(2)
Уравнения (1) выражают
требования, чтобы сумма всех грузов, вывозимых
из данного j-го склада,
равнялась запасам груза aj на данном складе; уравнения (2) - чтобы сумма всех
грузов, доставляемых данному i-му потребителю, равнялась потребности bi этого
потребителя.
Суммарные затраты на перевозки
будут равны
Рассмотрим транспортную задачу.
Из трех складов требуется
перевезти груз в два пункта назначения. Требуемый объем поставок в пункты
назначения и стоимости перевозки единицы груза со склада в пункт назначения
указаны в таблице:
Номер склада
|
Стоимость
перевозки единицы груза (ден. ед.)
|
1 пункт
|
2 пункт
|
1 склад
|
17
|
6
|
2 склад
|
12
|
13
|
3 склад
|
9
|
8
|
Объем поставок
|
45
|
79
|
Распределение груза на складах
18, 75, 31 соответственно
Определить оптимальный план
перевозок, при котором затраты на перевозку груза были бы минимальными.
Математическая модель задачи
линейного программирования состоит из трех составляющих частей:
система ограничений (система
равенств или неравенств)
целевая функция
неотрицательность неизвестных
(переменных).
Сумма груза на складах равна 124
единицам(18+75+31). Сумма поставляемого груза в пункты назначения также равна
124 единицам(45+79). Следовательно задача сбалансированная
В задаче шесть неизвестных :
X11, X12, X21, X22, X31, X32.
X11- количество груза,
поставляемого со склада 1 в пункт назначения 1, X12 - количество груза,
поставляемого со склада 1 в пункт назначения 2, X21 - количество груза,
поставляемого со склада 2 в пункт назначения 1 и т.д.
Составляем систему ограничений
из 5 уравнений.
1-ое уравнение определяет
перевозки груза с 1 склада : X11 + X12 = 18
2-ое уравнение определяет
перевозки груза со 2 склада : X21 + X22 = 75
3-е уравнение определяет
перевозки груза с 3 склада : X31 + X32 = 31
4-ое уравнение определяет объем
поставок в 1-ый пункт назначения :
X11 + X21 + X31 = 45
5-ое уравнение определяет объем
поставок во 2-ой пункт назначения :
X12 + X22 + X32 = 79
Целевая функция: 17X11 +6X12 +
12X21 + 13X22 + 9X31 + 8X32 → min
И третья составляющая часть
математической модели: X11, X12, … , X32 ≥ 0.
Решение задачи в Microsoft
Office Excel с помощью надстройки Поиск решения.
На электронный лист ведите
заданную таблицу и рядом подготовьте аналогичную таблицу для ввода уравнений и
вывода решения в соответствии с рис. 1.
Рис. 1
В блоке ячеек B3 : C5 содержится
матрица стоимости перевозок.
В блок ячеек G3 : H5 , будет
выводиться план перевозок (неизвестные): в ячейку G3 – количество единиц груза,
поставляемого с 1-ого склада в 1-ый пункт; в ячейку G4 – количество единиц
груза, поставляемого со 2-ого склада в 1-ый пункт и т.д.
В ячейке I3 , будет содержаться
уравнение, определяющее груз, перевозимый с 1-ого склада (первое уравнение из
системы равенств рис. 2). Копированием этого уравнения вниз в ячейки I4, I5
будут введены 2-ое и 3-е уравнения системы равенств.
В ячейку G3 вводится 4-ое
уравнение, оно определяет груз, поставляемый в 1-ый пункт, а в ячейке H3
копированием вводится 5-ое уравнение системы.
Рис. 2
После ввода уравнений таблица
будет соответствовать рис. 3.
Рис. 3
В целевую ячейку I6 ввести
уравнение цели в соответствии с рис. 4.
Рис. 4
Сервис → Поиск решения (для Microsoft Office Excel
2003) или Данные → Поиск решения (для Microsoft Office Excel 2007,2010). Если надстройка Поиск решения не
установлена в Excel 2007 то выполнить: Файл →Параметры Excel →Надстройки → Надстройки Excel →Перейти. В открывшемся меню отметьте
Поиск решения (рис 5). ОК → Выполнить
Рис.5
После ввода всех данных
диалоговое окно надстройки Поиск решения будет соответствовать рис. 6.
Рис. 6
Нажмите кнопку Параметры и в
этом диалоговом окне отметьте ٧ Линейная модель, ٧ Неотрицательные решения и по желанию по
желанию ٧ Показывать
результаты итераций. ОК → Выполнить.
Решение соответствует рис. 7.
Рис. 7
Количество груза, перевозимого
со склада в пункт назначения, находится на пересечении соответствующей номеру
склада строки и столбца, соответствующему номеру пункта назначения.
Анализируем полученный
результат.
Оставьте свой комментарий
Авторизуйтесь, чтобы задавать вопросы.