В. 7 Алгоритм прямого симплексного метода.

Прямой симп. метод предназначен для решения задачи ЛП вида .

Симплексный метод можно применять, только если выполняются 3 условия:

1) задача ЛП имеет канонический вид;

2) правая часть ограничений (вектор свободных членов) неотрицателен (b≥0)

3) матрица А содержит единичную подматрицу (имеется начальное допустимое базисное решение).

Тогда можно построить начальную симплексную таблицу:

			с1	c2		сn
	Базис	БДР	x1	x2	…	xn
cB	xB	b	A
	z	∆0	∆1	∆2	…	∆n

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

Элементы вектора c_B содержат коэффициенты целевой функции, соответствующие базисным переменным. Столбец «Базис» содержит названия текущих базисных переменных (в правильном порядке). Столбец «БДР» показывает текущее значение базисных переменных, при которых достигается текущее значение целевой функции. В конце работы алгоритма в этом столбце будет содержаться ответ.

Алгоритм прямого симплексного метода.

Шаг 0. Построить начальную симп.таблицу. В столбце «Базис» записать базисные переменные в правильном порядке. Вычислить оценки. Перейти на шаг 1.

Шаг 1. Проверить оценки . Если все оценки , то найдено оптимальное решение. Перейти на шаг 5.

Среди положительных оценок найти максимальную и столбец, соответствующий выбранной оценке, объявить ведущим (s). Перейти на шаг 2.

Шаг 2. Просмотреть элементы s-го столбца, если все они , то целевая функция неограниченна (нет оптимального решения), перейти на шаг 5. Иначе перейти на шаг 3.

Шаг 3. Для положительных элементов s-го столбца найти строчку r, в которой симп. отношение b_r/a_rs принимает минимальное значение. Объявить строку r ведущей. Перейти на шаг 4.

Шаг 4. На пересечении ведущего столбца и ведущей строки обозначить ведущий элемент. Нарисовать новую симплексную таблицу. На месте элемента x_r в столбце «базис» поставить элемент x_s и с помощью преобразования Жордана-Гаусса пересчитать всю таблицу (в том числе оценки и столбец БДР). Перейти на шаг 1.

Шаг 5. Конец алгоритма.

Пример в распечатке!

В. 8 Основные этапы решения задач оптимизации.

Задача оптимизации решается в 4 этапа:

1) Постановка задач и составление качественной модели.

Качественная модель – чёткое словесное описание задачи (также называется концептуальной).

На этом этапе выделяют наиболее важные факторы, влияющие на принятие решений. Факторы делятся на 2 категории:

1. Управляемые – те, которые можно изменить в процессе решения.

2. Неуправляемые – те, которые нельзя изменить в процессе решения.

На этом же этапе устанавливаются связи между выбранными факторами, выбираются один или несколько критериев оптимальности.

2) Построение математической модели.

Математическая модель – это абстракция реального мира, выраженная в виде математических соотношений.

На этом же этапе качественная модель превращается в математическую. Как происходит превращение:

1. Каждому неуправляемому фактору ставится в соответствие константа равная этому фактору.

2. Каждому управляемому фактору ставится в соответствие переменная.

3. Критерию оптимальности ставится в соответствие целевая функция.

Целевая функция – это функция, большему или меньшему значению которой соответствует наилучшее решение с точки зрения критерия оптимальности.

4. Выявленные закономерности между факторами записывают в виде математических соотношений (равенств или неравенств).

3) Решение задачи.

4) Проверка адекватности модели по отношению к реальности. Если данная модель предполагает абсурдные решения задачу нужно переосмыслить.

В. 9 Стандартный вид задач ЛП

Задача может быть на минимум:

, i=1,…,m

0, j=1,…,n

Задача может быть на максимум:

, i=1,…,m

0, j=1,…,n

Ax b

x 0

В. 10 Алгоритм приведения задач ЛП к каноническому виду

Любую задачу ЛП можно решить симплексным методом. Для начала её нужно привести к каноническому виду.

Правила:

1) если исходная задача на максимум, то коэффициенты целевой функции умножаем на «-1» и получаем задачу на минимум.

2x₁-x₂→max

-2x₁+x₂→min

2) если есть ограничения типа “≥”, то из левых частей каждого из таких ограничений вычитаем по одной дополнительной переменной и ставим знак “=”. Для каждого ограничения даётся своя новая переменная.

2x₁+x₂≥5

2x₁+x₂-x₃=5

3) если есть ограничения типа “≤”, то к левым частям каждого из таких ограничений прибавляем по одной дополнительной переменной и ставим знак “=”.

2x₁+x₂≤5

2x₁+x₂+x₃=5

4) если некоторые переменные x_j имеют значение “≤0”, то мы должны заменить их на “-x_j”, тогда ограничения станут правильными.

x_j ≤0

x_j’ = -x_j

x_j’≥0

5) если переменная x_j может иметь любой знак, то заменяем его на разность 2-х переменных, которые не отрицательны.

Например:

Пример в тетради!

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

В. 11 Математическая модель задачи об оптимальном распределении ресурсов.

Пусть имеется n - видов продукции и m - видов сырья. Пусть с_j - это прибыль от реализации единицы j-ого вида продукции (j=1,…,n).

b_i - запас i-ого вида сырья (i=1,…,m).

Пусть a_ij - это норма расхода i-ого вида сырья, необходимого для получения единицы j-ого вида продукции. Нужно ответить на вопрос:

Какую продукцию и в каком объёме производить так, чтобы суммарная цена от реализации была максимальной?

Решение:

Пусть x_j - объём производства товаров j-ого вида

- выручка (критерий оптимальности)

- сколько потрачено на производство всей продукции j ( - управляемый фактор)

x_j ≥0

В12 Математическая модель задачи о выборе оптимального рациона

Пусть имеется n - видов продовольственных товаров и m - видов витаминов.

Пусть с_j - стоимость единицы j-ого вида товара, (j=1,…,n). Пусть b_i -минимальное количество витаминов, требуемых организму в день, (i=1,…,m).

Пусть - норма содержания i-ого вида витамина в товаре j-ого вида. Нужно ответить на вопрос:

Какие товары следует закупать и в каком количестве, чтобы минимизировать затраты и обеспечить организм суточной нормой витаминов?

Пусть x_j - объём купленного товара j-ого вида (управляемое)

- всего витаминов i-ого вида (не меньше, чем требуется)

x_j ≥0

В13 Математическая модель задачи оптимального линейного раскроя.

Целлюлозно-бумажный завод, рулон шириной 9м. (бумажный)

1 вариант раскроя: допустим, есть один станок, который может распилить рулон на 3 равные части

Предполагается, что у нас неограниченное количество исходных рулонов.

Допустим, заказчик заказал:

(с_j - объём отходов при j-ом способе раскроя)

A - 20 шт B - 10 шт C - 15 шт (по 3м вариантам раскроя)

1способ: с₁=0,

2 способ: с₂=1,

3 способ: с₃=2.

x_j - количество раз, которое мы будем использовать раскрой вида j

+ + (общее кол-во рулонов, которое мы используем) M

Второе неравенство показывает количество заготовок вида А при 1-м, 2-м, 3-м способе раскроя.

Модель задачи в общем виде.

Введем следующие обозначения:

m - виды заготовок. n - способы раскроя.

с_j - объём отхода при j-том способе раскроя (j=1,2,...,n),

a_ij - количество заготовок i типа, которое выходит при раскрое по j-му способому

b_ij - количество заготовок i-того вида, которое нужно получить (i=1,2,...,m).

х_j – количество раз, которое мы будем использовать раскрой вида j.

x_j ≥0, ∑x_j≤M – количество рулонов, которое мы используем при выполнении заказа.

В14 Определение базисного допустимого решения (БДР) задачи линейного программирования

Система векторов А₁, А₂,…, A_k называется линейно зависимой, если существуют такие числа α₁, α₂,…, α_k не равные нулю одновременно, что сумма α₁*А₁+α₂*А₂+α_k*A_k=Θ (нулевому вектору). В противном случае систему векторов называют линейно независимой.

Пример 1:

Являются ли вектора линейно зависимыми?

- линейная комбинация векторов.

α₁= -1, α₂=2, α₃= -1

Ответ: линейно зависимы.

Линейная зависимость векторов означает, что один из них можно выразить через остальные.

Пример 2:

Линейно независимы, т. к. α₁ и α₂ не могут быть одновременно равны 0.

Опр: Максимальное кол-во линейно независимых векторов – столбцов матрицы называется рангом матрицы.

r(ранг)=2; ранг = 1, т.к. можно выразить через

Замечания:

1) у единичной матрицы всегда полный ранг (все столбцы линейно независимы)

2) если определитель квадратной матрицы=0, то её столбцы линейно зависимы

3) в матрице количество линейно независимых строк равно количеству линейно независимых столбцов

БДР – это решение, которое удовлетворяет следующим условиям:

1) оно допустимо

2) количество базисных переменных = рангу матрицы А

3) базисные переменные соответствуют линейно независимым столбцам матрицы А

Пример:

х = (5, 0, 1, 7) – числа выбираем сами как удобно, например x₂=0 => x₁=5.

1) +; 2) базисные переменные 5,1,7 соответствуют столбцам единичной матрицы; 3) ранг = 3.

В. 15 Определение базиса задачи Л.П., вырожденные и невырожденные БДР.

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

Базисные переменные – это часть вектора БДР, в которой переменные соответствуют линейно независимым столбцам матрицы А, эти переменные ≥ 0, из будем обозначать х_В, небазисные переменные – это остальные переменные, они равны нулю.

БДР называется вырожденным, если среди базисных переменных есть хоть одна = 0, если все базисные переменные строго положительные, то БДР называется невырожденным.

Пример: , 3-й и 4-й столбцы линейно независимы – базис, - вектор ограничений. А*х=в. Решив систему уравнений с 3-м и 4-м столбцами получим: х₃=0, х₄=2. х = (0, 0, 0, 2, 0) – 3-я и 4-я базисные переменные, остальные переменны кроме базиса = 0. - БДР. В качестве базиса также можно было выбрать 1-й и 3-й столбцы.