Шурко Введение в системный анализ

1

ДОНБАССКАЯ ГОСУДАРСТВЕННАЯ АКАДЕМИЯ СТРОИТЕЛЬСТВА

И АРХИТЕКТУРЫ

КАФЕДРА “ВЫСШАЯ МАТЕМАТИКА И ЭКОНОМЕТРИЯ”

КОНСПЕКТ ЛЕКЦИЙ по

“ВВЕДЕНИЮ В СИСТЕМНЫЙ АНАЛИЗ”

для инженерных специальностей

дневного отделения

доц. Шурко Г.К.

УТВЕРЖДЕНО НА ЗАСЕДАНИИ КАФЕДРЫ ВЫСШЕЙ МАТЕМАТИКИ И ЭКОНОМЕТРИИ ПРОТОКОЛ № ___________________

УТВЕРЖДЕНО НА ЗАСЕДАНИИ СОВЕТА ФАКУЛЬТЕТА ФОП ПРОТОКОЛ № ___________________

г. Макеевка 2001 г.

2

СОСТАВЛЕНИЕ МАТЕМАТИЧЕСКИХ МОДЕЛЕЙ ОПТИМИЗАЦИОННЫХ ИНЖЕНЕРНОЭКОНОМИЧЕСКИХ ЗАДАЧ

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

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

Задача 1.

Предприятие изготовляет продукцию 2 наименований П1 и П2, используя при этом 4 ресурсаР1, Р2, Р3, Р4.

Норма затраты, каждого из ресурса и прибыль от реализации выпускаемой продукции приведены в таблице №1.

Учитывая наличие ресурсов, нормы затраты и прибыль составить такой план реализации выпуска продукции П1 и П2, которые обеспечил бы наибольшую суммарную прибыль.

Алгоритм.

1 шаг. Введение переменных величин.

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

В нашей задаче введем 2 переменные величины Х1 и Х2. Х1- количество единиц продукции вида П1.

Х2- количество единиц продукции вида П2.

2 шаг. Получение системы ограничений.

3

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

3 шаг. Получение целевой функции.

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

4Х1 -это прибыль от реализации Х1 единиц продукции П1.

5Х2 - это прибыль от реализации Х2 единиц продукции П2.

L = 4 Х1 + 5 Х2 max (2)

- суммарная прибыль от реализации продукта Х1 и Х2.

Полученная математическая модель, т.е. система ограничений (1) и целевая функция (2) представляет собой задачу линейного программирования (планирования) З.Л.П.

Графический способ решения задач

линейного программирования

Графический способ решения задач линейного программирования применяется тогда, когда число переменных входящих ЗЛП не превышает 3.

Наиболее удобен графический способ, когда число переменных равно 2.

Прежде перейдем к описанию алгоритма графического способа решения определим некоторые понятия.

4

Допустимым планом (решением) ЗЛП называется множество значений переменных входящих в ЗЛП и удовлетворяющих системе ограничений.

Оптимальным планом (решением) ЗЛП называется такой допустимый план при котором достигается оптимальное значение целевой функции.

Алгоритм графического способа.

Алгоритм опишем на примере задачи линейного программирования (1) и

(2).

1 шаг. Получение выпуклого многоугольника допустимых решений.

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

Для построения многоугольника введем прямоугольную систему координат с осями Х1 и Х2.

2 шаг. Строим область допустимых решений для системы

ограничений.

Х1 0,

Х2 0

3х1 + 7х2 21

10Х1 + 8 Х2 40

5

3шаг. Строим вектор нормали n, выходящий из начала координат

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

4шаг. Перпендикулярно направлению вектора n проводим прямую

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

5 шаг. Перемещаем прямую l вдоль направления вектора n

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

достигается min целевой функции.

В последней же точке - max.

Если при решении задачи одна из сторон многоугольника допустимых решений окажется параллельной прямой l, то max (min) достигается в любой точке этой стороны.

Проверка.

Решим систему уравнений:

3х1 + 7х2 = 21

10Х1 + 8 Х2 = 40

х1=(21-7*х2)/3=2,43 10*(21-7*х2)/3+8*x2=40 70-23,3*х2+8*х2=40 -15,3*х2=-30

х2=1,96

6

СИМПЛЕКС-МЕТОД

("МЕТОД ПОСЛЕДОВАТЕЛЬНОГО УЛУЧШЕНИЯ ПЛАНА")

1. Понятие о симплекс-методе.

Впервые был разработан Данцигом в 1947г. Позволяет переходить от одного

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

функции возрастают. В результате оптимальное решения находят за конечное

число шагов.

Или, в векторной форме:

L=( c * x ) + c0 max

При выполнении условий:

A * X = B,

где:

c = (c1,c2,...,cn) ,

8

Условие (4) аналогично условию:

n

S аi*xк = bi , i=1,2,...,m; n m.

к=1

хк 0 , к=1,2,...,n.

При этом можем считать, что bi 0, i=1,2,...,m.

Предположим, что ранг матрицы А равен r; r m. Выразим переменные х1, х2, ... , хr (которые называются базисными переменными) через остальные

переменные (которые называются свободными):

Система уравнений (5) называется системой, приведенной к единичному базису, а

набор (х1, х2,…, хк) – базисом. Подставляя в функцию L вместо базисных переменных их выражения через свободные из (5), получим:

n

допустимым. Оно называется базисным.

Для полученного базисного решения значения целевой функции будет равно:

LБ = 0.

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

заключающихся в том, что от данного базиса Б мы переходим к другому базису Б` с таким расчетом, чтобы

LБ LБ`.

9

2. Симплексные таблицы.

В виде таблицы эти данные можно представить так:

БАЗИСЫЕ СВОБОД-

соответствующих свободных переменных Xj.

АЛГОРИТМ СИМПЛЕКС-МЕТОДА.

1 шаг. Выбирается р-ый разрешающий столбец из условия: оценка

p <0 и хотя бы один элемент aip >0.

2 шаг. Выбирается q-я разрешающая строка из условия:

строки по формуле.

10

a aqk (k 1,....., n)

qk aqk

4 шаг. Вычисляются элементы всех остальных строк (при к p) по формуле:

a`ik = aik - a`qk * aip ( i=1,...,q-1,q+1,...,n ).

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

5 шаг. В базис вводится переменная хp и выводится переменная xq.

Следует иметь в виду основную теорему симплекс-метода:

Теорема. Если после выполнения очередной операции;

1)найдется хотя бы одна отрицательная оценка и в каждом столбце с такой оценкой будет хотя бы один положительный элемент, т.е. k<0 для некоторого k и aik >0, для тех же к и некоторого i, то можно улучшить решение, выполнив следующую операцию;

2)найдется хотя бы одна отрицательная оценка, столбец которой не содержит положительных элементов, т.е.

k < 0,

aik < 0.

для какого-то k и всех i, то функция L неограничена в области допустимых решений;

(Lmax )

2x1+ x2 13

3x2 15

3x1 18