Линейное программирование и методы оптимизации

Задание 1.

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

Решение:

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

Определим полуплоскости, которые задают неравенства-ограничения.

ОДР – многоугольник. Построим n=grad z=(2,1) и основную прямую z=0, перпендикулярную n.

Перемещая прямую z=0 в направлении n, получим, что последней крайней точкой, в которой прямая пересекается с ОДР, будет точка, в которой достигается максимальное значение целевой функции z. Координаты этой точки определяются решением системы двух линейных уравнений (I) и (II), на пересечении которых она находится. В результате решения системы уравнений (I) и (II) получим оптимальное решение x*:

Сформулируем задачу, двойственную по отношению к данной.

Введём двойственные переменные ; тогда двойственная задача будет иметь вид:

Задание 2.

Графическим способом решить задачу линейного программирования (). Сформулировать задачу двойственную по отношению к данной.

Решение:

Построим область допустимых решений на плоскости Ох1х2. Для этого запишем уравнения прямых из системы ограничений, заменяя неравенства равенствами:

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

Перемещая прямую z=0 в направлении , получим, что первой крайней точкой, в которой прямая пересекается с ОДР, будет точка А. Следовательно в этой точке достигается минимальное значение целевой функции z. Координаты точки А определяются решением системы 2-х линейных уравнений (I) и (II), на пересечении которых она находится.

В результате получаем оптимальное решение:

Сформулируем двойственную задачу.

Двойственная задача имеет вид:

Ответ.

Задание 3.

Построить математическую модель задачи и решить её с использованием симплекс-таблиц. Сформулировать соответствующую двойственную задачу и дать её экономическую интерпретацию.

На предприятии имеется несколько производственных линий. j-я линия производит в единицу времени единиц продукции i-го типа. Для выполнения задания предприятию необходимо выпускать не менее единиц i-го типа продукции, при этом эксплутационные расходы j-й линии составляют млн. руб. в единицу времени. Определить время работы каждой линии для выполнения задания при условии минимизации затрат.

Решение:

Постановка задачи в общем виде:

количество усл.ед. j-вида продукции.

Подставим исходные данные:

Для получения начального допустимого базиса и опорного решения воспользуемся методом элементарных преобразований. Построим симплекс-таблицу, где в качестве нулевой итерации возьмем коэффициенты целевой функции и системы ограничений.

 Скачать реферат