Scientific journal
Fundamental research
ISSN 1812-7339
"Перечень" ВАК
ИФ РИНЦ = 1,087

SOLVING LINEAR PROGRAMMING PROBLEMS WITH MATLAB

Borodin G.A. 1 Titov V.A. 1 Maslyakova I.N. 1
1 Plekhanov Russian University of Economics
Настоящая статья посвящена разбору использования среды программирования MatLab при решении задач линейного программирования. Идея статьи возникла при обсуждении преподавания дисциплины «Линейная алгебра». Квалифицированный специалист должен довольно неплохо разбираться не только в методах решения задач, но и уметь проанализировать полученные результаты. Многочисленные математические пакеты и программы позволяют это сделать довольно легко и быстро. Мы предлагаем на примере одного такого пакета MatLab рассмотреть решение задач линейного программирования и с его помощью сделать анализ полученного результата. Были написаны алгоритмы, позволяющие разрешать задачи линейной оптимизации. Данный код позволяет продемонстрировать практическое применение теоретического подхода на современных вычислительных системах, раскрывая смысл каждого показателя. Была разобрана задача-пример, решенная при помощи данного кода.
This article is devoted to analysis of using MatLab environment for solving linear programming problems. The idea of the article appeared due to discussion of teaching «Linear Algebra». A qualified person should understand quite well not only the methods of solving problems, but also beready to analyzeresults. We offer MatLab environment as a tool for solving linear programming problems, and with his help to make the analysis of the result.Algorithms were created for solving linear optimization problems.The code allows demonstration of practical use of theoretical approach on modern computing systems, explaining every index. Example task was solved, using this code.
linear programming
MatLab
programming
the optimal solution
dual problem
1. Dancig D. Linejnoe programmirovanie, ego primenenija i obobshhenija. M., Progress, 1966. 600 p.
2. Masljakova I.N. Primenenie procedury Bajesovskogo ocenivanija v posledovatelnosti testov pri podgotovke specialistov // European researcher. Series A. 2011. no. 5–1. pp. 509–510.
3. Masljakova I.N., Mochalina E.P., Tatarnikov O.V., Ivankova G.N. Model rekurrentnogo ocenivanija urovnja znanij studenta // Menedzhment i biznes-administrirovanie. 2015. no. 3.pp. 71–76.
4. Titov V.A., Dolgopolov A.A. Primenenie simpleks-metoda dlja reshenija zadach dinamicheskogo upravlenija zapasami organizacii. //Sovremennye problemy nauki i obrazovanija. 2014. no. 3. pp. 321; URL: http://www.science-education.ru/ru/article/view id=13074.
5. Titov V.A., Dolgopolov A.A. Linejnye matematicheskie modeli upravlenija zapasami proizvodstvennoj kompanii s uchetom faktora vremeni // Uspehi sovremennogo estestvoznanija. 2015. no. 1–1. pp. 170–171.
6. Titov V.A., Maksimov D.A. Metody ocenki jekonomicheskoj bezopasnosti proizvodstvennoj sfery integrirovannoj proizvodstvennoj struktury // Putevoditel predprinimatelja. 2013. no. 18. pp. 188–205.

Еще в XIX в. общество начало предпринимать первые попытки составить математическую модель экономических проблем для создания точных прогнозов и принятия оптимальных решений. В 1939 г. советский математик Л.В. Канторович опубликовал работу «Математические методы организации и планирования производства», в которой заложил основы линейного программирования. Сам термин был предложен в середине 1940-х гг. американским математиком Джорджем Бернардом Данцигом, автором симплекс-метода [1]. В те времена вычислительная техника пребывала в самом начале своего развития, поэтому симплекс-таблицы, содержащие большое количество переменных, требовали большого количества ресурсов. С развитием IT-технологий, и в особенности появлением персональных компьютеров, исчезла проблема большого количества переменных при решении задач математического программирования. Но появилась другая проблема – проблема использования IT-технологий при подготовке специалистов. Ни для кого не секрет, что во многих российских вузах при подготовке экономистов практически не используются современные математические пакеты и программы для решения тех или иных задач. А это, в свою очередь, снижает конкурентоспособность нашего образования, а экономика нашей страны недополучает высококвалифицированных специалистов [3].

Идея написания данной работы возникла при изучении раздела линейной алгебры «Линейное программирование». Одним из достоинств, но и в то же время недостатков нашего образования является фундаментальность и теоретизированность подачи материала. На наш взгляд, необходим баланс между фундаментальной теорией, решением практических задач и применением современных технологий [2]. В данной работе продемонстрирован такой подход на примере решения задачи линейного программирования и ее постоптимального анализа.

Целью данной работы является создание универсального инструмента на базе среды Matlab для работы с задачами постоптимального анализа, который за счёт своей открытости не только может легко быть перестроен под специализированные задачи, но и стать иллюстрацией методов данного вида анализа экономических задач. Студенты смогут легко проследить, а следовательно, и понять, каким образом при изменении базисных переменных меняется значение целевой функции.

Общая постановка задачи оптимизации

В ходе решения задачи оптимизации необходимо будет выполнить следующие этапы решения:

  • Получить оптимальный план прямой задачи
  • Определить дефицитные ресурсы
  • Получить оптимальный план двойственной задачи
  • Найти интервалы устойчивости ресурсов
  • Предоставить данные пользователю

Постановка и решение прямой задачи линейного программирования

Общей задачей линейного программирования является задача, которая состоит в определении максимального или же минимального значения целевой функции при заданной системе ограничений (рис. 1).

bor01.wmf

bor02.wmf

bor03.wmf

Рис. 1. Общий вид задачи линейного программирования

К данным задачам сводятся многочисленные задачи экономического содержания [5]. Для решения этих задач в среде Matlab используется функция linprog из дополнения OptimizationToolbox. Работа с данной функцией производится путём задания пользователем данных о задаче следующими условиями:

  • A*x<=b (где A – матрица коэффициентов при переменных в ограничениях-неравенствах, b – вектор свободных членов в ограничениях-неравенствах, x – вектор значений переменных);
  • Aeq*x=beq (где Aeq – матрица коэффициентов при переменных в ограничениях-равенствах, beq-вектор свободных членов в ограничениях-равенствах, x – вектор значений переменных);
  • lb<=x<=ub (ограничения на координаты, заданные двумя векторами).

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

[x, fval] = linprog (f, A, b, Aeq, beq, lb, ub)

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

Приведем пример решения задачи:

bor04.wmf

bor05.wmf

Рис. 2. Система ограничений примера

Соответственно, на экране данная задача будет выглядеть так:

borod3.tif

Рис. 3. Запись системы ограничений примера в среде MatLab и нахождение решения

Здесь task = 1 (переменная-маркер поиска максимума/минимума целевой функции).

Значения в x на выходе будут:

x1 = 454,2553

x2 = 58,5106

x3 = 0,0000

x4 = 504,1135

x5 = 9,4326

При выполнении данной функции также можно сразу же получить значения теневых цен ресурсов, заменив запись на:

borod4.tif

Рис. 4. Вызов функции с введением дополнительных аргументов для получения теневых цен

borod5.tif

Рис. 5. Автоматизированный поиск наиболее дефицитного товара

В таком случае (рис. 4) в матрице lambda.ineqlin будут содержаться значения множителей Лагранжа для данной задачи. По своему экономическому смыслу множители Лагранжа одинаковы с теневыми ценами, которые показывают, насколько дефицитным является товар [6].

Код, представленный на рис. 5, показывает, как на основании полученных значений в матрице lambda.ineqlin определить наиболее дефицитный товар и его теневую цену. В теле цикла в переменной max содержится последнее известное максимальное значение, а в maxn – его порядковый номер.

Составление двойственной задачи линейного программирования

прямая

двойственная

(c, x) – min

(b, y) – max

Ax ≥b

AT y ≤ c

x ≥ 0

y ≥ 0

Рис. 6. Взаимосвязь коэффициентов прямой и двойственной задач

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

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

Воспользуемся функцией:

borod7.tif

Рис. 7. Код для решения двойственной задачи на основе заданных коэффициентов прямой задачи

В коде (рис. 7) используется тот же метод linprog, однако меняются аргументы функции в соответствии с теорией. В матрице y будут находиться значения неизвестных двойственной задачи, а в переменной doubleval – значение целевой функции двойственной задачи.

Нахождение интервалов устойчивости ресурсов

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

borod8.tif

Рис. 8. Код для нахождения нижней границы устойчивости ресурсов

Представленный на рис. 8 код для нахождения нижней границы устойчивости ресурсов легко можно использовать для установления верхней границы устойчивости, заменив операцию вычитания на операцию сложения. Смысл данного алгоритма состоит в том, что при изменении значения какого-либо ресурса в пределах его интервала устойчивости, значение целевой функции не изменяется. В переменной approxim задаётся значение приближения, чем оно меньше – тем точнее получаемый результат, однако медленнее вычисления. Таким образом, каждый раз, когда мы изменяем значение какого-то из ресурсов на значение переменной approxim, мы сравниваем его со значением целевой функции при начальных условиях. Как только значения перестают совпадать – обнаруживает себя граница интервала устойчивости, и данную процедуру можно повторять для следующего ресурса [4].

Выводы

Среда Matlab – крайне гибкий инструмент. Её использование в задачах оптимизации позволяет создать не просто приложение, но и наглядное пособие при обучении работе с задачами линейного программирования. На основании составленного «каркаса» возможно изменение используемых алгоритмов, подстройка кода под определенную задачу, а также настройка работы с большими данными, оформленными в форматах текстов файлов или записей БД. Заметим, что это только первый шаг на пути к созданию нового подхода в преподавании математических дисциплин.