Линейное программирование означает расчет значений

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

3.1. Линейное программирование как инструмент математического моделирования экономики

Линейное программирование сформировалось как отдельный раздел прикладной математики в 40 – 50-х гг. ХХ в. благодаря работам советского ученого, лауреата Нобелевской премии Л.В. Канторовича. В 1939 году им была опубликована работа «Математические методы организации и планирования производства», в которой он с использованием математики решил экономические задачи о наилучшей загрузке машин, раскрое материалов с наименьшими расходами, распределении грузов по нескольким видам транспорта и другие, предложив метод разрешающих множителей 8 .

Л.В. Канторович впервые сформулировал такие широко используемые экономико-математические понятия, как оптимальный план, оптимальное распределение ресурсов, объективно обусловленные оценки, указав многочисленные области экономики, где они могут быть применены.

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

Математическое программирование, в которое входит линейное программирование, в настоящее время является одним из направлений исследования операций. В зависимости от вида решаемых задач в нем выделяют такие области, как линейное, нелинейное, дискретное, динамическое программирование и др. Термин «программирование» введен в связи с тем, что неизвестные переменные, которые находятся в процессе решения задачи, обычно определяют программу или план работы некоторого экономического объекта.

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

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

Линейное программирование получило широкое развитие в связи с тем, что было установлено: ряд задач сферы планирования и управления может быть сформулирован в виде задач линейного программирования, для решения которых имеются эффективные методы. По оценкам специалистов примерно 80–85 % всех решаемых на практике задач оптимизации относится к задачам линейного программирования.

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

Определение 1 9 . Линейное программирование (ЛП) – это область математического программирования, являющегося разделом математики и изучающего методы поиска экстремальных (наибольших и наименьших) значений линейной функции конечного числа переменных, на неизвестные которой наложены линейные ограничения.

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

К задачам линейного программирования сводится широкий круг вопросов планирования экономических процессов, где ставится задача поиска наилучшего (оптимального) решения.

Общая задача линейного программирования (ЗЛП) состоит в нахождении экстремального значения (максимума или минимума) линейной функции, называемой целевой 10 :

(3.1)

от n переменных x₁, x₂, …, х_n при наложенных функциональных ограничениях:

(3.2)

и прямых ограничениях (требовании неотрицательности переменных)

, (3.3)

где a_ij, b_i, c_j – заданные постоянные величины.

В системе ограничений (3.2) знаки «меньше или равно», «равно», «больше или равно» могут встречаться одновременно.

ЗЛП в более краткой записи имеет вид:

,

;

.

Вектор `Х = (x₁, x₂, …, х_n) компоненты которого удовлетворяют функциональным и прямым ограничениям задачи называют планом (или допустимым решением) ЗЛП.

Все допустимые решения образуют область определения задачи линейного программирования, или область допустимых решений (ОДР). Допустимое решение, которое доставляет максимум или минимум целевой функции f(`X), называется оптимальным планом задачи и обозначается f(`X * ), где `Х * =(x₁ * , x₂ * , …, х_n * ).

Еще одна форма записи ЗЛП:

,

где f(`X * ) есть максимальное (минимальное) значение f(С, х), взятое по всем решениям, входящим в множество возможных решений Х.

Определение 2 11 . Математическое выражение целевой функции и ее ограничений называются математической моделью экономической задачи.

Для составления математической модели необходимо:

2) составить целевую функцию исходя из цели задачи;

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

Источник

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

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

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

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

(1)

(2) ,

(3) ,, (1.1)

(4) ,.

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

Целевая функция , где выражает критерий оптимизации, отражающий основную цель преследуемую субъектом управления — повышение эффективности использования ресурсов. В производственной сфере показателями эффективности являются обычно выручка или прибыль, что приводит к задачам максимизации. Именно (1.1) представляет собой формулировку задачи максимизации целевой функции.

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

Условия (2) могут выражать ограниченность ресурсов. Например, затраты материалов, труда и времени, необходимые для реализации плана производства, не должны превышать имеющиеся запасы. Ограничения могут также отражать спрос на продукцию. Так в задачах о диете и суточном рационе, условия (2), задают необходимый минимум потребности в ингредиентах (витаминах, кормовых единицах и т.п.).

Переменные называют управляемыми. На эти переменные обычно накладывают условия неотрицательности (4), что соответствует их экономическому смыслу. Допустимо и наличие свободных переменных, на которые не накладываются условия на знак.

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

Любой упорядоченный набор чисел , называется планом задачи или альтернативой. В ЗЛП трактуют как вектор из пространства.

План, удовлетворяющий всем ограничениям ЗЛП, называется допустимым планом.

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

Так как любое ограничение в виде равенства может быть приведено к ограничению в виде неравенства, а любое ограничение в виде неравенства может быть приведено к ограничению в виде равенства путем введения новых фиктивных переменных, исходная ЗЛП может быть записана в одном из специальных видов, стандартном или каноническом.

При записи в стандартном виде, ограничения формулируются в виде неравенств. Стандартный вид задачи максимизации:

, , (1.2)

,.

Обратите внимание на знак неравенств в ограничениях.

Стандартный вид задачи минимизации:

, , (1.3)

,.

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

Канонический вид задачи максимизации:

, , (1.4)

,.

Канонический вид задачи минимизации:

, , (1.5)

,.

ЗЛП можно записывать в матричном виде.

Стандартная задача максимизации в матричном виде:

, ,. (1.6)

Стандартная задача минимизации в матричном виде:

, ,, (1.7)

,

(1.8)

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

, (1.9)

Таким образом, задача линейного программирования (1.2) с использованием обозначения (1.9), заключается в нахождении неотрицательных значений управляемых переменных , максимизирующих заданную целевую функцию.

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

При решении ЗЛП обычно нужно перейти от словесной формулировки к математическому описанию. Для этого нужно:

1. Идентифицировать искомые переменные задачи, то есть указать перечень управляемых переменных , набор которых описывает возможное решение.
2. Задать ограничения, задающие множество допустимых планов, записать их в форме неравенств или уравнений относительно компонент плана.
3. Сформулировать критерий для оценки альтернатив. То есть построить целевую функцию.

Задача А1.41. Для изготовления различных изделий А, В, С предприятие использует три различных вида сырья. Нормы расхода сырья на производство одного изделия каждого вида, цена одного изделия А, В и С, а также общее количество сырья каждого вида, которое может быть использовано предприятием, приведены в табл. 1.1. Изделия А, В и С могут производиться в любых соотношениях (сбыт обеспечен), но производство ограничено выделенным предприятию сырьем каждого вида. Составьте план производства изделий, при котором общая стоимость всей произведенной предприятием продукции является максимальной.

Таблица 1.1
Видысырья	Нормы затрат сырьяна одно изделие			Общее количествосырья
А	В	С
I	18	15	12	360
II	6	4	8	192
III	5	3	3	180
Цена одногоизделия (руб.)	9	10	16

Построим математическую модель задачи. 1). Укажем искомые переменные задачи: —суточный объем производства изделия А (шт.); —суточный объем производства изделия B (шт.); —суточный объем производства изделия C (шт.). 2). Зададим ограничения задачи. а). Ограничения на ресурсы. Расход используемых ресурсов не должен превышать их запас. (ресурс I) (ресурс II) (ресурс III) б). Ограничения на знак. Объемы производства изделий не могут быть отрицательными. , ,. 3). Построим целевую функцию. максимизирует общую стоимость произведенной продукции. Запишем окончательно математическую постановку задачи максимизации в стандартном виде: (1.10) Задача. Требуется составить диету, содержащую, по крайней мере, 20 единиц белков, 30 единиц углеводов, 10 единиц жиров и 40 единиц витаминов. Как дешевле всего составить диету из 5 имеющихся продуктов: хлеба, сои, сушеной рыбы, фруктов молока? В табл. 1.2 указаны цены продуктов за 1 кг (или л) в денежных единицах и содержание в продуктах компонентов диеты в условных единицах.

Таблица 1.2.
Питательныевещества	Продукты
	Хлеб	Соя	Сушеная рыба	Фрукты	Молоко
Белки	2	12	10	1	2
Углеводы	12	0	0	4	3
Жиры	1	8	3	0	4
Витамины	2	2	4	6	2
Цена	24	75	64	36	10

Построим математическую модель задачи. 1). Искомые переменные задачи – количество каждого из 5 ингредиентов, входящих в диету. —количество -го ингредиента (кг или л),. 2). Ограничения задачи. а) Ограничения на ресурсы. Диета должна содержать, не менее, 20 единиц белков: , не менее, 30 единиц углеводов: , не менее, 10 единиц жиров: , не менее, 40 ед. витаминов: . b) Ограничения на знак. Искомые переменные по условию не могут быть отрицательными: ,,,,. 3). Целевая функция минимизирует общую сумму, потраченную на продукты. Запишем математическую постановку задачи минимизации в стандартном виде: (1.11)

Источник