![]() Главная страница Случайная страница КАТЕГОРИИ: АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника |
Постановка задачи целочисленного линейного программированияСтр 1 из 2Следующая ⇒
I. Теоретическая часть По содержанию значительной части экономических задач, относящихся к задачам линейного программирования, компоненты решения должны выражаться только целыми числами, т.е. быть целочисленными. К ним относятся, например, задачи, в которых переменные означают количество единиц неделимой продукции: число станков при загрузке оборудования, число судов при распределении их по линиям, составлении расписаний полета воздушных судов, определения числа турбин в энергосистеме, числа вычислительных машин в управляющем комплексе и многие другие. Задача линейного целочисленного программирования формулируется следующим образом: вычислить такое решение (план) Х* = (х*1, х*2, …, х*n,), при котором линейная функция
принимает максимальное или минимальное значение при ограничениях
xj - целые числа. (17.4)
Определение 17.1. Целой частью числа fi называют наибольшее целое число, не превосходящее fi. Обозначим: [fi ] – целая часть числа fi; { fi } – дробная часть числа fi.. Дробная часть числа вычисляется следующим образом: { fi } = fi - [fi ]. Примеры.
Следует отметить, что классическая транспортная задача и некоторые другие задачи транспортного типа «автоматически» обеспечивают решение задачи в целых числах (если, конечно, целочисленны параметры условий). В общем случае условие целочисленности (17.4), добавляемое к обычным задачам линейного программирования, существенно усложняет ее решение. Для решения задач линейного целочисленноro программирования используется ряд методов. Самый простой из них обычный метод линейного программирования. В случае если компоненты оптимального решения оказываются нецелочисленными, их округляют до ближайших целых чисел. Этот метод применяют тогда, когда отдельная единица совокупности составляет незначительную часть объема всей совокупности. В противном случае округление может привести далеко не к оптимальному целочисленному решению, поэтому используют специально разработанные методы.
Методы целочисленной оптимизации делят на три группы: а) методы отсечения; б) комбинаторные методы; в) приближенные методы. Остановимся подробнее на методах отсечения.
|