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

Размещено на http://www.allbest.ru/

1. Построение канонической формы задачи ЛП

Привести задачу к канонической форме.

(1)

В задаче (1) нарушены все три признака КФ.

Начнем с преобразования смешанной системы ограничений в систему уравнений. Для этого введем в первое и второе ограничения неотрицательные переменные y₁ которые называются дополнительными или слабыми. В результате система ограничений запишется в следующем виде:

(2)

Условия неотрицательности в (2) не выполняются только для переменной x₂. Представим переменную x₂, x₄ в виде разности двух неотрицательных переменных: После преобразования системы ограничений и целевой функции получим задачу

(3)

Ответ:

2. Графическое решение задачи ЛП

Решить графически задачу ЛП, заданную в канонической форме:

(6)

(8)

Число уравнений задачи m=4, число неизвестных n=2. Тогда n-m=-2 и задача может быть сведена к задаче на плоскости относительно свободных переменных.

Этап 1. Построение допустимой области.

Каждое из неравенств определяет некоторую полуплоскость :

Пересечением полуплоскостей будет являться область, координаты точек которого удовлетворяют условию неравенствам системы ограничений задачи.

Обозначим границы области многоугольника решений.

Этап 2. В допустимой области находим оптимальное решение.

Рассмотрим целевую функцию задачи

F = x2 > max.

Построим прямую, отвечающую значению функции F = 0: F = x2 = 0. Будем двигать эту прямую параллельным образом. Поскольку нас интересует максимальное решение, поэтому двигаем прямую до последнего касания обозначенной области. На графике эта прямая обозначена пунктирной линией.

Область допустимых решений представляет собой многоугольник.

Прямая F(x) = const пересекает область в точке D. Так как точка D получена в результате пересечения прямых (1) и (2), то ее координаты удовлетворяют уравнениям этих прямых:

-4x1+3x2?0

2x1+x2?10

Решив систему уравнений, получим: x1 = 3, x2 = 4

Откуда найдем максимальное значение целевой функции:

F(X) = 0*3 + 1*4 = 4.

3. Решение задачи в специальной форме симплекс-методом

Решить задачу, записанную в виде:

Составим симплексную таблицу:

Так как коэффициенты строки целевой функции неотрицательны, то начальное базисное решение не является оптимальным. Значение целевой функции для этого базиса L=0.

Выбираем ведущий столбец - это столбец, который соответствует переменной x₁.

Выбираем ведущую строку. Ведущая строка соответствует переменной y₁.

Проводим преобразование симплексной таблицы, вводя переменную x₁ в базис и выводя переменную y₁ из базиса. Получим таблицу:

Одна итерация метода завершена. Переходим к новой итерации. Полученная таблица неоптимальная. Базисное решение, соответствующее таблице, имеет вид . Значение целевой функции на этом базисе L= -5.

Ведущий столбец здесь - столбец, соответствующий переменной x₃. Ведущая строка - строка, соответствующая переменной y₂. После проведения преобразований получим симплексную таблицу:

Еще одна итерация завершена. Переходим к новой итерации.

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

4. Решение задачи методом искусственного базиса

Выделить допустимое базисное решение для задачи ЛП.

Приведем задачу к канонической форме на минимум с неотрицательными правыми частями.

В первую строку ограничений вводим искусственную переменную z, потому что в этой строке нет переменной, которую можно взять базисной, не проводя при этом дополнительных преобразований всей системы ограничений.

Полученная вспомогательная задача имеет вид

Приведем задачу к виду (16):

Выпишем соответствующую симплексную таблицу:

Выбираем ведущим столбцом столбец переменной x₁, получим ведущую строку - строку с переменной z. Тогда искусственная переменная z выйдет из базиса, а переменная x₁ введется в базис.

Симплексная таблица преобразуется к виду

Так как значение , то полученный базис x₁=5/3, x₄=2, является начальным допустимым базисом для исходной задачи ЛП. Чтобы выразить целевую функцию подставим значение базисной переменной в целевую функцию. В результате получим

Тогда исходная задача будет иметь вид специальной формы задачи ЛП:

что и требовалось получить в результате решения вспомогательной задачи.

5. Построение двойственной задачи

Построить двойственную задачу к следующей задаче ЛП.

Прежде чем приступать к построению двойственной задачи, необходимо упорядочить запись исходной: согласовать знаки неравенств в ограничениях с целевой функцией. Так как ЦФ минимизируется, то неравенства должны быть записаны с помощью знака «».

Для этого первое неравенство умножим на -1:

Теперь, вводя двойственные переменные , y₄ запишем в соответствии с указанным правилом пару двойственных задач:

Задача слева - исходная прямая задача, задача справа - двойственная к исходной задаче.

6. Решение пары двойственных задач

Используя теоремы двойственности, решить двойственную задачу, если известно решение прямой задачи.

(12)

Пусть решение задачи найдено одним из стандартных методов: . Построим двойственную задачу:

(13)

По первой теореме двойственности задача разрешима, причем . Найдем оптимальный план задачи (13), используя вторую теорему двойственности. Подставим координаты вектора в ограничения задачи (12). Получим

Следовательно, в силу УДН, неравенство должно выполняться как равенство, т.е. . Далее так как , то в силу УДН,

.

Получаем систему линейных уравнений и решаем ее:

Планы и удовлетворяют УДН, следовательно, в силу второй теоремы двойственности, являются оптимальными в задачах (12) и (13) соответственно.

7. Проверка вектора на оптимальность

Исследовать вектор на оптимальность в задаче ЛП.

Вначале нужно проверить, является ли вектор допустимым. Для этого подставляем координаты вектора в ограничения:

линейный программирование симплекс двойственный

Так как первое ограничение не выполняется как строгое неравенство, то в силу УДН вектора не оптимален.

Размещено на Allbest.ru