Скачать: 2-laba.zip [42,42 Kb] (cкачиваний: 53)

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

Лабораторная работа №2

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

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

Выполнили:

Проверил:

Цель и содержание работы

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

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

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

Симплексный метод

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

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

Понятие о симплекс-методе. Симплекс-метод, называемый также «методом последовательного улучшения плана», впервые был предложен Г. Данцигом в 1947 году. Этот метод позволяет переходить от одного допустимого базисного решения к другому, причем так, что значения целевой функции непрерывно возрастают. В результате оптимальное решение находят за конечное число шагов. Алгоритмы симплекс-метода позволяют также установить, является ли задача ЛП разрешимой.

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

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

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

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

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

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

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

(1)

и среди неотрицательных решений системы уравнений (1) надо найти такое, которое бы максимизировали или минимизировали линейную функцию

.

Алгоритм решения задачи симплекс-методом состоит из следующих этапов.

Во-первых, необходимо убедиться в совместности системы линейных алгебраических уравнений (1). Если ограничительные условия заданы неравенствами, то их нужно преобразовать в равенства путем введения новых неотрицательных переменных, так называемых балансовых (выравнивающих). Так, например, в неравенстве а₁ x₁ + а₂x₂ +…+ a_n x_n достаточно добавить к левой части х_{n +1,} и получится равенство а₁ x₁ + а₂x₂ +…+ a_n x_n +х_n+1 .

Ограничительные условия могут задаваться и смешанным образом, т. е. неравенствами и уравнениями. Тогда указанным способом их можно всегда свести к ограничениям вида (1).

Работа симплекс-метода начинается с выбора опорного решения, содержащего r базисных переменных и n-r свободных переменных. Так как в задаче имеется m уравнений-ограничений, то неизвестные переменные х₁,…,х_r можно выразить через остальные n-r переменные и уравнения-ограничения (1) могут быть преобразованы к следующему виду:

x₁ = а’_{1,r +1} x_{r +1} +…+ a’_1n x_n + b’₁,

x₂ = а’_{2, r + 1} x_{r + 1} +…+ a’_2n x_n + b’₂,

… … … … … (2)

x_r = а’_{r, r +1} x_{r +1} +…+ a’_2n x_n + b’_r,

где .

Неизвестные переменные х₁,х₂,…,х_r называются базисными. Остальные переменные называются свободными. При этом систему ограничений (2) называют системой, приведённой к единичному базису.

Подставляя теперь в линейную форму l вместо базисных переменных их выражения через свободные из системы (2), получим

l = g₀ + g _{r +1}x _r+1 +…+g _n x _n . (3)

Теперь, полагая все свободные переменные равными нулю, найдём значения базисных переменных: x₁=b’₁, x₂=b’₂,…, х_r=b’_r. Таким образом, решение системы (b’₁, b’₂,…, b’_r, 0,…,0) является допустимым – оно называется базисным. Подставляя в линейную форму l значения базисных переменных, получим базисное значение линейной формы . Для полученного базисного решения .

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

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

Таким образом, далее меняем одну из свободных переменных с таким расчётом, чтобы значение уменьшалось, или, по крайней мере, не увеличивалось, если нами решается задача на нахождение , т.е. переходим к новому базису такому, что . Процесс продолжается итеративно до тех пор, пока все коэффициенты в уравнении (2.13) не станут положительными.

Если ищется , то переход к новому базису осуществляется так, чтобы выполнялось неравенство: . Соответственно, процесс продолжается до тех пор, пока все коэффициенты в уравнении (3) не станут отрицательными.

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

Расчетная часть

Порядок выполнения работы

Задание №5

Найти оптимальные неотрицательные решения, минимизирующие линейную форму:L = х₁ – х₂ + х₃+ х₄ + х₅ – х₆ при ограничениях:

х₁ + х₄+ 6х₆ = 9,

3х₁ + х₂– 4х₃ + 2х₆ = 2,

х₁ + 2х₃+ х₅ + 2х₆ = 6;

Решение:

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

Система ограничений совместна, так как ранги соответствующих матриц совпадают и равны 3. Следовательно, три базисных переменных можно выразить линейно через другие три свободные. Примем за свободные переменные х₂ и х₄ и х₅. Тогда:

Таким образом, выразили базисные переменные через свободные:

При х₂=0,х₄=0, х₅ =0 базисные переменные , т.е. имеем первое допустимое решение и . Уменьшение L можно осуществить при увеличении х₂до 5. Тогда х₂ переходит в базисные, а х₁ – в свободные, т.к. при х₂=5 х₁=0.

Перепишем систему уравнений через новые свободные переменные:

.

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

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

Задание №6

Найти оптимальные неотрицательные решения, максимизирующие линейную форму:

х₁ + х₂+ 5х₃ = 20,

х₂ + 2х₄5,

х₁ + х₂– х₃ 8;

L = 2х₁ + х₄