Метод гомори онлайн

Dating > Метод гомори онлайн

Download links: → Метод гомори онлайн → Метод гомори онлайн

Пусть задача линейного программирования 8. Применяя симплекс-метод, получаем решение 4-й задачи:. Проводя конечное число итераций, либо получают оптимальный план задачи целочисленного программирования 78 — 81 , либо устанавливают ее неразрешимость. Решение задачи линейного программирования методом Гомори Введение Задачи, которые мы решали ранее всегда давали целочисленный ответ.

На приобретение оборудования двух видов выделено 6 млн. Исключая из него и подстановкой вместо них соответствующих значений из уравнений системы ограничений 87 , получим отсекающий от многоугольника OABCD треугольник EFC. Неосновные переменные х4, х5. Является ли целевая функция строго вогнутой? Если все элементы оптимального плана целые числа, то решение заканчивается для задачи целочисленного программирования. Так, однако бывает не всегда, и чаще всего доход фирмы при переходе к целочисленности немного падает. Дополнительное ограничение обладающие этими свойствами называются правильным отсечением. Технологический процесс также включает обработку изделий на токарных и фрезерных станках. Так как неизвестные могут принимать только целые значения, то задача 70 — 73 является задачей целочисленного программирования. Если такого столбца нет, то в качестве разрешающих выбираются столбец с наименьшим элементом в выделенной строке и строка по min . Следует обратить внимание на то, что в полученном выражении линейной функции Z отсутствуют неосновные переменные хГ и х6. Задача 1 — 3 называется задачей нелинейного программирования в стандартной форме на максимум.

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

Лекция №12 МЕТОД ГОМОРИ РЕШЕНИЯ ЗАДАЧ ЦЕЛОЧИСЛЕННОГО ПРОГРАММИРОВАНИЯ - Если нецелых базисных переменных несколько, то для составления ограничения выбираем компоненту оптимального плана с наибольшей дробной частью если таких переменных несколько, то выбираем любую.

Обычно в задачах линейного программирования не требуется, чтобы координаты плана были целыми числами. Однако в практике часто приходится сталкиваться с задачами, в которых координаты оптимальных планов должны быть целыми числами, и такие задачи называются задачами целочисленного программирования. При решении задач линейного программирования графическим методом и симплекс-методом нет гарантий, что координаты оптимального плана будут целыми числами. На первой итерации симплекс-методом нужно решить задачу линейного программирования. Если найденные неизвестные удовлетворяют требованию целочисленности, то задача целочисленного программирования решена. Если же среди найденных неизвестных хотя бы одна является дробным числом, то тогда следует составить дополнительное условие как его составлять - об этом чуть ниже и присоединить его к системе ограничений задачи целочисленного программирования. Таким образом, из множества планов удаляется подмножество, не содержащее целочисленных планов. Если оптимальный план дополненной таким образом задачи является целочисленным, то задача целочисленного программирования решена. Процесс решения продолжается то тех пор, пока на какой-либо итерации не будет найден целочисленный оптимальный план или можно убедиться, что задача не имеет решения. Решить методом Гомори следующую задачу целочисленного программирования. Найти максимум целевой функции при системе ограничений Решение. Поскольку у нас есть , сам метод объясняться здесь не будет, а будут приведены лишь симплексные таблицы. Дополнительные неизвестные x 3 и x 4 примем за базисные. Поскольку этот оптимальный план не удовлетворяет условию целочисленности, нам нужно составить дополнительное условие. Дробной частью координаты является число , а дробной частью координаты - число. Первое уравнение на основании таблицы запишется так:. Определив дробные части коэффициентов при неизвестных и свободных членов, получаем следующее дополнительное условие: или, введя добавочную переменную ,. Этот план, как и предыдущий, не удовлетворяет условию целочисленности. Поэтому вновь требуется составить дополнительное условие. В данном случае можно использовать первое или третье уравнение. Получится следующее дополнительное условие:. Координаты x 5 и x 6 можно не учитывать, так как начальные условия задачи содержит лишь четыре неизвестные. Поэтому окончательный оптимальный план запишется так: , а максимум функции цели равен 9. Методом ветвей и границ удобно решать такие задачи целочисленного программирования, в которых число неизвестных невелико либо требования целочисленности относятся не ко всем неизвестным. Суть метода ветвей и границ состоит в том, что для тех неизвестных, к которым относится требование целочисленности, нужно определить границы, в которых могут находиться значения этих неизвестных. Затем решаются соответствующие задачи линейного программирования. На каждой итерации решения задачи целочисленного программирования решается одна задача. Введём понятие: список решаемых задач линейного программирования. Из списка следует выбрать задачу, решаемую на соответствующей итерации. Согласно алгоритму решения задачи целочисленного программирования методом ветвей и границ, на каждой p-й итерации требуется сделать 4 шага. Если в списке решаемых задач нет ни одной задачи, то задача целочисленного программирования решена. Максимальное значение значение функции цели - то, которое было найдено на предыдущей итерации, оптимальный план - целочисленный план, найденный на предыдущей итерации. В противном случае следует выбрать одну из задач, имеющихся в списке. Решается выбранная из списка задача линейного программирования. Если задача не имеет решения или для полученного на этом шаге оптимального плана значение функции цели , то следует принять и выполнить шаг 1. В противном случае выполнять шаг 3. Если найденный оптимальный план является целочисленным, то следует принять, что и выполнить шаг 1. В противном случае выполнить шаг 4. Выбрать любую дробную координату оптимального плана. Определить целую часть координаты, составить две новые задачи линейного программирования и включить их в список решаемых задач. Новые задачи отличаются от задачи, выбранной на шаге 1 только границами допустимых значений выбранной координаты. Принять, что и выполнить шаг 1. Решить методом ветвей и границ следующую задачу целочисленного программирования. Найти максимум целевой функции при системе ограничений Решение. Допустим, что заданы или определены следующие границы оптимальных значений неизвестных:. Так как задача задана в нормальной форме, она имеет целочисленный план и нижнюю границу максимального значения целевой функции. В списке решаемых задач - 1-я задача: Итерация 1. С помощью получено решение 1-й задачи:. Так как найденный план не является целочисленным, следует шаг 4. Так как оптимальный план имеет дробную координату 1,2, то и. Применяя границы значений неизвестных 1-й задачи, получаем новые задачи. Во 2-й задаче нижней границей для является , а в 3-й задаче верхней границей для является. Итак, следует решить 2-ю задачу: и 3-ю задачу: Нижняя граница максимального значения целевой функции. Из списка решаемых задач выбираем 2-ю задачу. Констатируем, что 2-я задача не имеет решения, так как её система ограничений несовместна. Тогда и следует следующая итерация. В списке имеется только одна - 3-я задача. Применяя симплекс-метод, получаем решение 3-й задачи:. Так как это решение не является целочисленным, следует шаг 4. Применяя границы значений неизвестных из 3-й задачи, получаем две новых задачи. Из списка решаемых задач, в котором имеются 4-я и 5-я задачи, выбираем 4-ю задачу. Применяя симплекс-метод, получаем решение 4-й задачи:. Так как полученное решение не является целочисленным, следует шаг 4. Выбираем дробную координату и получаем и. Применяя границы значений переменной , получаем две новые задачи линейного программирования. Из списка выбираем 5-ю задачу. Применяя симплекс-метод, получаем решение 5-й задачи:. Так как найденный план не является целочисленным, следует шаг 4. Выбираем дробную координату и получаем и. Применяя границы значений неизвестной 5-й задачи, получаем две новые задачи. Из списка решаемых задач выбираем 6-ю задачу. Констатируем, что 6-я задача не имеет решения. Поэтому нижняя граница максимального значения функции цели и следует следующая итерация. Из списка решаемых задач выбираем 7-ю задачу. Применяя симплекс-метод, получаем решение 7-й задачи:. Так как полученное решение является целочисленным, то нижняя граница максимального значения функции цели и далее следует итерация 8. Из списка решаемых задач выбираем 8-ю задачу. Применяя симплекс-метод, получаем решение 8-й задачи:. Нижняя граница максимального значения функции цели , далее - следующая итерация. В списке решаемых задач имеется лишь 9-я задача. Применяем симплекс-метод и получаем решение 9-й задачи:. Так как полученное решение является целочисленным, нижняя граница максимального значения функции цели и переходим к следующей итерации. В списке решаемых задач нет ни одной задачи. Таким образом, решение данной задачи целочисленного программирования следующее:.