А. А. Хакимова

руководитель Бугульминского центра дистанционного обучения Института экономики, управления и права, аспирант Елабужского педагогического института

E-mail:hakimova@bug.ieml.ru

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

Ключевые слова: информационные технологии, задачи линейного программирования, компьютерная математическая система "Mathematica".

Современная экономика широко использует математические методы и самые разнообразные математические модели. Экономический эксперимент в масштабах страны может привести к кризису и социальным потрясениям, а в рамках отдельной фирмы - к убытку или краху. Поэтому моделирование экономических процессов, предварительный анализ возможных последствий тех или иных управленческих решений особенно важны [1].

Вычислительные и графические возможности компьютерной математической системы (КМС) "Mathematica" позволяет исключать рутинные вычисления, которые в изобилии присутствуют в задачах линейного программирования, и сосредоточить внимание обучаемых на творческих вопросах.

Рассмотрим методику использования КМС "Mathematica" для решения задачи линейного программирования.

Задача. Предприятие решило выпускать два вида продукции. Для производства необходим человеческий ресурс и два вида материалов: дерево и ткань. Предприятие ежемесячно имеет в своем распоряжении (по договорам) 440 ед. дерева, 65 ед. материала и 320 ед. человеко-часов. На производство одного вида продукции (на изготовление одного стула) требуется 2 ед. дерева, 0,5 ед. ткани и 2 ед. человеко-часов. На производство второго вида продукции (на изготовление одного стула) требуется 4 ед. дерева, 0,25 ед. ткани и 2,5 ед. человеко-часов. Доход от реализации первого вида продукции составляет 8 тыс. денежных единиц, второго вида продукции - 12 тыс. денежных единиц. Сколько

нужно выпустить продукции того и другого вида, чтобы суммарный доход от их реализации был максимальным? [2]

Решение.

Этап 1. Формализация задачи, или построение математической модели [4].

Определим размерность задачи: имеется 2 переменные (n = 2), удовлетворяющие 3 условиям (m = 3).

Введем необходимые обозначения: x₁ - первый вид продукции; x₂ - второй вид продукции.

Выберем характеристики операций, обозначающих результаты.

Для построения модели производственной программы нам необходимо определить производственный план, приносящий максимальную прибыль, т. е. необходимо найти максимум функции F = 8 x₁ + 12 x₂ при выполнении ограничений.

Ресурсные ограничения отражены в следующей табл. 1.

Таблица 1

Ресурсные ограничения

Сформулируем ограничения задачи:

- целевая функция: F = 8x₁ + 12x₂;

- ограничения ресурсов: 2x₁ + 4x₂ ≤ 440; 0,5x₁ + 0,25x₂ ≤ 65; 2 x₁ + 2,5 x₂ ≤ 320; x₁x₂ ≥ 0.

Сформулируем задачу математического программирования: требуется найти положительные численные значения двух переменных х и х удовлетворяющие следующей системе неравенств:

чтобы максимизировать целевую функцию:

F (x₁, x₂) = 8 x₁ + 12 x₂ → max. (2)

Этап 2. Проведение расчетов.

Решение задачи в КМС "Mathematica" можно выполнить несколькими способами.

Рассмотрим способ, при котором используется команда Maximize [].

Максимум целевой функции вычисляется с помощью функции Maximize []. Первым аргументом указываются целевая функция и накладываемые ограничения.

На рис. 1 представлен фрагмент документа с определением целевой функции и граничных условий.

Воспользуемся функцией LinearProgramming [], чтобы решить задачу.

Функция LinearProgramming [] используется для поиска минимума целевой функции. Чтобы найти максимум целевой функции, которая является линейной комбинацией своих аргументов коэффициентами, следует найти минимум функции, которая строится на линейной комбинации с противоположными коэффициентами [3].

Рис. 1. Целевая функция и ограничения

Для решения задачи достаточно ввести одну команду (см. рис. 2): LinearProgramming [{-8, -12},{{-2, -4},{-0,5, -0,25},{-2, -2,5}}, {-440, -65, -320}].

Рис. 2. Решение задачи линейного программирования с помощью встроенной функции LinearProgramming []

Решим задачу, используя Симплекс-метод.

При решении задачи линейного программирования Симплекс-методом, систему ограничений, записанную в виде неравенств (1) приводят к системе равенств (3) путем введения новых переменных.

Поиск оптимального решения задачи начинается с построения какого-нибудь опорного решения системы (3).

Наиболее просто найти опорное решение, соответствующее нулевым значениям переменных x₁ и x₂:

x₁ = 0, x₂ = 0, x₃ = 440, x₄ = 65, x₅ = 320. (4)

Ему соответствует нулевое значение целевой функции: F₀= 0.

1 итерация. Для исследования решения системы (4) мы должны ненулевые значения переменных x₃, x₄, x₅ принять за базисные, переменные x₁ и x₂ - за свободные и выразить из системы (3) базисные переменные через свободные. Воспользуемся для этого процедурой Solve [], решающей систему уравнений с помощью одной команды (см. рис. 3).

Рис. 3. Решение систем линейных уравнений первой итерации с помощью встроенной процедуры Solve []

Соответствующие формулы имеют вид:

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

Будем, например, увеличивать переменную x₁, оставляя переменную x₂= 0. Максимально допустимое значение x₁ определяется вторым соотношением (5): x₁ = 130.

При этом x₄ обратится в ноль, а переменные x₃ и x₅ останутся положительными.

Полагая в формулах (5) x₁ = 130, x₂ = 0 вычисляя x₃, x₄, x₅ мы перейдем от решения (4) к новому опорному допустимому решению:

x₁ = 130, x₂ = 0, x₃ = 180, x₄ = 0, x₅ = 60. (6).

Вычислим значение целевой функции, соответствующее этому решению, с помощью команды Solve [] (см. рис. 4).

Рис. 4. Вычисление значения целевой функции в первой итерации

F₁ = 1040 > F₀ = 0.

Мы видим, что решение (6) лучше решения (4).

2 итерация. Примем ненулевые переменные x₁, x₃, x₅ за базисные, переменные x₂ и x₄ за свободные и выразим из системы (3) первые через вторые (см. рис. 5):

Рис. 5. Решение систем линейных уравнений во второй итерации

Подставим выражение для x₁ в формулу (2) и запишем целевую функцию как функцию свободных переменных (см. рис. 6):

F (x₁, x₂) = 1040 + 8 x₂ - 16 x₄. (8)

Рис. 6. Преобразование целевой функции во второй итерации

Переменная x₂ входит в (8) со знаком плюс, а переменная x₄ - со знаком минус. Таким образом, для увеличения целевой функции нужно увеличивать переменную x₂ оставляя переменную x₄ равной нулю.

Максимальное допустимое значение переменной x₂ определяется третьим соотношением (7): x₂ = 40.

Полагая во всех формулах (7) x₂ = 40 и x₄ = 0 мы придем к новому опорному решению:

x₁ = 110, x₂ = 40, x₃ = 60, x₄ = 0, x₅ = 0. (9).

Вычислим значение целевой функции во второй итерации (см. рис. 7):

F₂ = 1360 > F₁ = 1040.

Рис. 7. Вычисление значения целевой функции во второй итерации

Вторая итерация позволила увеличить значение целевой функции.

3 итерация. Примем ненулевые переменные x₁, x₂, x₃ за базисные, переменные x₄ и x₅ за свободные и выразим из системы (3) первые через вторые (см. рис. 8):

Рис. 8. Решение систем линейных уравнений в третьей итерации

Подставляя (10) в (2), запишем целевую функцию как функцию свободных переменных x₄ и x₅ (см. рис. 9):

F (x₁, x₂) = 1360+ 16/3 x₄ - 16/3 x₅. (11)

Рис. 9. Преобразование целевой функции в третьей итерации

Переменная x₄ входит в (11) со знаком плюс, а переменная x₅ - со знаком минус. Таким образом, для увеличения целевой функции нужно увеличивать переменную x₄, оставляя переменную x₅ равной нулю.

Максимальное допустимое значение переменной x₄ определяется третьим соотношением (10): x₄ = 15.

Пологая во всех формулах (10) x₅ = 15 и x₅ = 0, мы придем к новому опорному решению:

x₁ = 60, x₂ = 80, x₃ = 0, x₄ = 15, x₅ = 0. (12)

Вычислим значение целевой функции во второй итерации (см. рис. 10):

Рис. 10. Вычисление значения целевой функции в третьей итерации

Третья итерация позволила увеличить значение целевой функции.

4 итерация. Решение (12) показывает, что для выполнения очередного шага за базисные переменные нужно принять x₁, x₂, x₄ а, переменные x₃ и x₅ - за свободные. Выражение базисных переменных и целевой функции через свободные переменные дается следующими формулами (см. рис. 11):

Рис. 11. Решение систем линейных уравнений в четвертой итерации

Подставляя (13) в (2), запишем целевую функцию как функцию свободных переменных x₃ и x₅ (см. рис. 12):

F (x₁, x₂) = 1440 - 4/3 x₄ - 8/3 x₅. (14)

Рис. 12. Преобразование целевой функции в четвертой итерации

Переменная x₃ и x₅ входят в (14) со знаком минус. Таким образом, уменьшение может только уменьшить значение целевой функции. Это означает, что решение (12) является оптимальным и F = 1440 - наибольшее значение в классе допустимых решений.

Этап 3. Анализ результатов.

Полученный ответ удовлетворяет условию задачи и показывает, что при выпуске 60 ед. первого вида продукции и 80 ед. второго вида продукции предприятие получит максимальную прибыль равную 1440 денежных единиц.

Приведенный пример наглядно демонстрирует, что использование КМС "Mathematica" позволяет основное внимание уделить математической формулировке проблемы, выводу необходимых соотношений. Происходит концентрация на самой сущности моделирования, на анализе и интерпретации результата. При этом процесс вычисления выходит на второй план.

Использование КМС "Mathematica" при решении задач линейного программирования позволяет:

1) уделить особое внимание постановке проблемы и ее анализу, построению и исследованию модели а также анализу результатов;

2) освободить учебное время за счет выполнения трудоемких вычислений с помощью КМС "Mathematica";

3) сформировать алгоритмическую культуру студентов.

ЛИТЕРАТУРА

1. Панъков А. В. Решение задач с экономическим содержанием на уроках математики в школе с использованием "Mathematica" // Инфокоммуникационные технологии глобального информационного общества: Сборник трудов 6-й Ежегодной международной научно-практической конференции. Казань, 4 - 5 сентября 2008 г. - Казань: Центр оперативной печати, 2008. - С. 316 - 324.

2. Красильников В. В. Математические методы в экономике. - Наб. Челны, 1996.

3. Васильев А. Н. "Mathematica". Практический курс с примерами решения прикладных задач. - К.: Век+, СПб: КОРОНА-ВЕК, 2008.

4. Баландин К. В., Брызгалов Н. А., Рукосоев А. В. Математическое программирование: Учебник / Под общ. ред. К. В. Баландина. - М: Дашков и К, 2009.

TECHNIQUE OF LINEAR PROGRAMMING PROBLEM-SOLVING WITH USE OF COMPUTER MATHEMATICAL SYSTEM "MATHEMATICA"

A.A. Khakimova

head of the Bugulma Centre of Remote Training of the Institute of Economy, Management and Law, post-graduate student of the Elabuga Pedagogical Institute

The article is devoted to a private technique of training to mathematics applying information technologies on the basis of use of computermathematical system "Mathematica" aimedat solving ojlinearprogramming problems.

Keywords: information technologies, problems of linear programming, computer mathematical system "Mathematica".