ПРАКТИЧЕСКОЕ ПРИМЕНЕНИЕ МАТЕМАТИЧЕСКИХ МЕТОДОВ В

ЭКОНОМИКЕ

Аннотация:

в

работе

рассматривается

применение

линейного

программирования при решении оптимизационных задач с ограничениями.

Мы использовали симплексный метод для нахождения максимума целевой

функции. Этот метод применяется к реальному примеру. Для решения задач

мы использовали функцию “linprog” в MatLab. Мы показали, как применить

симплексный метод к реальной задаче и решить ее с помощью линейного

программирования.

Наконец,

мы

исследуем

сложность

метода

путем

изменения

компьютерного

времени

в

зависимости

от

количества

управляющих переменных.

Ключевые слова: симплексный метод, линейное программирование,

целевая функция, сложность.

Линейное

программирование

было

разработано

во

время

Второй

мировой

войны,

когда

система,

позволяющая

максимизировать

эффективность ресурсов, имела первостепенное значение. Новые проекты,

связанные с войной, требовали оптимизации ограниченных ресурсов.

"Программирование"

использовалось

в

качестве

военного

термина,

который

относился

к

таким

видам

деятельности,

как

эффективное

планирование графиков или оптимальное развертывание людей [1].

Математическое программирование-это та область математики, которая

имеет дело с методами максимизации или минимизации целевой функции,

подверженной линейным, нелинейным и целочисленным ограничениям на

переменные.

Частный

случай

математического

программирования

-это

линейное

программирование.

Линейное

программирование

связано

с

максимизацией или минимизацией линейной целевой функции со многими

переменными,

подверженными

линейному

равенству

и

ограничениям

неравенства [2]. Линейное программирование можно рассматривать как часть

Великого

революционного

развития.

Он

имеет

возможность

определять

общие цели и находить подробные решения для достижения этих целей. Он

может сталкиваться с практическими ситуациями большой сложности.

Для

формулирования

задач

реального

мира

в

л и н е й н ом

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

решения моделей (алгоритмы) и механизмы выполнения шагов алгоритмов

(компьютеры и программное обеспечение) [3].

Принципы

оптимизации

имеют

важное

значение

в

современном

проектировании и эксплуатации систем в различных областях. Компьютеры,

способные

решать

масштабные

задачи,

в

последнее

время

способствуют

разработке

новой

оптимизации

методы.

Основная

цель

этих

методов-

оптимизировать (максимизировать или минимизировать) некоторую функцию

f. Эти функции называются объективными функциями. В качестве примера

мы

использовали

целевую

функцию

f,

представляющую

доход

от

производства электронных элементов, точнее видеокарт. Мы использовали

методы

максимизации

выручки

компании.

Используя

линейное

программирование, мы можем моделировать большое разнообразие целевых

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

автомобилей,

почасовое

количество

клиентов,

обслуживаемых

в

банке,

пробег на галлон определенного типа автомобиля, производство компьютеров

на

ежемесячной

основе

и

так

далее.

Иногда

мы

можем

захотеть

минимизировать f, если f-это затраты на единицу производства определенных

видеокарт (в отличие от нашего примера, где мы максимизируем доход от

производства), эксплуатационные расходы некоторой электростанции, время,

необходимое для производства нового типа автомобиля, ежедневные потери

тепла

в

системе

отопления,

затраты

на

ИТ-инфраструктуру

в

некоторой

компании и так далее.

В

большинстве

задач

оптимизации

целевая

функция

f

зависит

от

нескольких переменных:

x1, x2,.....хп

Эти переменные называются "управляющими переменными", потому

что мы можем управлять ими, то есть мы можем выбирать их значения.

Например, производство некоторых растений может зависеть от температуры

x1, влажности x2, азота в почве x3. Эффективность определенной системы

кондиционирования

воздуха

может

зависеть

от

давления

воздуха

x1,

температуры

x2,

площади

поперечного

сечения

выходного

отверстия

x3,

влажности

x4

и

так

далее.

Теория

оптимизации

разрабатывает

методы

оптимального выбора x1,..., xn, которые максимизируют или минимизируют

целевую функцию f, то есть методы поиска оптимальных значений x1,..., xn.

Во

многих

задачах

выбор

значений

x1,...,

xn

зависит

от

некоторых

ограничений. Это ограничения, которые возникают из-за характера проблемы

и

переменных.

При

определении

оптимальных

значений

управляющих

переменных

необходимо

учитывать

эти

ограничения.

В

нашем

примере

ограничения относятся к числу видеокарт, производимых в течение одного

часа,

если

мы

используем

четыре

разных

машины

в

производстве.

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

могут быть решены с помощью линейного программирования, например:

если x1-стоимость производства, то x1≥0, и есть много других переменных

(время, вес, расстояние, пройденное продавцами), которые могут принимать

только неотрицательные значения. В данном примере ограничения имеют

форму неравенств. Ограничения могут также иметь форму ofequations. В

данной работе рассматривается задача оптимизации с ограничениями.

В линейном программировании целевая функция является линейной

функцией, заданной как:

z=f (x1,...,xn) = a1x1 + a2x2 + ... + anxn

Мы можем переставить структуру, характеризующую задачи линейного

программирования

(возможно,

после

нескольких

манипуляций),

в

следующую форму [1]:

Максимизировать c1x1 + c2x2 + * * * + cnxn = z

Подлежит a11x1 + a12x2 + ** * + a1nxn = b1

...

a21x1 + a22x2 + ** * + a2nxn = b2

am1x1 + am2x2 + * * * + amnxn = bm

x1, x2,. . . , xn ≥ 0

Часть

после

"максимизировать

“представляет

целевую

функцию,

а

часть после” подлежит" представляет ограничения. Это нормальная форма

задачи

линейного

программирования.

Здесь

x1,...,

xn

включают

также

переменные slack. Это вспомогательные переменные, для которых c в f равны

нулю. Мы используем переменные slack для преобразования неравенств в

уравнения. Например, если целевая функция:

f=60x1+40x2

И ограничения:

2x1 + 3x2≤80

5x1+4x2≤80

x1≥0

x2≥0

Нормальной формой задачи линейного программирования будет:

f-60x1-40x2 = 0

2x1+3x2+x3 =80

5x1+4x2+ x4 =8

Как

мы

уже

говорили,

x1

и

x2

называются

управляющими

переменными или переменными решения, а x3 и x4-слабыми переменными

или

вспомогательными

переменными.

Набор

из

x1,

x2

.

.

.

xn,

удовлетворяющий

всем

ограничениям,

называется

выполнимой

точкой

и

множеством всех таких точки называют выполнимым регионом. Решением

линейной программы должна быть точка (x1, x2,. . . , xn) в осуществимом

egion, иначе не все ограничения будут удовлетворены. Алгоритм линейного

программирования

находит

точку

в

допустимой

области,

если

она

существует,

на

которой

целевая

функция

имеет

максимальное

(или

минимальное) значение [4]. Это осуществимое решение.

Выполнимым решением называется оптимальное решение, если для

него

целевая

функция

f

становится

максимальной

по

сравнению

со

значениями

f

при

всех

выполнимых

решениях.

Основное

возможное

решение-это

возможное

решение,

для

которого

по

крайней

мере

n-m

переменных х1, х2 . . . xn равны нулю.

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

графический метод и симплексный метод. Графический метод ограничен

задачами

линейного

программирования,

включающими

две

переменные

решения и ограниченное число ограничений из-за сложности построения

графиков

и

оценки

более

двух

переменных

решения.

Это

ограничение

серьезно ограничивает использование графического метода для реальных

задач. Графический метод прост и удобен поймите, и это очень хороший

инструмент обучения. Симплексный метод намного мощнее графического и

обеспечивает

оптимальное

решение

задач

LP,

содержащих

тысячи

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

решения

для

оптимального

решения.

Кроме

того,

симплексный

метод

предоставляет информацию о слабых переменных (неиспользуемые ресурсы)

и теневых ценах (альтернативные издержки), что полезно при выполнении

анализа чувствительности [5]. Поскольку наша реальная проблема связана с

четырьмя переменными решения, мы использовали симплексный метод. Мы

использовали его вместо графического метода ввиду сложности построения.

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

[1]

Уитмен

Колледж.

Линейное

программирование:

теория

и

приложения.

[2] Dantzig, G. B, Thapa, M. N (1997). Линейное программирование 1:

Введение: Springer-Verlag New York, LLC, книга

[3]

Исследовательская

Группа

Биоинформатики,

Лаборатория

Передовых Вычислений. Линейное программирование.

[4]

Университет

Карнеги-Меллона,

школа

компьютерных

наук.

Линейное программирование.

[5] Университет Брок. Линейное программирование: графические и

симплексные методы.

[6]

Cengage.

Линейное

программирование.

Симплексный

метод:

максимизация.