9.2. задачи линейного программирования
9.2. задачи линейного программирования
Оптимизационная задача (V, /, Q), в которой целевая функция является линейной функцией на V= R", ail множеством решений некоторой системы линейных уравнений и линейных неравенств от п неизвестных, называется задачей линейного программирования. При этом система линейных уравнений и линейных неравенств, определяющая допустимое множество Q, называется системой ограничений задачи линейного программирования.
Задача линейного программирования будет поставлена, если:
л
а) указана линейная целевая функция / = ^ДуХу-;
7=1
б) записана система ограничений
л
Y,ayxj = ьі> ієі>1 £ м = ft2>w}>
7=1 л
< bt, і є МІ,
7=1
xj>0, jeJ, /<=уУ = {1,2,...,и}
221
(часто бывает полезно в системе ограничений особо выделить неравенства вида х}. > 0);
в) определено, к какому типу (максимизации или минимизации) принадлежит данная задача. (Задачу максимизации всегда можно свести к задаче минимизации, поменяв знаки у коэффициентов целевой функции.)
Любую задачу линейного программирования можно записать в следующем виде:
У=1
Y^ai]xj = А> 1 є 7> / е М = {1,2,тп),
/=1
Xj > 0.
п
jsJ, J^N = {l,2,...,n}.
(9.1)
(9.2)
(9.3) (9.4)
В частности, если /= 0, то система (9.2), (9.3) состоит только из линейных неравенств, если же I-М, то только из линейных уравнений.
Матрица^ размера тхп,у которой на месте (/,/") стоит коэффициент при Xj в і-м ограничении системы (9.2), (9.3), т.е.
ГаП «12 аЫЛ
А =
*21
*22
<hn
222
В =
.bmJ
Свойства задач линейного программирования:
Г. Допустимое множество задачи линейного программирования либо пусто, либо является выпуклым подмножеством пространства R".
2°. Если допустимое множество задачи линейного программирования не пусто, а целевая функция ограничена снизу (для задачи минимизации) на этом множестве, то задача линейного программирования имеет оптимальное решение.
3°. Оптимальные решения задачи линейного программирования (если они существуют) всегда находятся на границе допустимого множества и образуют выпуклое подмножество пространства R".
Рассмотрим примеры экономических задач, приводимых к задаче линейного программирования.
Задача о рационе. В хозяйстве имеется и видов кормов, каждый из которых содержит т разновидностей питательных веществ. Известно, что одна единицау'-го вида кормов (J 1, 2, п) содержит atj. единиц г-го питательного вещества (і 1, 2, т) и имеет стоимость е.. Требуется составить такой рацион, который бы удовлетворил всем потребностям Ь. (і 1, 2,т) в питательных веществах и имел наименьшую стоимость.
Обозначим количество у'-го корма в рационе х„ х. > О (j 1,
У=1
У=1
Таким образом, мы получим задачу линейного программирования:
л
223
Простейшая задача планирования производства. Предприятие располагает т видами ресурсов и может выпускать некоторую однородную продукцию я различными технологическими способами. За единицу времени использованияу'-го технологического способа (у = 1, 2, л) расходуется a(j. единиц г'-го ресурса (/ = 1, 2, т) и выпускается Cj единиц продукции. Требуется спланировать работу предприятия так, чтобы оно выпускало наибольшее количество продукции при условии, что ресурса г'-го вида нельзя израсходовать более чем bi единиц (/ = 1, 2,т).
Пусть х}., Xj > О (у = 1, 2,..., я) — время использования предприятием у'-го технологического процесса. Если при этом /— количество ВЫПущеННОЙ ПРОДУКЦИИ, ТО / = ^CjXj.
j=l п
Для выпуска продукции предприятие израсходует ^ciyXj еди-ницг'-горесурса. Значит, 2^ayXj <bt, і = 1,2,...,т.
Итак, мы снова имеем задачу линейного программирования:
л
/ = Х^хДтах),
л
^ayXj^bj, і = 1,2,...,/я,
7=1
Х;>0, у = 1,2,..., я.
Важным примером задачи линейного программирования является транспортная задача (см. п. 9.12).
Обсуждение Справочник по математике для экономистов
Комментарии, рецензии и отзывы