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

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

Цель работы

  1. Ознакомиться с принципами составления оценочных характеристик для задач линейного программирования.
  2. Научиться применять симплекс-метода для решения задач линейного программирования.
  3. Изучить табличную форму применения симплекс-метода.
  4. Объяснить различия получаемых результатов.

ТЕОРИЯ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ

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

целевой функции (на максимум или минимум) — формула (1.1),

основных ограничений- формула (1.2),

ограничений не отрицательности переменных (есть или нет) — формула (1.3)

(1.1)

i = 1,… m (1.2)

(1.3)

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

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

Существуют ограничения не отрицательности переменных (если их нет для некоторой переменной хk, то их можно ввести путем замены всех вхождений этой переменной комбинацией x1k — х2k = хk, где х1kи х2k). При этом для решения задачи линейного программирования необходимо иметь базис, т.е. набор переменных хi, в количестве, равным числу основных ограничений, причем каждая из этих переменных должна входить лишь в одно основное ограничение с множителем аij = 1. При отсутствии таких переменных их необходимо искусственно добавить в основные ограничения и снабдить индексами хm+1, xm+2и т.д. При этом считается, что переменные удовлетворяют условиям не отрицательности переменных. Заметим, что если базисные переменные (все) образуются в результате приведения задачи к каноническому виду, то целевая функция задачи не изменяется, а если переменные добавляются искусственно косновным ограничениям, имеющим вид равенств, то из целевой функции вычитается их сумма, умноженная на М, т.е. (так называемый модифицированный симплекс-метод).

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

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

(1.4)

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

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

Другой важной оценкой является тетта-оценка, следующего вида: (1.5)

По номеру k, найденному по дельта-оценке, мы получаем выход на переменную хkи элементы столбца ХB делим на соответствующие (только положительные) элементы столбца матрицы А, соответствующего переменой xk. Из полученных результатов выбираем минимальный, он и будет тетта-оценкой. аi-й элемент столбца B, лежащий в одной строке с тетта-оценкой, будет выводиться из базиса, заменяясь элементом xk, полученным по дельта-оценке. Для осуществления такой замены нужно в i-ю строку k-гo столбца матрицы А поставить единицу, а остальные элементы k-гостолбца заменить нулями. Подобное преобразование является одним шагом итерационного процесса.

Используем метод Гаусса для поведения преобразования. В соответствии с ним i-я строка всей матрицы А, а также i-я координата ХB делятся на aik (получаем единицу в i-ой строке вводимого в базис элемента). Затем вся i-я строка (если i не единица), а также i-я координата ХBумножаются на элемент (1k). После этого производится поэлементное суммирование чисел в соответствующих столбцах 1-ой и i-ой строк, суммируются также ХB1, и (1k)Bi. Для всех остальных строк кроме i-ой (базисной) строки производятся аналогичных действия. В результате получается, что в i-ой строке k-го элемента стоит 1, а во всех остальных его строках находятся 0. Так осуществляется один шаг итерационного алгоритма. Пошаговое выполнение алгоритма симплекс-метода продолжается до тех пор, пока не будет получен один из следующих результатов:

Все небазисные дельта-оценки больше нуля. Решение задачи линейного программирования представляет вектор с компонентами х, значения которых либо равны нулю, либо равны элементам столбца Х. Компоненты вектора стоят на базисных местах (например, если базис образуют переменные х2, x4, х5, то ненулевые компоненты стоят в векторе решения задачи линейного программирования на 2-м, 4-м и 5-м местах).

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

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

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

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

Таблица 1.1

B

CB

XB

A1

An

Q

Базисные

Целевые

Правые

компоненты

Коэффиц.

Части

Базиса

ограничен

D

D1

Dn

Задание

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

L (x) = x1 — 2x2 + 3x3

x1 — 3x23

2x1 — x2 + x33

-x1 + 2x2 — 5x33

Все xi0 i = 1, …3

1. Вначале сведем задачу к каноническому виду

L (x) = x1 — 2x2 + 3x3

x1 — 3x2 + x4 = 3

2x1 — x2 + x3 + x5 = 3

-x1 + 2x2 — 5x3 + x6 = 3

Все xi0 i = 1, …6

2. Составим таблицу симплекс-метода (табл. 1.2)

В данном случае базис образуют компоненты x4, x5, x6.

B

CB

XB

A1

A2

A3

A4

A5

A6

Q

A4

0

3

1

-3

0

1

0

0

-

A5

0

3

2

-1

1

0

1

0

3

A6

0

3

-1

2

-5

0

0

1

-

D

-1

2

-3

0

0

0

A4

0

3

1

-3

0

1

0

0

A3

3

3

2

-1

1

0

1

0

A6

0

3

-1

2

0

0

0

1

D

9

5

2

0

0

3

0

После вычисления дельта-оценок можно сделать вывод.

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

3. Решение задачи будет выглядеть следующим образом

X* = (0, 0, 3, 3, 0, 3), L*(X*) = 9.