Учебная работа № 1907. Решение задач линейного программирования

Учебная работа № 1907. Решение задач линейного программирования

Министерство общего и профессионального образования Российской Федерации Воронежский Государственный Архитектурно – Строительный Университет Кафедра Экономики и управления строительством ЛАБОРАТОРНАЯ РАБОТА На тему : «Решение задач линейного программирования» Выполнил: Студент 4 курса ФЗО ЭУС Сидоров В.В. Руководитель: Богданов Д. А. Воронеж – 2002 г.

ЛАБОРАТОРНАЯ РАБОТА № 11

РЕШЕНИЕ ЗАДАЧ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ

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

ТЕОРЕТИЧЕСКИЕ ОСНОВЫ

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

целевой функции (на максимум или минимум) формула (1.1), основных oграничений формула (1.2), ограничений не отрицательности переменных (есть, нет) формула (1.3)

(1.1)

i = 1,… m (1.2)

(1.3)

Алгоритм решения задач линейного программирования требует приведения их постановки в канонический вид , когда целевая функция стремится к максимуму (если стремилась к минимуму, то функцию надо умножить на 1, на станет стремиться к максимуму), основные ограничения имеют вид равенства (для приведения к равенствам в случае знака надо в правую часть каждогo такого kго неравенства добавить искусственную переменную u_k , а в случае знака , u_k надо отнять ее из правой части основных ограничений), присутствуют ограничения не отрицательности переменных (если их нет для некоей переменной х_k , то их можно ввести путем замены всех вхождений этой

переменной комбинацией x¹ _k х ² _k = х _k , где х ¹ _k и х ² _k ). При этом для решения задачи линейного программирования необходимо иметь базис , т.е. набор переменных х _i , в количестве, равным числу основных ограничений, причем чтобы каждая из этих переменных присутствовала лишь в одном основном oграничении и имела свой множитель а _ij = 1 . Если таких переменных нет, то они искусственно добавляются в основные ограничения и получают индексы х _m+1 , x_m+2 и т.д. Считается при этом, что они удовлетворяют условиям не отрицательности переменных. Заметим, что если базисные переменные (все) образуются в результате приведения задачи к каноническому виду, то целевая функция задачи остается без изменений, а если переменные добавляются искусственно к основным ограничениям, имеющим вид равенств, то из целевой функции вычитается их сумма, умноженная на М, т.е. (так называемый модифицированный симплексметод ). Мы не будем рассматривать задачи, относящиеся к модифицированному симплексметоду. Для практической работы по нахождению решения задачи линейного программирования (по варианту простого симплексметода )будут использоваться алгоритм итерационного (многошагового) процесса нахождения решения и два типа оперативных оценок, позволяющих делать переходы от одного шага к другому, а также показывающих, когда итерационный процесс остановится и результат будет найден.

Первая оценка это дельтаоценка , для переменной х _j она имеет вид:

(1.4)

Здесь выражение i B означает, что в качестве коэффициентов целевой функции, представленных в сумме выражения (1.4), используются коэффициенты переменных, входящих в базис на данном шаге итерационного процесса. Переменными а _ij являются множители матрицы коэффициентов А при основных ограничениях, рассчитанные на данном шаге итерационного процесса. Дельтаоценки рассчитываются по всем переменным х_i , имеющимся в задаче. Следует отметить; что дельтаоценки базисных переменных равны нулю. После нахождения дельтаоценок из них выбирается наибольшая по модулю отрицательная оценка, переменная х_k , ей соответствующая, будет вводиться в базис. Другой важной оценкой является теттаоценка , имеющая вид:

(1.5)

Т.е. по номеру k, найденному по дельтаоценке, мы получаем выход на переменную х_k и элементы столбца Х^B делим на соответствующие (только положи

тельные) элементы столбца матрицы А, соответствующего переменой x_k . Из полученных результатов выбираем минимальный, он и будет теттаоценкой, а_i й элемент столбца B , лежащий в одной строке с теттаоценкой, будет выводиться из базиса, заменяясь элементом x_k , полученным по дельтаоценке. Для осуществления такой замены нужно в iой строке k гo столбца матрицы А сделать единицу, а в остальных элементах k гостолбца сделать нули. Такое преобразование и будет одним шагом итерационного процесса. Для осуществления такого преобразования используется метод Гаусса . В соответствии с ним iя строка всей матрицы А, а также iя координата Х ^B делятся на a_ik (получаем единицу в iой строке вводимого в базис элемента). Затем вся iя строка (если i не единица), а также iя координата Х^B умножаются на элемент (а_1k ). После этого производится поэлементное суммирование чисел в соответствующих столбцах 1ой и iой строк, суммируются также Х^B ₁ , и (а_1k )*Х^B _i ;. Аналогичные действия производятся для всех остальных строк кроме iой (базисной) строки. В результате получается, что в iой строке kго элемента стоит 1, а во всех остальных его строках находится 0. Таким образом осуществляется шаг итерационального алгоритма, Шаги алгоритма симплексметода продолжаются до тех пор, пока не будет получен один из следующих результатов.
• Все небазисные дельтаоценки больше нуля — найдено решение задачи ли

нейного программирования, оно представляет из себя вектор компонент х;, значения которых либо равны нулю, либо равны элементам столбца Х, тав

кие компоненты стоят на базисных местах (скажем, если базис образуют переменные х₂ , x₄ , х₅ , то ненулевые компоненты стоят в векторе решения задачи линейного программирования на 2м, 4м и 5м местах).

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

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

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

записывать в виде Х* = (…, …, …) вектора решения и значения целевой функции в точке решения L *(Х*). В других случаях (решений много или они отсутствуют) следует словесно описать полученную ситуацию. Если решение задачи линейного программирования не будет получено в течение 1012 итераций симплексметода, то следует написать, что решение отсутствует в связи с неограчниченностью функции цели.

Для практического решения задачи линейного программирования симплексметодом удобно пользоваться таблицей вида (табл. 11.1):

Таблица 1.1

B	CB	XB	A1	…	An	Q
Базисные	Целевые	Правые
компоненты	Коэффиц.	Части
Базиса	ограничен
D	D1	D n

Задание

Необходимо решить задачу линейного программирования.

L(x) = x₁ – 2x₂ + 3x₃

x₁ – 3x₂ 3

2x₁ – x₂ + x₃ 3

x₁ + 2x₂ – 5x₃ 3

Все x_i 0 i = 1, … 3

1. Для начала приведем задачу к каноническому виду :

L(x) = x₁ – 2x₂ + 3x₃

x₁ – 3x₂ + x₄ = 3

2x₁ – x₂ + x₃ + x₅ = 3

x

Учебная работа № 1907. Решение задач линейного программирования