- •5. Классификация задач оптимизации
- •7. Понятие, критерий оптимальности и тд
- •10. Графо-аналитич метод решения лин программирования
- •11. Краткая характеристика симплекс метода, его графич интерпретация
- •12. Этапы вычисления симплексным методом
- •17. Алгоритм решения симплекс методом
- •13. Правила составления исходной матрицы и 1-ого плана
- •14. Экономич смысл доп и искусственных переменных при м-методе
- •16. Геометрическая интерпретация этапов решения задачи симплексным м-методом.
- •19. Алгоритм решения задач симплексным методом и искусственным базисом. Расчет коэффициентов целевой строки исходной матрицы
- •18. Правила нахождения коэффициентов новой симплексной таблицы. Оценка оптимальности плана при решении задач на максимум и минимум целевой функции
- •22. Основные теоремы двойственности
- •24 Графо-аналитический метод решения задач целочисленного программирования. Область допустимых решений. Случаи множества равноценных оптимальных планов.
- •27. Целочисленное программирование. Характеристика класса задач, для которых имеет смысл только целочисленное решение. Дополнительное ограничение Гомори.
- •28. Транспортная задача линейного программирования. Метод потенциалов.
- •31. Вырождение плана и его преодоление при решении транспортной методом потенциалов
- •33. Признаки оптимальности плана транспортной задачи при решении методом потенциалов
- •32. Этапы решения транспортной задачи методом потенциалов
- •34. Расчет опорного (базисного) плана транспортной задачи методом «северо-западного угла».
- •35. Расчет опорного (базисного) плана транспортной задачи методом минимальных тарифов.
- •36. Характеристика задачи о назначениях. Методы нахождения оптимального решения.
- •37. Формулы расчёта потенциалов занятых клеток и расчёта оценок свободных
- •39. Характеристика условий и правил игры двух лиц с нулевой суммой.
- •41. Хаар-ка максиминной и минимаксной стратегии игры 2 лиц с нулевой суммой
- •42.Важнейшие свойства максиминных (минимаксных) стратегий игровых матриц с «седловой точкой» (точкой равновесия)
- •46. Биматричные игры. Максиминные и минимаксные стратегии игры игроков
- •44. Приведение матричной антагонистической игры к задаче линейного программирования
- •45. Необходимые и достаточные условия смешанных оптимальных стратегий в матричной игре с нулевой суммой
- •47. Нахождение равновесных стратегий в биматричной игре. Равновесные ситуации.
- •48. Смешанные стратегии в биматричной игре. Свойства смешанных стратегий.
- •49. Многокритериальные задачи. Парето оптимальные стратегии
- •50. Характерные особенности в задачах игры с природой.
27. Целочисленное программирование. Характеристика класса задач, для которых имеет смысл только целочисленное решение. Дополнительное ограничение Гомори.
По смыслу значит части экономич задач, относящихся к задачам лин программирования, компоненты решения должны выражаться в целых числах, т.е. быть целочисленными. К ним относятся, напр, задачи, в которых переменные означают количество единиц неделимой продукции, число судов при распределениях по линиям, число турбин в энергосистеме, число вычислительных машин в управляющем комплексе и многие другие.
Задача лин целочис программирования формулируется следующим образом: найти такое решение (план) Х=(х1, х2, …, хn), при котором линейная функци я
принимает максимальное или минимальное значение при ограничениях , i=1, 2, …, m
, j= 1, 2,…,n. Xj- целые числа.
Для решения задач линейного целочисленного программирования используется ряд методов. Самый простой из них – обычный метод линейного программирования. В случае если компоненты оптимального решения оказываются нецелочисленного, их округляют до ближайших целых чисел. Этот метод применяют тогда, когда отдельная единица совокупности составляет малую часть объема всей совокупности. В противном случае округление может привести к далекому от оптимального целочисленному решению, поэтому используют специально разработанные методы. Методы целочисленной оптимизации можно разделить на 3 основные группы: 1.методы отсечения 2.комбинаторные методы 3.приближенные методы.
Сущность методов отсечения состоит в том, что сначала задача решается без условия целочисленности. Если полученный план целочисленный, задача решена. В противном случае к ограничениям задачи добавляется новое ограничение, обладающее следующими свойствами:
оно должно быть линейным
должно отсекать найденный оптимальный нецелочисленный план
не должно отсекать ни одного целочисленного плана
Дополнительное ограничение, обладающее указанными свойствами, называется правильным отсечением. Далее задача решается с учетом нового ограничения. После этого в случае необходимости добавляется еще одно ограничение итп.
Один из алгоритмов решения задачи линейного целочисленного программирования (2.4.2)-(2.4.4), предложенный Гомори, основан на симплексном методе и использует достаточно простой способ построения правильного отсечения.
Пусть задача линейного программирования (2.4.1)-(2.4.3) имеет конечный оптимум и на последнем шаге ее решения симплексным методом получены следующие уравнения, выражающие основные переменные х1, х2, ..., xj..., xm через неосновные переменные xm+1, xm+2,…, xm+i, …, xn оптимального решения
(2.4.5)
так, что оптимальным решением задачи (2.4.1)-(2.4.3) является Х* = (β1, β2, …, βi, …βm,0,0,…,0), в котором, например βi - нецелая компонента. В этом случае можно доказать, что неравенство
(2.4.6)
сформированное по i-му уравнению системы (2.4.5), обладает всеми свойствами правильного отсечения.
Для решения задачи целочисленного линейного программирования (2.4.1)-(2.4.4.) методом Гомори используется следующий алгоритм:
- симплексным методом решается задача (2.4.1)-(2.4.3) без учета условия целочисленности. Если все компоненты оптимального плана целые, то он является оптимальным и для задачи целочисленного программирования (2.4.1)-(2.4.4). Если первая задача (2.4.1)-(2.4.3) неразрешима (т.е. не имеет конечного оптимума или условия ее противоречивы), то и вторая задача (2.4.1)-(2.4.4) также неразрешима;
- если среди компонент оптимального решения есть нецелые, то выбирается компонента с наибольшей целой частью и по соответствующему уравнению системы (2.4.5) формируется правильное отсечение (2.4.6);
- неравенство (2.4.6) путем введения дополнительной неотрицательной целочисленной переменной преобразовывается в равносильное уравнение
(2.4.7)
и включается в систему ограничений (2.4.2);
- полученную расширенную задачу решают симплексным методом. Если найденный оптимальный план будет целочисленным, то задача целочисленного программирования (2.4.1)-(2.4.4) решена. В противном случае следует вернуться к пункту 2 алгоритма и повторить цикл до тех пор, пока не будет получен оптимальный план .
Если задача разрешима, то оптимальный целочисленный план будет найден после конечного числа шагов (итераций).
Если в процессе решения появится уравнение (выражающее основную переменную через неосновные) с нецелым свободным членом и целыми остальными коэффициентами, то соответствующее уравнение не имеет решения в целых числах. В этом случае и данная задача не имеет целочисленного оптимального решения.