Задачи линейного программирования. Алгоритм Флойда (стр. 1 из 3)
Содержание
1 Постановка задач линейного программирования (ЗЛП). Примеры экономических задач, сводящихся к ЗЛП. Допустимые и оптимальные решения
2 Алгоритм Флойда. Постановка задачи
1 Постановка задач линейного программирования (ЗЛП). Примеры экономических задач, сводящихся к ЗЛП. Допустимые и оптимальные решения
В общем виде задача линейного программирования (в дальнейшем ЗЛП) может быть сформулирована как задача нахождения наибольшего значения линейной функции
(1)на некотором множестве DÌRn ,где xÎDудовлетворяют системе ограничений
(2)и, возможно, ограничениям
(3)He умаляя общности, можно считать, что в системе (2) первые т ограничений являются неравенствами, а последующие — l-уравнениями. Очевидно, этого всегда можно добиться за счет простого переупорядочения ограничений. Относительно направления знака неравенства будем предполагать, что левая часть меньше или равна правой. Добиться этого можно, умножив на (-1) обе части тех неравенств, которые имеют противоположный знак. Ограничения (3), вообще говоря, могут быть рассмотрены как частный случай ограничений в форме неравенств, но в силу особой структуры их обычно выделяют отдельно и называют условиями неотрицательности (или тривиальными ограничениями).
Дополнительно следует заметить, что выбор типа искомого экстремума (максимума или минимума) также носит относительный характер. Так, задача поиска максимума функции
эквивалентна задаче поиска минимума функции
Часто условия задачи (1) - (3), содержащей ограничения только типа неравенств, бывает удобно записывать в сокращенной матричной форме
где с и x — векторы из пространства Rn, b — вектор из пространства Rm, a А — матрица размерности m´ п.
Задачу линейного программирования, записанную в форме (1) - (3), называют общей задачей линейного программирования (ОЗЛП).
Если все ограничения в задаче линейного программирования являются уравнениями и на все переменные xjналожены условия неотрицательности, то она называется задачей линейного программирования в канонической форме, или канонической задачей линейного программирования (КЗЛП). В матричной форме КЗЛП можно записать в следующем виде:
Поскольку любая оптимизационная задача однозначно определяется целевой функцией f и областью D, на которой отыскивается оптимум (максимум), будем обозначать эту задачу парой (D, f).
Условимся относительно терминологии, которая используется в дальнейшем и является общепринятой в теории линейного программирования.
Планом ЗЛП называется всякий вектор х из пространства Rn.
Допустимым планом называется такой план ЗЛП, который удовлетворяет ограничениям (1.2)-(1.3), т. е. содержится в области D. Сама область Dназывается при этом областью допустимых планов. Оптимальным планом х* называется такой допустимый план, при котором целевая функция достигает оптимального (в нашем случае — максимального) значения, т. е. план, удовлетворяющий условию
maxf(x) = f(x*).
Величина f* = f(x*) называется оптимальным значением целевой функции.
Решением задачи называется пара (х*, f*), состоящая из оптимального плана и оптимального значения целевой функции, а процесс решения заключается в отыскании множества всех решений ЗЛП.
Примеры экономических задач, сводящихся к ЗЛП.
Несмотря на многообразие задач математического программирования, при их решении можно выделить некоторую общую последовательность этапов, через которые проходит любое операционное исследование. Как правило, это:
1.Постановка задачи.
2.Построение содержательной (вербальной) модели рассматриваемого объекта (процесса). На данном этапе происходит формализация цели управления объектом, выделение возможных управляющих воздействий, влияющих на достижение сформулированной цели, а также описание системы ограничений на управляющие воздействия.
3.Построение математической модели, т. е. перевод сконструированной вербальной модели в ту форму, в которой для ее изучения может быть использован математический аппарат.
4.Решение задач, сформулированных на базе построенной математической модели.
5.Проверка полученных результатов на их адекватность природе изучаемой системы, включая исследование влияния так называемых внемодельных факторов, и возможная корректировка первоначальной модели.
6.Реализация полученного решения на практике.
Математическое моделирование в исследовании операций является, с одной стороны, очень важным и сложным, а с другой — практически не поддающимся научной формализации процессом. Заметим, что неоднократно предпринимавшиеся попытки выделить общие принципы создания математических моделей приводили либо к декларированию рекомендаций самого общего характера, трудноприложимых для решения конкретных проблем, либо, наоборот, к появлению рецептов, применимых в действительности только к узкому кругу задач. Поэтому более полезным представляется знакомство с техникой математического моделирования на конкретных примерах.
В качестве таких примеров приведем несколько классических экономико-математических моделей и задач, которые могут быть сформулированы на их основе.
Управление портфелем активов. Рассмотрим проблему принятия инвестором решения о вложении имеющегося у него капитала. Набор характеристик потенциальных объектов для инвестирования, имеющих условные имена от А до F, задается следующей таблицей.
| Название | Доходность (в %) | Срок выкупа (год) | Надежность (в баллах) |
| А | 5,5 | 2001 | 5 |
| В | 6,0 | 2005 | 4 |
| С | 8,0 | 2010 | 2 |
| D | 7,5 | 2002 | 3 |
| Е | 5,5 | 2000 | 5 |
| F | 7,0 | 2003 | 4 |
Предположим, что при принятии решения о приобретении активов должны быть соблюдены условия:
a.суммарный объем капитала, который должен быть вложен, составляет $ 100 000;
b.доля средств, вложенная в один объект, не может превышать четверти от всего объема;
c.более половины всех средств должны быть вложены в долгосрочные активы (допустим, на рассматриваемый момент к таковым относятся активы со сроком погашения после 2004 г.);
d.доля активов, имеющих надежность менее чем 4 балла, не может превышать трети от суммарного объема.
Приступим к составлению экономико-математической модели для данной ситуации. Целесообразно начать процесс с определения структуры управляемых переменных. В рассматриваемом примере в качестве таких переменных выступают объемы средств, вложенные в активы той или иной фирмы. Обозначим их как хА, хВ, хС, хD, хE, хF. Тогда суммарная прибыль от размещенных активов, которую получит инвестор, может быть представлена в виде
(1)На следующем этапе моделирования мы должны формально описать перечисленные выше ограничения a-d на структуру портфеля.
a) Ограничение на суммарный объем активов:
xA+ xB+ xС + xD+ xE+ xF£100 000. (2)
b) Ограничение на размер доли каждого актива:
хА£25 000, хВ£25 000, хС£ 25 000,
xd£ 25 000, хе£ 25 000, xf£25 000. (3)
c) Ограничение, связанное с необходимостью вкладывать половину средств в долгосрочные активы:
хВ + хС³ 50 000 (4)
d) Ограничение на долю ненадежных активов:
xC+ xD£ 30 000. (5)
Наконец, система ограничений в соответствии с экономическим смыслом задачи должна быть дополнена условиями неотрицательности для искомых переменных:
хА³ 0, хB³0, хC³ 0, xD³0, хЕ ³0, xF³ 0. (6)
Выражения (1)-(6) образуют математическую модель поведения инвестора. В рамках этой модели может быть поставлена задача поиска таких значений переменных ха, хB, хC, xd, xe, хF, при которых достигается наибольшее значение прибыли (т. е. функции (1)) и одновременно выполняются ограничения на структуру портфеля активов (2)-(6).
Перейдем теперь к рассмотрению более общих моделей и задач.
Простейшая задача производственного планирования. Пусть имеется некоторый экономический объект (предприятие, цех, артель и т. п.), который может производить некоторую продукцию п видов. В процессе производства допустимо использование т видов ресурсов (сырья). Применяемые технологии характеризуются нормами затрат единицы сырья на единицу производимого продукта. Обозначим через ai,jколичество i-го ресурса (iÎ1: m), которое тратится на производство единицы j-го продукта (jÎ1:n). Весь набор технологических затрат в производстве j-го продукта можно представить в виде вектора-столбца
а технологию рассматриваемого предприятия (объекта) в виде прямоугольной матрицы размерности т на п: