Математика для экономистов - Красс М.С.
ISBN 5-94723-672-9
Скачать (прямая ссылка):
Определение 1. Линейное программирование — это область математического программирования, являющегося разделом математики, в котором изучаются методы исследования и отыскания экстремальных (наибольших и наименьших) значений некоторой линейной функции, на аргументы которой наложены линейные ограничения.
Такая линейная функция называется целевой, а набор количественных соотношений между переменными, выражающих определенные требования экономической задачи в виде уравнений или неравенств, называется системой ограничений. Слово «программирование* введено в связи с тем, что неизвестные переменные, которые находятся в процессе решения задачи, обычно определяют программу.'или план работы некоторого экономического субъекта.
Определение 2. Совокупность соотношений, содержащих целевую функцию н ограничения на ее аргументы, называется математической моделью экономической задачи оптимизации.
13 общем виде математическая модель задачи линейного программирования (ЗЛП) записывается как
L(x) = C1A', + C2X1 + ... + C1Xj + ... + CnXn -> шах (min) (І4.1)
260 Глава 14, Линейное программирование
o,,.y, +O11X2 + ... +fljj-v, + ... + а2яхя = bj,
U11X, + a,jXj + ... + O11Xj у ... 4 виТ. = і»;,
л"; > 0, і = I. щ j - I п. где .V1 — неизвестные; ау, bLl с} — заданные постоянные величины.
Наиболее распространенная интерпретация сформулированной задачи состоит в следующем: имеется п ресурсов при некоторых т ограничениях; нужно определить объемы этих ресурсов jy, при которых целевая функция будет достигать максимума (минимума), т. е. найти оптимальное распределение ограниченных ресурсов. При этом возникают также и ограничения, которые называются естественными:
х>0.
Следует особо отметить, что экстремум целевой функции ищется на допустимом множестве решений, определяемом системой ограничений. При этом все или некоторые уравнения системы ограничений могут быть записаны также в виде неравепств.
Математнческая модель в более краткой записи имеет вид
L (Jr) = ? с,*/ -> (пул) (14.3)
при ограничениях
Xj >0, i = U Щ j=\ П.
Для составления математической модели ЗЛП необходимо выполнить следующие этапы:
¦ обозначить переменные;
• составить целевую функцию в соответствии с целью задачи;
• записать систему ограничений с учетом имеющихся в условии задачи показателей.
14.1. Графический метод 261
Если все ограничения задачи заданы уравнениями, а переменные неотрицательные, то модель такого вида называется канонической. Если хотя бы одно ограничение является неравенством, то модель называется неканонической. Далее мы укажем наиболее распространенные методы решения задач линейного программирования.
14.1. Графический метод
Наиболее простым и наглядным методом решения ЗЛП является графический метод. Он применяется для решения ЗЛГ1 с двумя переменными, заданными в неканонической форме, и многими переменными и канонической форме при условии, что они содержат не более двух свободных переменных.
С геометрической точки зрения в задаче линейного программирования ищется такая угловая точка или набор точек из допустимого множества решений (ОДР), па которой достигается самая верхняя (нижняя) линия уровня, расположенная дальше (ближе) остальных в направлении наискорейшего роста целевой функции.
Для нахождения экстремального значения целевой функции при графическом решении ЗЛП используют вектор grad L на плоскости X)OX7, который обозначим С. Этот вектор показывает направление наискорейшего изменения целевой функции, он равен
--, , 7т OL _ dL _
grad L = C= —- е, +-е.,,
дх: дх.,
где «| и ?, — единичные векторы по осям ОХ, и OAV Координатами вектора С являются коэффициенты целевой функции L(x).
14.1.1. Алгоритм решения задачи ЛП
Алгоритм решения задач графическим методом состоит из следующих действий:
1. Находим область допустимых решений системы ограничении задачи,
2. Строим вектор С.
3. Проводим некоторую линию уровня L0 функции i(.v), которая перпендикулярна С.
4. Линию уровня перемещаем по направлению вектора С для задач на максимум и в направлении, противоположном С, для задач на минимум.
262 Гпааа 14. Линейное программирование
Исходи i.iii продукт
Рагхп.ч исходных пролуктои на I кг мороженого
Запас, кг
Сливочное
Шоколадное
Mилико
0,8
0,5
400
I [ал олн «тел и
0.4
0,8
365
Научение рынка сбыта показало, что суточный спрос на сливочное мороженое превышает спрос на шоколадное пс более чем на МО кг. Кроме того, установлено, что спрос на шоколадное мороженое не превышает 350 K]' в сутки. Отпускная цена 1 кт сливочного мороженого 16 ден. ед., шоколадного — U ден. ед.
Определить количество мороженого каждого вида, которое должна производить фирма, чтобы доход от реализации продукции был максимальным.
5. Перемещение линии уровня (т. е. переход от одной линии уровня к другой) производится до тех пор, пока у нее окажется только одна общая точка с областью допустимых решении. Эта точка определяет единственное решение задачи ЛП и будет точкой экстремума.
