7. Методы решения задач с нецелочисленным планом
Существует ряд задач оптимального планирования, в которых переменные могут принимать лишь целочисленные значения. Такие задачи связаны с определением количества единиц неделимой продукции, числа станков при загрузке оборудования, численности работников в структурных подразделениях предприятия и т.д. Достаточно часто возникают задачи с так называемыми булевыми переменными, решениями которых являются суждения типа «да-нет». Если функция и ограничения в таких задачах линейны, то мы говорим о задаче линейного целочисленного программирования.
Задача линейного целочисленного программирования формулируется следующим образом: найти такое решение (план)
Х = (x1, x2, ..., xn),
Метод Гомори
Сущность метода заключается в построении ограничений, отсекающих нецелочисленные решения задачи линейного программирования, но не отсекающих ни одного целочисленного плана.
1.Решаем задачу симплексным методом без учета условия целочисленности. Если все компоненты оптимального плана целые, то он является оптимальным и для задачи целочисленного программирования. Если обнаруживается неразрешимость задачи, то и неразрешима задача целочисленного программирования.
2.Если среди компонент оптимального решения есть нецелые, то к ограничениям задачи добавляем новое ограничение, обладающее следующими свойствами:
- оно должно быть линейным;
- должно отсекать найденный оптимальный нецелочисленный план;
- не должно отсекать ни одного целочисленного плана.
Для построения ограничения выбираем компоненту оптимального плана с наибольшей дробной частью и по соответствующей этой компоненте k-й строке симплексной таблицы записываем ограничение Гомори.
4. Решаем при помощи обычных симплексных преобразований полученную задачу. Если решение этой задачи приводит к целочисленному оптимальному плану, то искомая задача решена. Если мы получили нецелочисленное решение, то снова добавляем одно дополнительное ограничение, и процесс вычислений повторяется. Проделав конечное число итераций, либо получаем оптимальный план задачи целочисленного программирования, либо устанавливаем ее неразрешимость.
Замечания:
1.Если дополнительная переменная S* вошла в базис, то после пересчетакакого-либопоследующего плана соответствующие ей строку и столбец можно удалить (тем самым сокращается размерность задачи).
2.Если для дробного xj обнаружится целочисленность всех коэффициентов соответствующего уравнения (строки), то задача не имеет целочисленного решения.
Метод ветвей и границ
Первоначально находим симплексным методом или методом искусственного базиса оптимальный план задачи без учета целочисленности переменных. Если среди компонент этого плана нет дробных чисел, то тем самым найдено искомое решение данной задачи.
Метод ветвей и границ основан на предположении, что новый оптимальный нецелочисленный план дает значение функции, большее, чем всякий последующий план перехода.
Пусть переменная xi в плане дробное число. Тогда в оптимальном план ее значение будет, по крайней мере: либо меньше или равно ближайшему меньшему целому числу Ki*; либо больше или равно ближайшему большему целому числу Ki*.
Определяя эти числа симплексным методом решения двух ЗЛП:
Возможны четыре случая при решении этой пары задач:
1) Одна из задач неразрешима, а другая имеет целочисленный оптимальный план. Тогда этот план и значение целевой функции и дают решение исходной задачи.
2) Одна из задач неразрешима, а другая имеет нецелочисленный оптимальный план. Тогда рассматривается вторая задача и в ее оптимальном плане выбирается одна из компонент, значение которой равно дробному числу и строятся две новые задача, аналогично предыдущим.
3) Обе задачи разрешимы. Одна из задач имеет оптимальный целочисленный план, а в оптимальном плане другой задачи есть дробные числа. Тогда вычисляем значение целевой функции от планов и сравниваем их между собой. Если на целочисленном оптимальном план значение целевой функции больше или равно ее значению в плане, среди компонент которого есть дробные числа, то данный целочисленный план является оптимальным для исходной задачи и дает искомое решение.
4)Обе задачи разрешимы, и среди оптимальных планов обеих задач есть дробные числа. Тогда рассматриваем ту из задач, для которой значение целевой функции является наибольшим. Строятся новые две задачи.
Алгоритм метода ветвей и границ
1. Находится решение задачи линейного программирования без учета целочисленности.
2. Составляется дополнительные ограничения на дробную компоненту плана.
3. Находится решение двух задач с ограничениями на компоненту.
4. Строятся в случае необходимости дополнительные ограничения, согласно возможным четырем случаям. Определяется оптимальный целочисленный план, либо устанавливается неразрешимость задачи.
8. Постановка и экономико-математическая модель задачи о назначениях
9. Задача производственного планирования как задача об оптимальных назначениях
Базовая модель задачи планирования производства.
|
|
10. Математические модели дискретного программирования
11.Классификация прикладных задач целочисленного программирования
См. вопрос №10
12. Геометрическая интерпретация задач целочисленного программирования.
См. вопрос №3
13. Характеристики численных методов решения дискретных задач.
Методы решения системы делятся на две группы:
1) прямые (точные методы);
2) итерационные методы (приближенные).
В точных методах решение х находится за конечное число действий, но из-за погрешности округления и их накопления прямые методы можно назвать точными, только отвлекаясь от погрешностей округления.
К точным методам относятся следующие:
Метод Гаусса
Метод Холецкого (метод квадратных корней)
К итерационным методам относятся:
Метод Якоби (простых итераций)
Метод Зейделя
Метод Ричардсона