Студопедия
Случайная страница | ТОМ-1 | ТОМ-2 | ТОМ-3
АрхитектураБиологияГеографияДругоеИностранные языки
ИнформатикаИсторияКультураЛитератураМатематика
МедицинаМеханикаОбразованиеОхрана трудаПедагогика
ПолитикаПравоПрограммированиеПсихологияРелигия
СоциологияСпортСтроительствоФизикаФилософия
ФинансыХимияЭкологияЭкономикаЭлектроника

Постановка задачи целочисленного линейного программирования

Читайте также:
  1. I. ЦЕЛИ И ЗАДАЧИ ПРЕДДИПЛОМНОЙ ПРАКТИКИ
  2. II. Цели и задачи Конкурса
  3. II. Цели и задачи преддипломной практики.
  4. III. Задачи Коммунистического Интернационала в борьбе за мир, против империалистической войны
  5. III. ЦЕЛИ И ЗАДАЧИ
  6. III. ЦЕЛИ, ЗАДАЧИ И ПРИНЦИПЫ ДЕЯТЕЛЬНОСТИ ПЕРВИЧНОЙ ОРГАНИЗАЦИИ ПРОФСОЮЗА
  7. В отличие от аллегории, символический образ не имеет прямолинейного, рассудочного значения. Он всегда сохраняет живые, эмоциональные ассоциации с широким кругом явлений.

Глава 3. Метод ветвей и границ решения задач целочисленного линейного программирования

 

Постановка задачи целочисленного линейного программирования

 

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

где ; xj - переменные, aij, bi, cj - константы.

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

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

На первый взгляд, тривиальным подходом к решению такой задачи является решение задачи линейного программирования без ограничений целочисленности и последующее округление полученного решения до целых. Однако в общем случае такой подход неверен, так как он может привести к одной из двух ошибок. Во-первых, при округлении возможен выход за пределы ОДП, т.е. полученное решение не будет удовлетворять ограничениям. Во-вторых, даже оставшись в пределах ОДП, можно в результате получить неоптимальное решение.

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

1. Метод ветвей и границ.

2. Методы отсечения.

3. Методы динамического программирования.

Здесь будет рассмотрен метод из первой группы. Однако, предварительно сформулируем ряд определений.

 


Дата добавления: 2015-08-27; просмотров: 74 | Нарушение авторских прав


<== предыдущая страница | следующая страница ==>
При таком использовании команды FOR процесс обработки продолжается, пока не обработаются все файлы (или группы файлов), указанные во множестве.| Элементы теории графов

mybiblioteka.su - 2015-2024 год. (0.005 сек.)