Главная страница

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


Скачать 0.59 Mb.
Название"Решение оптимизационных задач линейного программирования"
Дата19.09.2022
Размер0.59 Mb.
Формат файлаdoc
Имя файлаКурсовой проект Вариант 20.doc
ТипПояснительная записка
#684806
страница2 из 3
1   2   3

4 Решение задачи оптимизации на основе симплекс-таблиц
Приведём математическую модель задачи к стандартной форме. Для этого в ограничения “меньше или равно” потребуется ввести остаточные переменные, а в ограничения “больше или равно” потребуется ввести избыточные переменные:
Х14=40 (1)

0,8Х1+0,5Х2+0,6Х35=800

0,2Х1+0,4Х2+0,3Х36=600 0Х1+0,1Х2+0,1Х37=120

i ≥ 0, i = 1,…,3 ,

Е=314Х1+120Х2+128Х3 >max.

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

Поэтому требуется ввести искусственную базисную переменную. Система ограничений с искусственными базисными переменными будет иметь вид:

Х148=40 (1)

0,8Х1+0,5Х2+0,6Х35=800

0,2Х1+0,4Х2+0,3Х36=600 0Х1+0,1Х2+0,1Х37=120

i ≥ 0, i = 1,…,3 ,
Составляется искусственная целевая функция – сумма искусственных переменных:

W= Х8→ min.
Искусственная целевая функция выражается через небазисные переменные. Для этого сначала выразим искусственные переменные через небазисные переменные:
Х8=40-Х14,

и подставим их в искусственную целевую функцию:

W = 40-Х14,→ min.
Для приведения всей задаче к стандартной форме требуется перейти к искусственной целевой функции, подлежащей максимизации. Для этого она умножается на -1:
-W = -40+Х14,→ max.
Приведем полную математическую модель задачи в стандартной форме:

Х148=40 (1)

0,8Х1+0,5Х2+0,6Х35=800

0,2Х1+0,4Х2+0,3Х36=600 0Х1+0,1Х2+0,1Х37=120

i ≥ 0, i = 1,…,8,
Е=314Х1+120Х2+128Х3 >max,
-W = -40+Х14,→ max.
Составим первую симплекс таблицу (таблица 1):
Таблица 1

БП

X 1

X 2

X 3

X 4

X 5

X 6

X 7

X 8

БР

E

-314

-120

-128

0

0

0

0

0

0

-W

-1

0

1

0

0

0

0

0

-40

X8

1

0

0

-1

0

0

0

1

40

X5

0,8

0,5

0,6

0

1

0

0

0

800

X6

0,2

0,4

0,3

0

0

1

0

0

600

X7

0

0,1

0,1

0

0

0

1

0

120


Приведённое в таблице 1 начальное решение является недопустимым: в базисе есть искусственные переменные, и искусственная целевая функция не равна нулю. В случае, когда строка искусственной целевой функции (-W) не будет содержать отрицательных значений, данное решение будет оптимальным. Иначе необходимо составлять следующую симплекс-таблицу.

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

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

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

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

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

Согласно правилу прямоугольника пересчитываемый элемент и ведущий составляют одну из диагоналей прямоугольника. На второй диагонали находим еще два элемента. Отношение разности произведений элементов диагонали к ведущему элементу и дадут искомую величину.
Аналогично пересчитаем все элементы таблицы и получим новую (Таблица2):
Таблица 2

БП

X1

X2

X3

X4

X5

X6

X7

X8

БР

E

0

-120

-128

-314

0

0

0

314

12560

-W

0

0

0

0

0

0

0

1

0

X1

1

0

0

-1

0

0

0

1

40

X5

0

0,5

0,6

0,8

1

0

0

-0,8

768

X6

0

0,4

0,3

0,2

0

1

0

-0,2

592

X7

0

0,1

0,1

0

0

0

1

0

120


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

Х2348=0, Х1=40, Х5=768, Х6=592, Х7=120, E=12560 (в этом легко убедиться, подставив значения исходных переменных задачи в математическую модель).

Т.о. строку с искусственной целевой функцией и столбцы с искусственными переменными можно исключить из таблицы.

Получаем следующую симплекс-таблицу (Таблица 3):

Таблица 3

БП

X1

X2

X3

X4

X5

X6

X7

БР

E

0

-120

-128

-314

0

0

0

12560

X1

1

0

0

-1

0

0

0

40

X5

0

0,5

0,6

0,8

1

0

0

768

X6

0

0,4

0,3

0,2

0

1

0

592

X7

0

0,1

0,1

0

0

0

1

120


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

Определим переменную для включения в базис. Такой переменной станет X4. Определим переменную для исключения из базиса. Составляем симплексные отношения:

40/(-1)= -40,

768/0,8= 960,

592/0,2=2960.

Переменная с минимальным симплексным отношением исключается из базиса, т.е. переменная Х5.

Т.о. ведущий столбец X4, ведущая строка X5, ведущий элемент 0,8.

Строим новую симплекс-таблицу (Таблица 4).
Таблица 4

БП

X1

X2

X3

X4

X5

X6

X7

БР

E

0

76,25

107,5

0

392,5

0

0

314000

X1

1

0,63

0,75

0

1,25

0

0

1000

X4

0

0,63

0,75

1

1,25

0

0

960

X6

0

0,28

0,15

0

-0,25

1

0

400

X7

0

0,1

0,1

0

0

0

1

120


Последняя симплекс-таблица не содержит отрицательных элементов в строке целевой функции. Это указывает на оптимальность найденного решения. Проанализируем получившийся результат:
X1=1000, т.е. 1000 т следует выпустить карамели «Мечта».

X2=0, т.е. не нужно выпускать карамель «Заря».

X3=0, т.е. не нужно выпускать карамель «Полёт».

X4=960, т.е. карамели «Мечта» выпустят на 960 тон больше, чем минимально необходимо.

X6=400, остаточная переменная закупки потока, т.е. из возможных 600 тонн, закупят только 200 тонн.

X7=120,остаточная переменная закупки фруктового пюре.

Расчёты базовой задачи на программе Simplex-M приведены в “Приложении А”, а проверка расчетов при помощи Excel приведена в “Приложении Б”.
1   2   3


написать администратору сайта