9.2. задачи линейного программирования

9.2. задачи линейного программирования: Справочник по математике для экономистов, В.И. Ермаков, 2009 читать онлайн, скачать pdf, djvu, fb2 скачать на телефон Содержит материал, позволяющий анализировать экономические задачи и осуществлять расчеты. Отражены разделы линейной алгебры, математического программирования, сетевое программирование и планирование, обработка результатов измерений, статистический анализ.

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).

Справочник по математике для экономистов

Справочник по математике для экономистов

Обсуждение Справочник по математике для экономистов

Комментарии, рецензии и отзывы

9.2. задачи линейного программирования: Справочник по математике для экономистов, В.И. Ермаков, 2009 читать онлайн, скачать pdf, djvu, fb2 скачать на телефон Содержит материал, позволяющий анализировать экономические задачи и осуществлять расчеты. Отражены разделы линейной алгебры, математического программирования, сетевое программирование и планирование, обработка результатов измерений, статистический анализ.