9.16. целочисленные задачи линейного программирования

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

9.16. целочисленные задачи линейного программирования

Целочисленная задача линейного программирования — это оптимизационная задача (V, /, Q), где целевая функция/является линейной функцией на VR", a Q — множеством решений некоторой системы линейных уравнений или линейных неравенств, у которых координаты с заданными номерами — целые числа.

Целочисленная задача линейного программирования отличается от общей задачи линейного программирования только дополнительным требованием о целочисленности некоторых (быть может, и всех) неизвестных. Если в задаче требуется целочисленность всех неизвестных, то ее называют полностью целочисленной.

Задача о загрузке корабля. В морском порту имеются предметы п видов. Предмет у'-го вида имеет массу а. и ценность с. (/' = 1, 2,

и). Требуется загрузить корабль данной грузоподъемности Ъ так, чтобы ценность груза была наибольшей.

Обозначив через х. количество предметов у'-го вида (у = 1, 2,

и), которые необходимо погрузить на корабль, получим целочисленную задачу линейного программирования:

и

f = Xc;*/(max)>

и У'=1

Ху^О, / = 1,2, ...,п, Xj — целое, у = 1,2,и.

Задача о распределении капиталовложений между проектами.

Имеется и проектов Ру,Р.,Рп, причем для каждого проекта Р. известны ожидаемый эффект у. от его реализации и необходимая величина капиталовложений g.. Общий объем капиталовложений не может превышать заданной величины Ъ. Требуется определить, какие проекты необходимо реализовать, чтобы суммарный эффект был наибольшим.

253

Введем неизвестные Xj (7 = 1, 2,и), полагая Ґ1, если проект Pj реализуется; J [О, если проект Pj не реализуется. Получим целочисленную задачу линейного программирования:

л

f = ^yjXj(max),

п

J,gjXj < b,

У=і

0<Xj<l, 7 = 1,2, ...,n,

Xj — целое, 7 = 1,2,п.

В ряде случаев оптимизационную задачу с разрывной целевой функцией удается свести к целочисленной задаче линейного программирования.

Рассмотрим, например, задачу максимизации с целевой функцией

7=1

где

І

0, еслих, = О,

CjXj + fly, еслих,> О, допустимое множество Q которой задано системой ограничений

л

Y*atixj=bi> i = l,2,-,m,

Xj>0, 7=1,2,и.

Введем п новых неизвестных, полагая

У і ГО, если Xj О, 11, ЄСЛИ Xj > 0.

Если допустимое множество Q ограничено, то исходная оптимизационная задача сводится к целочисленной задаче линейного программирования:

л

7=1

254

п

Y*atixj=bi> г = 1,2,...,/и,

х.>0; х.<Му., 0<ц<1, у=1, 2,..., и, уу —целое, 7=1,2,и,

где М— достаточно большое число.

Если допустимое множество целочисленной задачи линейного программирования является конечным множеством, то это комбинаторная оптимизационная задача. Классическим примером комбинаторной оптимизационной задачи наряду с задачами о загрузке корабля и о распределении капиталовложений между проектами является задача о коммивояжере.

Задача о коммивояжере. Имеется п городов Ар А2,Ап и задана матрица С = (су) расстояний между этими городами. Выезжая из исходного города Av коммивояжер должен побывать во всех остальных городах по одному разу и вернуться в Av Определить, в каком порядке следует объезжать города, чтобы суммарное пройденное расстояние было наименьшим.

Если в целочисленной задаче линейного программирования отбросить требование о целочисленности неизвестных, то получим задачу линейного программирования, которая называется ослаблением исходной целочисленной задачи.

Целочисленное оптимальное решение ослабления является оптимальным решением и исходной целочисленной задачи.

В частности, если ослабление окажется транспортной задачей с целочисленным вектором ограничений, то оптимальное решение транспортной задачи (которое при этих условиях всегда может быть выбрано целочисленным) будет оптимальным решением исходной задачи.

В большинстве же случаев ослабление целочисленной задачи имеет только нецелочисленное оптимальное решение, причем если округлить нецелочисленные координаты этого решения, то нельзя получить даже допустимого решения исходной задачи.

С другой стороны, для решения комбинаторной оптимизационной задачи можно попробовать перебрать все допустимые решения этой задачи и выбрать среди них такое, на котором целевая функция принимает наибольшее (наименьшее) значение. Однако

255

существуют задачи, у которых допустимых решений очень много и перебрать их все практически невозможно.

Таким образом, целочисленные задачи линейного программирования образуют специфический класс оптимизационных задач, для решения которых требуются специальные методы.

Известны различные методы решения целочисленных задач: метод отсечений, метод ветвей и границ, метод Беллмана. Эффективность того или иного метода зависит от конкретных условий задачи.

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

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

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

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

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