Алгоритм. 1. Графическим методом строим ограничения на плоскости 2. Находим точку пересечения целевой функции с вершиной многоугольника, удовлетворяющего. - презентация

1

2 Алгоритм. 1. Графическим методом строим ограничения на плоскости 2. Находим точку пересечения целевой функции с вершиной многоугольника, удовлетворяющего условию оптимальности. 3. Если решение не целочисленное, то внутри многоугольника строим многоугольник max площади с вершинами, имеющими целочисленные координаты. 4.Находим оптимальное решение как точку пересечения целевой функции с конечной вершиной нового многоугольника.

3 Справка Целой частью числа «а» называется наибольшее целое число не превосходящее а. Для решения задачи методом Гомори если найдено нецелочисленное решение вводят в зону дополнительные ограничения, которые: 1) Отсекает уже найденное нецелочисленное решение. 2) Не отсекает все целочисленные решения. Пусть найдено решение:

4 Если все целые то решение найдено, если существуют не целые решения, то для них (для решения у которого дробная часть самая большая). Введем дополнительные ограничения. Пусть это каждая строка в системе т.е. (**) Введем следующее ограничение: (*) Данное ограничение удовлетворяет всем правилам правильного отсечения. 1.Подставим правильное решение, в ограничение – противоречие. Это означает: что если бы дополнительные (*) столбцы в исходной системе ограничений, то полученный ответ был бы отсечён. 2.Покажем что не отсекаются все целочисленные решения. Рассмотрим каждою строку: (Отсечён от левой и правой части дроби) Справка: Если решение целочисленное, то оно удовлетворяет неравенство (*)

5 1. Решаем задачу без ограничения целочисленности. 2. Если решение не целочисленное, то выбираем с наибольшей дробной частью и для него вводим дополнительные ограничения(*). 3. Решаем задачу с дополнительным ограничением. ( Для этого вводим столбец с новой дополнительной переменной и новую строку, соответствующую дополнительному ограничению). Выбор размещающего элемента производится по новой строке. 4. Проверяем новое решение на целочисленность. В случае невыполнения целочисленности возвращаемся к пункту 2.

6 / Построим симплекс таблицу

7 2 5/ /3 5 1/3101/34/3 1/3004/316/3 Мы получили оптимальное но не целочисленное решение

8 Т.к. решение не целочисленное, то составим дополнительные ограничения для строки35/301-1/305 1/3101/304/3 -1/300-1/31-1/3 1/3004/3016/3

9 /310/ / /35 Мы получили целочисленное решение, удовлетворяющее нашим ограничением.