Методы оптимизации

Теория двойственности

Теория двойственности
Правила построения двойственной задачи можно описать следующим образом:

Теория двойственности
Составить двойственную задачу по отношению к исходной задаче линейного программирования :

Теория двойственности
Построить двойственные задачи к следующим задачам линейного программирования:
1.
2.
3.

Теория двойственности

Основные теоремы о двойственных задачах можно переформулировать следующим образом:
1) Если исходная и двойственная ей задачи имеет допустимые решения, то обе имеют оптимальные решения, причем значения целевых функций для оптимальных решений обоих задач совпадают.
2) Если одна из задач имеет допустимые решения, а другая – нет, то задача, которая имеет допустимые решения, неограниченна.
Третий возможный случай: обе задачи не имеют допустимых значений.
Других вариантов нет.

Теория двойственности
Решать двойственную задачу можно двойственным симплекс-методом. Двойственный симплекс-метод строится по аналогии с прямым симплекс-методом. Различие состоит лишь в том, что свободные члены задачи, решаемой двойственным симплекс-методом, могут быть любыми числами, в то время как в прямом симплекс-методе эти числа должны быть неотрицательными. При этом если все коэффициенты в строке целевой функции неположительны, то базисное решение называется псевдорешением.
Алгоритм двойственного симплекс-метода
1) Пусть дана задача линейного программирования в канонической форме, так что базисное решение является псевдорешением. Тогда, если все свободные члены неотрицательны, псевдорешение является оптимальным.
2) Если в какой-нибудь строке, кроме отрицательного свободного члена нет других отрицательных коэффициентов, то данная задача линейного программирования не имеет допустимых решений.
3) Если базисное решение содержит отрицательные переменные (есть отрицательные свободные члены), то исключению из базиса подлежит одна из этих переменных, а именно та, значение которой максимально по модулю.

Целочисленное программирование
Основной класс задач оптимизации составляют задачи линейного программирования, в которых на значения всех или части переменных наложены требования целочисленности. Если все переменные принимают только целочисленные значения, то модель определяет полностью целочисленную задачу, иначе говорят о частично целочисленной задаче.
Постановка полностью целочисленной задачи линейного программирования
Если найти решение данной задачи симплекс-методом, то оно может оказаться как целочисленным, так и нет. Поэтому в общем случае для определения оптимального плана требуются специальные методы.

Целочисленное программирование
Определение

Целочисленное программирование

Целочисленное программирование
Алгоритм метода Гомори
1. Используя симплекс-метод, находим оптимальное решение задачи линейного программирования без учета требования целочисленности.
2. Если все свободные члены в завершающей симплекс-таблице целые числа, то оптимальное решение является целочисленным, то есть отвечает условиям исходной задачи.
3. Если же есть нецелые свободные члены, то выбираем среди них член с наименьшим номером и рассматриваем соответствующую ему строку симплекс-таблицы. Допустим, эта строка с номером l. По выбранной строке записываем правильное отсечение вида 22.

Целочисленное программирование
Пример решения целочисленной задачи линейного программирования, используя алгоритм Гомори:
Решение:

Найдите графическим методом и методом Гомори оптимальное целочисленное решение задачи линейного программирования, если она задана следующей математической моделью
Решить целочисленные задачи линейного программирования методом Гомори
Найти целочисленное решение задачи линейного программирования. Составить двойственную задачу и решить её без условия целочисленности. По теоремам двойственности проверить связь нецелочисленных решений прямой и двойственной задачи.

Транспортные задачи

Транспортные задачи
ТАБЛИЦА ТРАНСПОРТНОЙ ЗАДАЧИ

Транспортная задача
Пример решения транспортной задачи:
Решение:

Транспортная задача

Транспортная задача

Транспортная задача
Три оптовых склада (A1 А2 A3) поставляют в три магазина розничной сети (B1 В2 B3) некоторый товар. Запасы данного товара на складах (шт.), потребности в нем магазинов (шт.) и тарифы на перевозку (в расчете на 1 шт.) приведены в транспортной таблице ниже. Найти оптимальный план перевозок, обеспечивающий удовлетворение потребностей магазинов в товаре с минимальными издержками на его транспортировку, а также общие затраты грузоперевозок.

Вопросы для проверки знаний
- Задачи линейного программирования (ЗЛП). Каноническая форма ЗЛП. План. Допустимый план. Теорема о множестве допустимых планов.
- Область допустимых решений. Ограниченная и неограниченная область допустимых решений. Геометрическая интерпретация ЗЛП для двумерного случая.
- Симплекс-метод Данцига. Базисный план. Леммы 1, 2. Теоремы Данцига.
Нахождение исходного базисного плана. Переход от одного базисного решения к другому.
- Двойственность в линейном программировании. Типы двойственных задач.
- Задачи линейного целочисленного программирования. Постановка задачи целочисленного программирования. Алгоритм метода Гомори для решения задач целочисленного программирования.
- Транспортные задачи. Постановка задачи и стратегия решения. Методы нахождения начального плана перевозок. Метод северо-западного угла. Метод минимальной стоимости. Решение транспортной задачи методом потенциалов.

1) Задачу линейного программирования можно сформулировать так:
А. найти максимум или минимум линейной формы при отсутствии ограничений на переменные;
B. найти нули функции при заданных интервалах их положения;
C. найти максимум или минимум линейной формы при заданных ограничениях в виде равенств или неравенств;
D. найти максимум или минимум нелинейной формы при заданных ограничениях в виде равенств или неравенств.
2) Симплекс-метод в задаче линейного программирования реализуется в виде:
A. системы линейных дифференциальных уравнений;
B. системы рекуррентных соотношений;
C. симплекс таблиц;
D. системы нелинейных дифференциальных уравнений.
3) Один из алгоритмов нахождения решения задачи целочисленного программирования группы методов отсекающих плоскостей называется:
A. алгоритм двойственного симплекс-метода;
B. алгоритм метода ветвей и границ;
C. алгоритм метода Гомори;
D. алгоритм симплекс-метода.
Примеры тестовых заданий для проверки знаний

4) Метод северо-западного угла это
A. один из методов проверки опорного плана транспортной задачи на оптимальность;
B. один из комбинированных методов дискретного программирования, при котором гиперплоскость, определяемая целевой функцией задачи, вдавливается внутрь многогранника планов соответствующей задачи линейного программирования до встречи с ближайшей целочисленной точкой этого многогранника;
C. один из методов отсечения, с помощью которого решаются задачи целочисленного программирования;
D. один из группы методов определения первоначального опорного плана транспортной задачи.
5) Оптимальный план задачи линейного программирования это
A. решение задачи линейного программирования, т. е. такой план, который не входит в допустимую область и доставляет экстремум целевой функции;
B. решение задачи линейного программирования, т. е. такой план, который входит в допустимую область и доставляет ненулевое значение целевой функции;
C. решение задачи линейного программирования, т. е. такой план, который входит в допустимую область и доставляет нулевое значение целевой функции;
D. решение задачи линейного программирования, т. е. такой план, который входит в допустимую область и доставляет экстремум целевой функции.
Примеры тестовых заданий для проверки знаний