Актуальные проблемы при решении практически значимых задач

Микитась Галина Яковлевна

ст. преподаватель, СГАСУ филиал в г. Белебее

E-mail:

Попова Ирина Александровна

ст. преподаватель, СГАСУ филиал в г. Белебее

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

Сложность решения этой проблемы заключается в том, что для решения этих конкретных дидактических задач часто используются очень разнообразные инструментальные средства [8, с. 167]. Складывается ситуация, когда студенты «за деревьями - леса не видят», то есть основная часть учебного времени тратиться на изучение средств обучения. Каждый программный комплекс имеет свои достоинства и недостатки. Наиболее универсальным программным средством является Microsoft Office, а именно, табличный процессор Excel, методика работы с которым разработана и широко используется [1], [4, с. 51]. Дидактические возможности табличного процессора недостаточно оценены. Он позволяет не только проводить расчеты, работать с таблицей как с базой данных, визуализировать данные, но и решать нелинейные уравнения, системы линейных и нелинейных уравнений, проводить анализ статистических данных, интерполировать и экстраполировать данные, выполнять прогнозирование как точечное, так и интервальное, автоматизировать ведение учета [1], [4], [8].

В данной статье на примере решения транспортной задачи показаны пути решения проблемы. Транспортная задача является одной из наиболее распространенных задач линейного программирования и находит широкое практическое применение. Для её решения применяются различные методы, основанные на решении систем линейных уравнений. Задача рассматривается в курсе высшей математики [2, с. 288], [6, с. 476, 493, 497] изучается в дисциплине «Методы и модели в экономике» [6, с. 123]. Методы решения уравнений и систем уравнений изучаются в курсе «Информатика» [8, с. 188].

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

Постановка транспортной задачи. Некоторый однородный продукт, сосредоточенный у m поставщиков A_i, в количестве a_i (i=1,…,m) единиц, необходимо доставить n потребителям B_j в количестве b_j (j=1,…,n) единиц. Известна стоимость c_ij перевозки единицы груза от i- го поставщика к j- му потребителю. Необходимо составить план перевозок, позволяющий вывести все грузы, полностью удовлетворить потребности и имеющий при этом минимальную стоимость.

Экономико-математическая модель транспортной задачи. Обозначим через x_ij количество единиц груза, запланированных к перевозке от i- го поставщика к j- му потребителю. Стоимость перевозки от i- го поставщика к j- му потребителю составит c_ijx_ij денежных единиц.

Стоимость всего плана (критерий оптимальности) выразится суммой                                                                                   (1)

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

все грузы должны быть перевезены,

                                                                             (2)

все потребности должны быть удовлетворены,

                                                                              (3)

При естественных ограничениях

.                                                                                                     (4)

Математическая модель транспортной задачи в общем виде: найти минимальное значение линейной функции (1) при ограничениях (2), (3) и (4)

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

                                                                                      (5)

Такая транспортная задача называется закрытой моделью.

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

Если суммарные потребности больше суммарных запасов груза то есть , то следует ввести фиктивный пункт отправления i=m+1, условно приписывая ему недостающий запас грузов .

Если суммарные запас груза больше суммарных потребностей, то следует ввести фиктивный пункт потребления j=n+1, условно приписав ему недостающую потребность в грузе .

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

Транспортная задача имеет n+m уравнений с mn неизвестными.

Матрицу , удовлетворяющую условиям (2)—(4), называют планом перевозок транспортной задачи, а x_ij - поставками.

План X^*, при котором целевая функция (1) достигает минимума, называется оптимальным.

Транспортная задача с ограничениями на пропускную способность [6, с. 493]. Пусть требуется при решении транспортной задачи ограничить перевозки от поставщика с номером l к потребителю с номером k. Возможны ограничения двух типов: 1) ≥а; 2) ≤b, где a и b — постоянные величины.

1.  Если ≥a, то необходимо прежде, чем решать задачу, сократить (уменьшить) запасы l-го поставщика и запросы k-го потребителя на величину а (зарезервировать перевозку =а). В полученном оптимальном решении следует увеличить объем перевозки  на величину а.

2.  Если ≤b, то необходимо вместо k-го потребителя с запросами b_k ввести двух других потребителей. Один из них с номером k должен иметь запросы =b, а другой с номером n+1 — запросы b_n+1=b_k-b. Стоимости перевозок для этих потребителей остаются прежними, за исключением стоимости , которая принимается равной сколь угодно большому числу М (М>>1). После получения оптимального решения величины грузов, перевозимых к (n+1)-му потребителю, прибавляются к величинам перевозок k-го потребителя. Так как =М — самая большая стоимость перевозки, то в оптимальном решении клетка с номером (l, n+1) останется пустой (=0) и объем перевозки  не превзойдет b.

Транспортная задача по критерию времени [6, с. 497]. Задача по критерию времени возникает при перевозке срочных грузов. Как и в обычной транспортной задаче, имеется m поставщиков с запасами однородного груза в количестве , ,…,  и n потребителей, которым этот груз должен быть доставлен в объемах ,,…, . Известны , i=1,2,..., m; j=1, 2,…, n — интервалы времени, за которые груз доставляется от каждого i -го поставщика каждому j-му потребителю. Требуется составить такой план перевозок груза, при котором запасы всех поставщиков вывозятся полностью, запросы всех потребителей удовлетворяются полностью и наибольшее время доставки всех грузов является минимальным.

Изменим математическую модель задачи. Обозначим  — объем перевозимого груза от i-го поставщика j - му потребителю. Система ограничений задачи не отличается от системы ограничений обычной транспортной задачи (2)- (4). Пусть X=, i=1,2..., m; j=1, 2,…, n —некоторое опорное решение задачи. Запишем целевую функцию задачи. Обозначим через Т(Х) наибольшее значение элементов матрицы Т = =1,2,…, m; j=1, 2,…, n, соответствующих клеткам таблицы, занятым опорным решением: Математическая модель транспортной задачи по критерию времени имеет вид:

За время Т(Х) план перевозок будет выполнен полностью.

Задача решается в следующем порядке. Находится начальное опорное решение . Определяется значение целевой функции  Все свободные клетки, которым соответствуют значения >Т(Х1), исключаются из рассмотрения (перечеркиваются). Занимать эти клетки нецелесообразно, так как увеличится значение целевой функции. Чтобы уменьшить ее значение, необходимо освободить клетку (), в которой  достигает максимума.

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

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

Структура экономико-математической модели транспортной задачи в формате данных в ТП Excel. Для решения задачи создается форма. В эту форму вводятся исходные данные математической модели транспортной задачи (рисунок 1).

Рисунок 1 Шаблон для решения транспортной задачи

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

Рисунок 2 Модель транспортной задачи в режиме отображения формул

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

Рисунок 3 Модель ТЗ в диалоговом окне «Поиск решения»

С помощью диалогового окна Параметры вводятся параметры для решения оптимизационных задач. Следует установить флажки “неотрицательные значения” и “линейная модель” (рисунок 4)

Рисунок 4 Настройка параметров линейной модели ТЗ

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

Рисунок 5 Диалоговое окно условного форматирования

В диалоговом окне Поиск решения (рисунок 3) после нажатия кнопки Выполнить на экране появится диалоговое окно Результаты поиска решения (рисунок 6). Можно получить отчеты по результатам, по устойчивости и пределам. Можно сохранить сценарий и с помощью Диспетчера сценариев проводить анализ решенной задачи с различными входными параметрами и условиями.

Рисунок 6 Диалоговое окно результатов решения задачи

Результаты – это оптимальный план перевозок (рисунок 7).

Рисунок 7 Результаты оптимального решения ТЗ

Устойчивость (таблица 1) – это чувствительность решения транспортной задачи

Таблица 1

Устойчивость решения транспортной задачи

Из таблицы отчета по устойчивости (таблица 1) видно, на какую величину следует снизить затраты на перевозку в неиспользуемых направлениях, чтобы перевозить грузы в этих направлениях стало выгодно. Например, затраты на перевозку единицы груза из ЖБИ 1 на стройку 2 должны быть сокращены на 11 денежных единиц, чтобы это направление стало привлекательным.

Таблица 2

Устойчивость решения транспортной задачи (продолжение)

Отчет по устойчивости (таблица 2) показывает также, насколько можно снизить общие затраты за счет уменьшения потребностей в пунктах назначения или увеличения запасов в пунктах отправления (изменения в противоположном направлении недопустимы, так как приводят к превышению потребностей над запасами и делают задачу неразрешимой). Например; если на несколько единиц (до 90) увеличить потребности в 2-м пункте назначения, то на каждую единицу общие затраты снизятся на 4 денежных единиц. А если на несколько единиц (до 90) уменьшить запас во 3-м пункте отправления, то на каждую единицу общие затраты увеличатся на 7 денежных единиц.

Анализ решения задачи. Минимальная стоимость перевозок будет при следующем плане поставок:

X11=160 ед. груза следует перевезти от 1-го поставщика 1-му потребителю;

X13=60 ед. груза следует перевезти от 1-го поставщика 3-му потребителю;

X14=110 ед. груза следует перевезти от 1-го поставщика 4-му потребителю;

X25=250 ед. груза следует перевезти от 2-го поставщика 5-му потребителю;

X32=150 ед. груза следует перевезти от 3-го поставщика 2-му потребителю;

X33=100 ед. груза следует перевезти от 3-го поставщика 3-му потребителю;

X41=170 ед. груза следует перевезти от 4-го поставщика 1-му потребителю.

X52=60 ед. груза следует перевезти от 5-го поставщика 2-му потребителю;

X55=90 ед. груза следует перевезти от 5-го поставщика 5-му потребителю.

Общая стоимость перевозок = 9620 (усл. ден. ед.).

Диаграмма, иллюстрирующая оптимальный план перевозок. Для визуализации полученного результата построим диаграмму оптимального плана перевозок груза (рисунок 8).

Рисунок 8 Диаграмма оптимального плана перевозки грузов

Задания для исследовании решения транспортной задачи:

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

·Если какие-либо маршруты перевозок недопустимы, то соответствующие затраты следует положить равными достаточно большим числам, значительно превышающим затраты остальных перевозок, либо положить перевозки от поставщика с номером l к потребителю с номером k равными нулю. Так если дорога между ЖБИ3 и стройкой 2 разрушена, то есть поставка не возможна, то в диалоговом окне Поиск решения (рисунок 3) в систему ограничений вводят условие D5=0.

·Пусть необходимо в рассматриваемой задаче сделать поставку от ЖБИ3 на стройку 2 в размере не менее a=100 единиц, тогда в диалоговом окне Поиск решения добавляется ограничение D5>=100. Выполнить решение задачи с измененной моделью задачи

·Если стройка 2 закончена, то её нужно сделать фиктивным потребителем, положив стоимость перевозки от всех поставщиков c_i2=0. Аналогично, если завод ЖБИ2 встал на ремонт в, тогда он становится фиктивным поставщиком и стоимость перевозки полагаем c_2j=0.

Список литературы:

1.Безручко В.Т. Информатика (курс лекций): учебное пособие. – М.: ИД «ФОРУМ»: ИНФРА – М, 2006. - 432 с.

2.Данко, П.Е., Высшая математика в упражнениях и задачах. В 2 ч. Ч. 1: Учеб. пособие для вузов/ П.Е. Данко, А.Г. Попов, Т.Я. Кожевникова. - М.: Издательский дом «ОНИКС 21 век»: Мир и Образование, 2007. – 304 с.

3.Исследование операций в экономике: Учебн. пособие для вузов/ Н.Ш. Кремер, Б.А. Путко и др.; под ред. проф. Н.Ш. Кремера. - М.: Банки и биржи, ЮНИТИ, 1997. - 407 с.

4.Орлов И.В. Экономико-математическое моделирование: Практическое пособие по решению задач. - М.: Вузовский учебник, 2008. - 144 с.

5.Орлова, И.В. Экономико-математические методы и модели. Выполнение расчетов в среде EXCEL. Практикум / И.В. Орлова // М., Финстатинформ, 2000.

6.Сборник задач по высшей математике для экономистов: Учеб. Пособие/ под ред. В.И. Ермакова. – М.: ИНФРА-М, 2009. - 575 с.

7.Цисарь И.Ф. Лабораторные работы на персональном компьютере: М.: Издательство «Экзамен», 2002. - 224 с.

8.Численные методы: учеб. пособие для студ. высш. учеб. заведений/ М.П. Лапчик, М.И. Рагулина, Е.К. Хеннер; под ред. М.П. Лапчика. – М.: Издательский центр «Академия», 2007. – 384 с.