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

Лекция 3. Линейное программирование

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.4. Определение задачи линейного программирования. (злп)

ЗЛП состоит в максимизации (минимизации) линейной функции при линейных ограничениях.

найти (1.3)

(1.4)

ЗЛП, записанная в виде (1.3) и (1.2), называется общей задачей ЛП, заданной в произвольной форме записи.

Любую ЗЛП можно записать в виде:

найти при условиях , но при этом вводится дополнительное условие:

(1.5)

(1.3) и (1.5) — стандартная форма записи ЗЛП

Любую ЗЛП можно представить в виде:

найти (1.6)

(1.7)

(1.6) и (1.7) — представляют собой каноническую форму записи ЗЛП.

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

1. ; (1.8)
2. ; (1.9)
3. если , то; (1.10)
4. ; (1.11)

~ — означает, что эту переменную дополнительно вводят.

1. (1.12)

Преобразования 3-5 приводят к увеличению размера задачи. Пример 1.2: В стандартной форме: В канонической форме:

1.2. Графоаналитический метод для решения задачи линейного программирования (злп).

Пример 1.3: Найти план производства товаров, при котором будет мах прибыль. Таблица 1.1

Типы ресурсов	Нормы затрат ресурсов		Запасы ресурсов
	а	б
1	2	4	9
2	3	1	6
Прибыль от 1 изделия	6	2

Решение: Найти max f(x) = 6x₁ + 2x₂B m f(x) ax f(x) = 12 C Рис. 1.1 Отрезок ВС, допустимый в области Х, параллельный линиями уровня целевой функции, является крайней гранью этой области в направлении возрастания функции, следовательно, любая точка на отрезке ВС является оптимальным решением. Пример 1.4: Найтиmax f(x) = x₁ + x₂f(x) Рис. 1.2 Допустимая область не ограничена в направлении возрастания целевой функции, т.е. в допустимой области не существует конечной точки максимума. Пример 1.5 : Найтиmax f(x) = 2x₁ + 3x₂f(x) Рис. 1.3 Ограничения задачи противоречивы, отсюда следует, что допустимых решений нет. Пример 1.6: Найдем наибольшее значение функции в заданной области, т.е. решим задачу линейного программирования (максимизируем линейную функцию при линейных ограничениях). Стандартная форма записи ЗЛП Каноническая форма записи ЗЛП

х2
	(1)
(3)
f (x)	(4)
(2)
х1
с=40
	сmax
с=0

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

1. Допустимая область всегда является выпуклым многоугольником, даже в случае, когда она не ограничена.
2. Оптимальное решение в заданном направлении всегда достигается на крайней границе допустимой области.
3. Если в заданном направлении крайняя граница — вершина, то задача имеет единственное решение, если крайняя граница — ребро, то задача имеет множество решений.

Источник