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

Введение

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

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

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



1. Формулировка задачи линейного программирования

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

(1.1)

при условиях

(1.2)

(1.3)

Функцию (1.1) называют целевой, а условия (1.2) - (1.3) - ограничениями задачи.

Задачей линейного программирования, заданной в симметричной форме записи, называют задачу, в которой требуется найти максимум функции (1.1) при условиях (1.2) и условиях

(1.4)

Задачей линейного программирования в канонической форме записи называют задачу, в которой требуется найти максимум функции (1.1) при условиях (1.3), где s=0, и (1.4).

Набор чисел =(х₁;...;х_n), удовлетворяющих ограничениям задачи линейного программирования, называется ее планом. План *=(х₁*;...;х_n*), доставляющий максимум (минимум) функции (1.1), называется оптимальным.

Поскольку min f=-max (-f), то задачу минимизации функции f формально можно свести к задаче максимизации противоположной функции (-f). Найдя максимальное значение функции (-f), его знак нужно заменить на противоположный. Тем самым определится минимальное значение исходной функции.

2. Симплекс-метод

а) Алгоритм метода.

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

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

(2.1)

(2.2)

(2.3)

Решение задачи (2.1) - (2.3) складывается из двух этапов: на первом находят какой-либо начальный опорный план , на втором -- по специальным правилам переходят от начального плана к другому, более близкому к оптимальному, опорному плану , затем к следующему и так до тех пор, пока задача не будет решена.

1. Нахождение начального опорного плана.

Для нахождения начального опорного плана задачи (2.1)-(2.3) можно предложить следующий алгоритм:

записать задачу в форме жордановой таблицы так, чтобы все элементы столбца свободных членов были неотрицательными, т.е. выполнялось неравенство ?0 (i=). Те уравнения системы (2.2), в которых свободные члены отрицательны, предварительно умножаются на (-1).

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

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

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

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

Если система ограничительных уравнений совместна, то через некоторое число шагов все нули в левом столбце будут замещены х и тем самым получен некоторый базис, а следовательно, и отвечающий ему опорный план (табл. 2.2). Чтобы выписать из таблицы компоненты опорного плана, нужно положить равными нулю свободные переменные, тогда базисные переменные будут равны соответствующим свободным членам. Отвечающее опорному плану значение функции f равно свободному члену , т. е. .

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

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

1) просматривают строку, отвечающую какому-либо отрицательному свободному члену, например t-строку, и выбирают в ней какой-либо отрицательный элемент, а соответствующий ему столбец принимают за разрешающий (мы предполагаем, что ограничения задачи совместны);

2) составляют отношения элементов столбца свободных членов к соответствующим элементам разрешающего столбца, имеющим одинаковые знаки (симплексные отношения);

3) из симплексных отношений выбирают наименьшее. Оно и определит разрешающую строку. Пусть ею будет, например, р-строка;

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

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

2. Нахождение оптимального опорного плана.

Начальный опорный план исследуется на оптимальность:

1) если в f-строке нет отрицательных элементов (не считая свободного члена) -- план оптимален.

Если в f-строке нет также и нулевых элементов, то оптимальный план единственный; если же среди элементов есть хотя бы один нулевой, то оптимальных планов бесконечное множество;

2) если в f-строке есть хотя бы один отрицательный элемент, а в соответствующем ему столбце нет положительных, то целевая функция не ограничена в допустимой области (f>?). Задача неразрешима;

3) если в f-строке есть хотя бы один отрицательный элемент, а в каждом столбце с таким элементом есть хотя бы один положительный, то можно перейти к новому опорному плану, более близкому к оптимальному. Для этого столбец с отрицательным элементом в f-строке берут за разрешающий (если в f-строке отрицательных элементов несколько, разрешающим выбирают столбец с наибольшим по абсолютной величине отрицательным элементом); определяют по минимальному симплексному отношению разрешающую строку и делают шаг жорданова исключения. Полученный опорный план вновь исследуют на оптимальность.

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

б) Применение искусственного базиса.

Решение задачи линейного программирования симплекс-методом начинается с нахождения какого-либо опорного плана.

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

a_i0?0 (i=),(3.1)

введем в каждое из уравнений по одной неотрицательной переменной х_n+i?0, (i=), которые будем называть искусственными, а из линейной формы вычтем сумму искусственных переменных, умноженную на как угодно большое положительное число М.

В результате получим так называемую М-задачу:

(Max)(3.2)

(i=);(3.3)

x_j?0 (i=). (3.4)



В системе (3.3) переменные x_n+i (i=1,m) образуют базис, называемый искусственным. При x_i=…=х_n=0 из (3.5) получаем начальный опорный план ₀= (0; ... ; 0; a_i0; ... ; a_m0) M-задачи.

Получение оптимального опорного плана исходной задачи основано на следующих утверждениях.

- Если в оптимальном плане М-задачи все искусственные переменные х_n+i = 0 (i= ), т. е. * = (х₁*; ...; х_n*; 0; ...; 0), то план х* = (х₁*; ...; х_n*) является оптимальным планом исходной задачи.

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

- Если М-задача не имеет решения, то и исходная задача неразрешима.

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

Как видно из равенства (3.2), функция F состоит из двух слагаемых и , поэтому в симплексных таблицах для нее удобней отводить две строки: одну -- для f, другую -- для Если преобразования выполняются с двумя строками, то признак оптимальности проверяется сначала по второй строке.

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

Если в исходной задаче нам нужно целевую функцию минимизировать, то в М-задаче целевая функция будет иметь вид и также минимизируется.

в) Двойственность в линейном программировании.

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

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

Двойственную задачу можно сформулировать следующим образом.

Найти вектор Y = (у₁, у₂, у_n), который удовлетворяет ограничениям

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

f=b₁y₁+b₂y₂+…+b_my_m

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

Исходная задача. Сколько и какой продукции х_j (j= 1,2, .... п) необходимо произвести, чтобы при заданных стоимостях С_j (j= 1,2, ...n) единицы продукции и размерах имеющихся ресурсов b_i (i=1,2,...т) максимизировать выпуск продукции в стоимостном выражении.

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

Переменные y_i называются оценками пли учетными, неявными ценами.

Многие задачи линейного программирования первоначально ставятся в виде исходных или двойственных задач, поэтому имеет смысл говорить о паре двойственных задач линейного программирования.

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

min Z = max f.

Если линейная функция одной из задач не ограничена, то другая не имеет решения.

3. Расчётный раздел

Задание №1

Задание №1.1

Графическое решение задачи линейного программирования.



z=-2+5>min

Построим граничные линии. Выразим х2 и построим график.

Решение:

1. Представим систему неравенств в виде системы равенств - совокупность прямых ограничивающих области, представленные в системе неравенств:

z=-2+5>min

2.Рассмотрим точки для построения граничных прямых

: (-5; ) (5; -)

: (-5; ) (5; )

: (-5; ) (5; )

Построим вектор .. (-2; )

3.Целевая функция представляет собой прямую, проходящую через точку (0;0) (10;4)

4.Построим область допустим решений:

5. Точка максимума (;)

Точка минимума (;)

Ответ: Zmin=-; Zmax=

Задание №2

Решить задачу симплекс - методом c использованием искусственного базиса на нахождение минимума линейной функции

Решение:

1.Заменим систему неравенств системой уравнений, для этого введем дополнительный переменные:

2.Введем искусственный базис:

3.Выразим переменные х4, х5, через свободные переменные х1, х2, х3:

Первый опорный план (0,0,0,200,180)

Z=0-(-2x?-3x?-4x?)

Так как в нуль-записи есть отрицательные коэффициенты, то:

Выбрал элемент с наибольшим по модулю отрицательным коэффициентом, т. е. переменную x₃. Данную переменную перенес в базис, т.е. выразил ее через остальные:

Выразим из каждого уравнения этой системы x₃

Подставим полученное x3 в систему

X₃=100

X₃=45

X₄=200-3_x1-3_x2-2_x3-2(45-x2-)

Подставим x2 в нуль - уравнение

X₄=200-3_x1-3_x2-2_x3-2(45-x2-)

X₄=110-2x1-+

Z=2x?+3_x2+4*(45-)

Z=2_x1+3_x2+180-2_x1-3_x2+_x5

Z=180+x5

Так как в 0-уравнении положительныe коэффициенты, решение заканчивается

Второй опорный план(0,0,45,200,0)

Ответ:Zmax=180 при x?=45

Задание № 2.1

Решение задачи с помощью симплекс-таблицами

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



базис	св.член	х1	х2	х3	х4	х5	оцен.отн
х4	200	3	3	2	1	0	100
х5	180	2	3	4	0	1	45
F	0	-2	-3	-4	0	0

2)Составляем оценочное отношение каждой строки по следующим правилам:

1. ?, если b_is и a_is имеют разные знаки

2. ?, если b_is=0 и a_is<0

3. ?, если a_is=0

4. 0, если b_is=0 и a_is>0

5. , если b_is и a_is имеют одинаковые знаки

Выбираем строку, в которой оценочное отношение минимально:

базис	св.член	х1	х2	х3	х4	х5	оцен.отн
х4	200	3	3	2	1	0	100
х5	180	2	3	4	0	1	45
F	0	-2	-3	-4	0	0

Эта строка называется разрешающей. Элемент, на пересечении разрешающего столбца и строки называется разрешающим.

Переходим к следующей таблице. Переносим переменную x₃ в базис вместо x₅.Разделим ведущую строку на 4. Далее, прибавляем ведущую строку к второй строке.. Получим таблицу:

базис	св.член	х1	х2	х3	х4	х5	оцен.отн
х4	110	2	1,5	0	1	-0,5
Х3	45	0,5	0,75	1	0	0,25
F	180	0	0	0	0	1

Критерий оптимальности выполнен. Определим оптимальный план.

(0,0,45,200,0)

Ответ: Zmax=180 при x?=45

Задание № 2.2

Решим данную задачу с помощью надстройки «Поиск решения» табличного процессора MS Excel.

На значения переменных установим ограничения: x₁, x₂, x₃ и x₁, x₂, x₃ - целые числа. В ячейки программного средства вводим исходные данные и формулы:

· В ячейках B2:D2 находятся значения переменных x₁, x₂, x₃ соответственно. Присвоим значения 0, 0, 0.

· В ячейки B6:D6 вводим коэффициенты при переменных в целевой функции (2, 3, 4).

· В ячейку E6 вводим выражение целевой функции «=СУММПРОИЗВ(B6:D6;B2:D2)».

· В ячейки B8:D9 помещаем коэффициенты при переменных в ограничениях задачи.

· В ячейки E8:E9 вводим выражения левых частей ограничений функции.

· В ячейках F8:F9 указываем знаки для наглядности.

· В ячейки G8:G9 поместим значения правых частей ограничений функции.

После ввода данных запускаем надстройка «Поиск решения» и заполняем необходимые поля: ограничения переменных на значения и ограничения функций. Операции добавления представлены на рисунках 3, 4, 5:



В параметрах указываем, что модель задачи оптимизации является линейной. Параметры поиска решения показаны на рис. 6:

После выполнения получаем значение переменных и - это и есть оптимальное решение поставленной задачи.



Заключение

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

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

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

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