Решение задач целочисленного программирования онлайн
Dating > Решение задач целочисленного программирования онлайн
Download links: → Решение задач целочисленного программирования онлайн → Решение задач целочисленного программирования онлайн
Система ограничений для левой области Правая область представляет собой точку С. Этот план удовлетворяет условию целочисленности переменных в задаче и может быть принят в качестве оптимального опорного плана для исходной задачи целочисленного линейного программирования. Преобразуем исходную задачу таким образом, чтобы не выполнялось условие целочисленности при решении обычными методами. Гомори доказал, что конечное число подобных шагов приводит к такой задаче линейного программирования, решение которой будет целочисленным и, следовательно, искомым. Построить математическую модель задачи. На каждой итерации решения задачи целочисленного программирования решается одна задача. В противном случае выполнять шаг 3. Строим произвольную линию уровня целевой функции, например, П1. Обнулим все элементы этого столбца, кроме ведущего элемента. Проводим прямую через точки 0; 7 и 10,5; 0.
МИНИСТЕРСТВО ОБРАЗОВАНИЯ РОССИЙСКОЙ ФЕДЕРАЦИИ КУЗБАССКИЙ ГОСУДАРСТВЕННЫЙ ТЕХНИЧЕСКИЙ УНИВЕРСИТЕТ Кафедра вычислительной техники и информационных технологий РЕШЕНИЕ ЗАДАЧ ЛИНЕЙНОГО ЦЕЛОЧИСЛЕННОГО ПРОГРАММИРОВАНИЯ МЕТОДОМ ГОМОРИ Методические указания и задания к практическим занятиям по курсу «Экономико-математическиеметоды» для студентов экономических специальностей Составитель Н. ПОСТАНОВКА ЗАДАЧИ Существует ряд задач оптимального планирования, в которых переменные могут принимать лишь целочисленные значения. Такие задачи связаны с определением количества единиц неделимой продукции, числа станков при загрузке оборудования, численности работников в структурных подразделениях предприятия и т. Достаточно часто возникают задачи с так называемыми булевыми переменными, решениями которых являются суждения типа «да-нет». Если функция и ограничения в таких задачах линейны, то мы говорим о задаче линейного целочисленного программирования. МЕТОД ГОМОРИ Одним из методов решения задач линейного целочисленного программирования является метод Гомори. Сущность метода заключается в построении ограничений, отсекающих нецелочисленные решения задачи линейного программирования, но не отсекающих ни одного целочисленного плана. Решаем задачу симплексным методом без учета условия целочисленности. Если все компоненты оптимального плана целые, то он является оптимальным и для задачи целочисленного программирования. Если обнаруживается неразрешимость задачи, то и неразрешима задача целочисленного программирования. Если среди компонент оптимального решения есть нецелые, то к ограничениям задачи добавляем новое ограничение, обладающее следующими свойствами: - оно должно быть линейным; - должно отсекать найденный оптимальный нецелочисленный план; - не должно отсекать ни одного целочисленного плана. Для построения ограничения выбираем компоненту оптимального плана с наибольшей дробной частью и по соответствующей этой компоненте k-йстроке симплексной таблицы записываем ограничение Гомори. Составленное ограничение добавляем к имеющимся в сим- плексной таблице, тем самым получаем расширенную задачу. Если же величина θ не соответствует дополнительной строке, то необходимо 3 переходить к М-задаче вводить искусственную переменную в ограничение Гомори. Решаем при помощи обычных симплексных преобразований полученную задачу. Если решение этой задачи приводит к целочисленному оптимальному плану, то искомая задача решена. Если мы получили нецелочисленное решение, то снова добавляем одно дополнительное ограничение, и процесс вычислений повторяется. Проделав конечное число итераций, либо получаем оптимальный план задачи целочисленного программирования, либо устанавливаем ее неразрешимость. Если для дробного x j обнаружится целочисленность всех коэффициентов соответствующего уравнения строки , то задача не имеет целочисленного решения. ПРИМЕРЫ РЕШЕНИЯ ЗАДАЧ МЕТОДОМ ГОМОРИ Задача: Для приобретения нового оборудования предприятие выделяет 19 ден. Оборудование должно быть размещено на площади, не превышающей 16 кв. Предприятие может заказать оборудование двух видов: машины типа «А» стоимостью 2 ден. Требуется составить оптимальный план приобретения оборудования, обеспечивающий максимальную общую производительность. Решение: Обозначим через x 1, x 2 количество машин соответственно типа «А» и «В», через L - их общую производительность. После построения дополнительного ограничения имеем новую задачу линейного программирования, в которой 3 ограничения. Строим новое ограничение Гомори. Введем вектор S 1. Учитывая замечание 1, вычеркиваем строку и столбец, соответствующие пере- менной S 1. В полученном плане максимальную дробную часть имеет компонента х 2, поэтому записываем дополнительное ограничение по первой строке. При этом будет достигнута максимальная производительность работы оборудования, равная 36 т продукции за смену. Полученную экономию денежных средств в размере 3 ден. На излишнюю площадь в 2 кв. Геометрическая интерпретация метода Гомори: строим множе- ство планов см. В точке 1 - оптимальный нецелочисленный план.
Last updated
