О САЙТЕ
Добро пожаловать!

Теперь вы можете поделиться своей работой!

Просто нажмите на значок
O2 Design Template

ФЭА / АИТ / Лабораторная работа №2 по дисциплине: «Моделирование систем» на тему: «Решение задач линейного программирования»

(автор - student, добавлено - 20-09-2017, 20:51)

 

 

 

 

 

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

 

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

 

 

 

 

 

 

 

 

 

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

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

 

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

 

 

 

Выполнили:

Проверил:

 

 

 

 

 

 

 

 

 

 

 

 

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

(1)

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

.

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

Во-первых, необходимо убедиться в совместности системы линейных алгебраических уравнений (1). Если ограничительные условия заданы неравенствами, то их нужно преобразовать в равенства путем введения новых неотрицательных переменных, так называемых балансовых (выравнивающих). Так, например, в неравенстве а1 x1 + а2x2 +…+ an xn достаточно добавить к левой части хn +1, и получится равенство а1 x1 + а2x2 +…+ an xn +хn+1 .

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

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

x1 = а’1,r +1 xr +1 +…+ a1n xn + b1,

x2 = а’2, r + 1 xr + 1 +…+ a2n xn + b2,

… … … … … (2)

xr = а’r, r +1 xr +1 +…+ a2n xn + br,

где .

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

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

l = g0 + g r +1x r+1 +…+g n x n . (3)

Теперь, полагая все свободные переменные равными нулю, найдём значения базисных переменных: x1=b1, x2=b2,…, хr=br. Таким образом, решение системы (b1, b2,…, br, 0,…,0) является допустимым – оно называется базисным. Подставляя в линейную форму l значения базисных переменных, получим базисное значение линейной формы . Для полученного базисного решения .

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

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

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

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

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

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

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

Задание №5

Найти оптимальные неотрицательные решения, минимизирующие линейную форму:L = х1 – х2 + х3+ х4 + х5 – х6 при ограничениях:

х1 + х4+ 6х6 = 9,

1 + х2– 4х3 + 2х6 = 2,

х1 + 2х3+ х5 + 2х6 = 6;

Решение:

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

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

 

 

 

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

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

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

 

.

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

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

Задание №6

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

х1 + х2+ 5х3 = 20,

х2 + 2х45,

х1 + х2– х3 8;

L = 2х1 + х4

 

 


Ключевые слова -


ФНГ ФИМ ФЭА ФЭУ
Copyright 2018. Для правильного отображения сайта рекомендуем обновить Ваш браузер до последней версии!