Решение задач линейного программирования

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

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

Министерство образования и науки РТ

Альметьевский государственный нефтяной институт

Кафедра «Автоматизации и информационных технологий»

Отчет по лабораторной работе

по дисциплине:

«Моделирование систем»

«Решение задач линейного программирования»

Миннахметова А.А., Мухаметзянов Р.

Альметьевск 2014 г.

Цель работы

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

Основные сведения из теории

Среди известных разделов математического программирования наиболее развитым является линейное программирование (ЛП). Несмотря на требование линейности целевой функции, и ограничений, в рамки линейного программирования укладываются задачи распределения ресурсов, управления запасами, конструкций и технологических процессов производства аппаратуры и т.д.

Постановка задач линейного программирования и их геометрическая интерпретация

В задачах линейного программирования критерий оптимальности представляется в виде:

(1)

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

(2)

Коэффициенты в соотношение (2) принимаются действительными числами, положительными или отрицательными, среди которых могут быть равные нулю.

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

, (3)

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

(4)

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

9 задача

Решить задачу максимизации критерия оптимальности, имеющего вид:

При наличии ограничений на и типа неравенств:

Решить аналитически и графически.

Решение:

I. 1) Перепишем систему ограничений в виде равенств:

2) Составим матрицу системы и расширенную матрицу и найдем их ранги:

ранг = 2;

; ранг = 2;

3) За базисные переменные примем , , следовательно, свободные переменные - ,.

; ; ;

; ; ;

4) Следовательно, целевая функция

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

Таким образом, оптимальное решение

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

2) Рассмотрим первое неравенство системы ограничений .

Построим прямую. Заменим знак неравенства на знак равенства. . Преобразуем уравнение следующим образом. . Данное представление прямой называется уравнением прямой в отрезках и позволяет, очень легко, нарисовать данную прямую. На оси рисуем точку с координатой 1/2 . На оси рисуем точку с координатой 1 .Соединяем полученные точки и получаем необходимую прямую.

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

3) Рассмотрим второе неравенство системы ограничений .

Построим прямую. Заменим знак неравенства на знак равенства. . Преобразуем уравнение следующим образом. . Данное представление прямой называется уравнением прямой в отрезках и позволяет, очень легко, нарисовать данную прямую. На оси рисуем точку с координатой 1. На оси рисуем точку с координатой 1/2 .Соединяем полученные точки и получаем необходимую прямую.

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

4) Пересечением полуплоскостей будет являться область, координаты точек которого удовлетворяют условию неравенствам системы ограничений задачи. Обозначим границы области многоугольника решений (рис.1).

Рис.1.

5) Рассмотрим целевую функцию задачи > max. Из начала координат проводим вектор . Из начала координат перпендикулярно вектору перемещаем прямую по всей области. Поскольку нас интересует максимальное решение, поэтому двигаем прямую до последнего касания обозначенной области.

Рис.2

линейное программирование аналитика геометрия

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

Прямая пересекает область в точке C. Так как точка C получена в результате пересечения прямых, то ее координаты удовлетворяют уравнениям этих прямых. Решив систему уравнений, получим: , (рис.2).

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

Видим, что решение, полученное графическим путем, совпадает с решением, полученным аналитическим методом.

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