Основная задача.

F=CX —> min

A₁X₁+A₂X₂+...+A_nX_n=A₀ (*)

, , , , C=(c₁, c₂, ... , c_n)

Система векторов является линейнозависимой, если существуют числа

₁, ₂, ... , _ь

не все =0, при которых имеет место равенство

₁A₁+₂A₂+ ... +_mA_m=0 (1)

Если соотношение (1) возможно лишь тогда когда все =0.

Теорема о крайней точке

Если в системе ограничений вектора А₁,А_2, ... ,А_m (m<n) линейнонезависимы и существует Х_j0 такое, что

A₁x₁+A₂x₂+...+A_mx_m=A₀ ,

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

Доказательство.

Пусть Х – допустимое базисное решение (*), и эта точка не является крайней. Пусть имеется две точки, ,

которые удовлетворяют системе величин

Если точка Х не крайняя, то её можно представить в виде линейной комбинации

X=X₁+(1-)X₂, 01

Получим

Вычтем

Данное равенство справедливо при

Отсюда вытекает, что точки Х₁ и Х₂ совпадают, а это противоречит тому что Х не является крайней точкой ==> Х – крайняя точка.

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

Табличный алгоритм замены переменных.

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

Задача в стандартной постановке:

(1) F(x₁,x₂,…,x_n)=c₁x₁+c₂x₂+…c_nx_n max

a₁₁x₁+a₁₂x₂+…+a_1sx_s+…a_1nx_n<=b₁

a_i1x₁+a_i2x₂+…+a_isx_s+…a_inx_n<=b_i (2)

……..

……..

a_m1x₁+a_m2x₂+…+a_msx_s+…a_mnx_n<=b_m

x_j >=0, j=1..n

Сведем эту стандартную постановку к основной задаче линейного программирования, т.е. необходимо, чтобы fmin.

F(x₁,x₂,…,x_n)=c₁x₁-c₂x₂-…-c_nx_n min (3)

Введем дополнительные неотрицательные переменные: y₁,y₂,…,y_m>=0, т.о. к (2) прибавляем:

a₁₁x₁+a₁₂x₂+…+a_1sx_s+…a_1nx_n+ y₁<=b₁

a_i1x₁+a_i2x₂+…+a_isx_s+…a_inx_n+ y_i<=b_i (4)

……..

……..

a_m1x₁+a_m2x₂+…+a_msx_s+…a_mnx_n+ y_m<=b_m

x_j >=0, j=1..n

Выберем в качестве базисных переменных y₁,y₂,…,y_m , тогда все остальные будут свободными (x₁,x₂,…,x_n). Выразим и запишем в стандартном виде:

F(x₁,x₂,…,x_n)= 0-(c₁x₁+c₂x₂+…c_nx_n )min (5)

y₁₌ b₁-(a₁₁x₁+a₁₂x₂+…+a_1sx_s+…a_1nx_n)

y_i=b_i-(a_i1x₁+a_i2x₂+…+a_isx_s+…a_inx_n) (6)

……..

……..

y_m=b_m-(a_m1x₁+a_m2x₂+…+a_msx_s+…a_mnx_n)

Занесем полученное в таблицу:

Базисные переменные	Свободные члены	Свободные переменные
		x1	x2	…	xs	…	xn
y1	b1	a11	a12	…	a1s	…	a1n
:	…	…	…	…	…	…	…
yi	bi	ai1	ai2	…	ais	…	ain
:	…	…	…	…	…	…
yr	br	ar1	ar2	…	ars	…	arn
:	…	…	…	…	…	…	…
ym	bm	am1	am2	…	ams	…	amn
f	C0	C1	C2	…	Cs	…	Cn

Другими словами выразить переменную y_r через базисную переменную x_s. Мы хотим получить : (y₁,y₂,…,y_r,…,y_m,0,…0)

меняем местами

(y₁,y₂,…,x_s,…,y_m,0,…0)

Каждый разделим на a_rs и получим:

x_s= b_r/ a_rs+( a_r1*x₁/ a_rs+ a_rs*x₂/ a_rs+…+ 1*y_r/ a_rs+…+ a_rn*x_n/ a_rs)

y_i= b_i –( a_i1*x₁+a_i2*x₂ +…+a_is*[b_r/a_rs–(a_ri*x₁+ a_rs*x₂/a_rs+ 1*y_r/a_rs+…+a_rn*x_n/a_rs)]+…+ a_in*x_n)= b_i- a_is*b_r/a_rs-((a_i1- a_is*a_ri/a_rs)*x₁+((a_i2-a_is*a_rs/a_rs)*x₂+a_is*y_r/a_rs+…+(a_in- a_is*a_rn/a_rs)*x_n

Аналогично можно записать: C₀=C₀-b_ri/a_rs;C^*_s= -C_s/a_rs;C^*_j=C₀-a_rj/a_rs;

Полученные значения для x_s,y_i и функции определяют правила преобразования таблицы при переходе от одного базисного решения к другому, т.е. при замене y_r на x_s.

Алгоритм замены переменных.

Строка таблицы, соответствующая переменной y_r называется разрешающей строкой и помечается «», а столбец таблицы, соответствующий переменной x_s называется разрешающим столбцом и помечается «». Элемент таблицы, расположенный на пересечении разрешающих строки и столбца называется разрешающим элементом a_rs.

1) Новое значение разрешающего элемента : a^*_rs=1/a_rs

2) Новое значение элементов разрешающей строки : a^*_rj= a^*_rj/a_rs (i<>r)

3) Новое значение элементов разрешающего столбца получается делением старого значения на разрешающий элемент и все берется с обратным знаком a^*_is=-a_is/a_rs (i<>r)

4) Все остальные элементы таблицы, не принадлежащие пунктам 1)-3), получаются как алгебраическая сумма прежнего значения и произведения элементов со значениями a_rj и a^*_is (i<>r,j<>s). a^*_ij=a_ij+a_rj+a^*_is

5) Переход к следующей таблице, в которой вместо базисной переменной y_r записываем x_s , а в столбце свободных переменных вместо x_s записываем y_r и переписываем числа из нижних частей предыдущей таблицы в верхнюю часть новой таблицы.

Лекция 7. СИМПЛЕКСНЫЙ МЕТОД РЕШЕНИЯ ЗАДАЧИ Л.П.

Идея: в основе симплекс метода лежит процедура целенаправленного перебора допустимых базисных решений. Симплексный метод представляет собой вычислительный алгоритм, состоящий из конечного числа итераций. На каждой итерации находится базисное решение. В общем случае количество итераций заключено между m и 2m (m – число ограничений).

Предположим k – количество свободных переменных, n – общее количество переменных, m – количество уравнений, k=n-m.

x, x,…, x - свободные переменные.

Выразим базисные переменные через свободные:

x= x+x+…+x+;

x= x+x+…+x+;

x= x+x+…+x+;

C = j+jx+j₂x₂+…+j_kx_k

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

В частности, для k=2, вершина многоугольника – есть пересечение двух прямых, на каждой из которых соответ-я переменная равная нулю. Для попадания в первую вершину многоугольника k переменных x₁,x₂,…,x_k

Тогда целевая функция = j₀, а оставшиеся базисные переменные соответственно равны:

X_k+1=_k+1 0

X_k+2=_k+2 0

….

X_n=_n 0

Справедливо при условии C = j₀.

Целью решения задачи является минимизация задачи С. Измененные значения С получается при изменении переменных x₁, x₂, … , x_k. Если все коэффициенты j₁, j₂, …, j_k > 0, то при положительном изменении свободных переменных, целевая функция возрастает. Следовательно не отрицательность коэффициентов j целевой функции является признаком оптимальности полученного решения.

Предположим, что один из коэффициентов, пусть j₁ < 0. Тогда, возрастание x₁ приводит к уменьшению целевой функции С. Необходимо определить граничное значение переменной x₁. Для этого анализируются знаки коэффициентов , , …, , при переменной x₁. Если все коэффициенты не отрицательные, то это указывает на то, что целевая функция не ограничена на области ОДР и следовательно оптимального решения не существует.

Предположим, что один из коэффициентов (<0). Тогда возрастание x₁ приводит к уменьшению значения x_k+2. Предельное значение переменной x₁ определяется нулевым значением x_k+2. Следовательно, предельное значение x₁ находится из _k+2,1x₁ + _k+2 = 0;

X₁ = - _k+2/ _k+2,1

_k+2,1 < 0.

Таким образом, переменная x_k+2=0, а x₁ присвоено положительное значение. Общее количество нулевых переменных осталось неизменным, равным k, т.е. произошел переход из одной вершины многоугольника в другую. Целевая функция уменьшилась на величину j₁ * (-_k+2/ _k+2,1).

Предположим, что не один, а несколько коэффициентов при x₁ отрицательны. Тогда предельное значение x₁ будет определяться из:

x_{1 =} min {- _k+i/_k-i,1} при условии _k-i,1<0.

Описанная процедура повторяется пока, все коэффициенты j целевой функции не станут неотрицательными. Перед выполнением процедуры необходимо выполнить преобразования связанные с переводом x_i с правой части уравнения в левую часть и наоборот x_k+i из левой части в правую.

Лекция 8. Алгоритм нахождения допустимого базисного значения.

1)Исходная задача сводится к основной задаче линейного программирования.

2)Задача записывается в стандартной записи.

3)Заполняется симплексная таблица, коэффициенты которой переносятся из стандартной записи задачи.

4)Анализ свободных членов симплексной таблицы. Если все элементы столбца свободных членов (кроме последнего ) неотрицательны ,то получено ДБР. Базисные переменные равны соответствующим свободным членам , а все свободные переменные равны 0.

Переход к поиску оптимального решения.

5)Анализ задачи на разрешение. Если в симплексной таблице найдётся строка в которой свободный член отрицательный ,а все элементы этой строки неотрицательны , то задача не имеет решения.

6)Выбор разрешающего столбца .В строке с отрицательным свободным членом выбирается любой отрицательный элемент и столбец ,в котором расположен этот элемент объявляется разрешающим .

7)Выбор разрешающей строки.

Для элементов разрешающего столбца ,вычисляется (если существуют симплексные отношения ). Строка для которой симплексные отношения min объявляется разрешающей строкой. Если min симплексные отношения не единственные, то выбирается любая строка в качестве разрешающей строки.

8)Используя табличный алгоритм замены переменных, преобразуем симплексную таблицу. Меняем местами переменные соответствующие разрешающей строки и столбца. Переход на п.4 алгоритма.

Нахождение оптимального решения.

1. Пусть в результате проведения к итерации над симплексной таблицей получено ДБР. Из числа базисных переменных выведены 1-е переменные у₁…у_к, а введены переменные х₁….х_к. Обозначим элементы строки целевой функции С (j=).Пусть какой-то элемент С>0 , а элементы этого столбца  , а все элементы этого столбца отрицательны (i=) .Тогда для какого-то i-го элемента строки Х_i =_i -(Y*Y₁ +X*Y₂ +…+X*Y_k + …+*X_s+…+ *X_n) , где i<k

Y_j=_j –(*Y₁+*y₂ +…+*y_k +*X_k+1 +…+*y_s +…+*X_n) , j>k .

F=C-(C+…+ C*Y_k +…+ C*X_n)

Приравняем к 0 : y₁=y₂=…=y_k=0 ,X_k+1=0,X_s-1=0,X_s0, X_s+1=0,X_n=0.

А 0 , 0

Пусть X_s ,тогда X_i , будут положительными. Если посмотреть на функцию , то видно, что она будет убывать неограниченно .Таким образом, получим критерий неограниченно. Таким образом, получим критерий неограниченности целевой функции. Если в таблице найдётся такой столбец в котором коэффициент в строке целевой функции положительный , а все элементы этого столбца 0, то целевая функция в исходной задаче неограниченна ,т.е. задача не имеет оптимального решения .

2)Пусть значение целевой функции после K итераций равно С.

Пусть в качестве следующей итерации выполняем К+1 , в качестве разрешающей строки выбрана строка r , и столбец S ,разрешающий элемент . После к+1 шага новое значение будет равно С= С -. Если С>0 ,то С< С , т. е значение функции уменьшилось. Если для всех элементов строки функции S= С<0 , то значение функции будет больше. Т.е при любом выборе разрешающего столбца уменьшение функции невозможно.

Критерий оптимальности решения:

Если все коэффициенты строки целевой функции (исключая свободные члены) неположительные, то полученное ДБР является оптимальным. Таким образом, по коэффициентам элементов целевой функции можно определить достигнуто ли оптимальное решение. Если не все элементы строки целевой функции неотрицательны ,то необходимо продолжить преобразования . И в качестве разрешающего элемента выбирается столбец с положительным коэффициентом в строке целевой функции. Для определения будем выбирать столбец с max коэффициентом. Для обеспечения перехода к новому ДБР дающему меньшее значение целевой функции в качестве разрешающей строки, как и при поиске ДБР строка выбирается по min для разрешающего столбца симплексному отношению.

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

1)Анализ коэффициентов строки целевой функции.

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

2)Анализ ограниченности целевой функции.

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

3)Выбор разрешающего столбца.

В качестве разрешающего столбца выбирается столбец с положительным элементом в строке целевой функции (с max).

4)Выбор разрешающей строки.

Для выбранного разрешающего столбца составляются симплексные отношения (0). Строка, для которой эти отношения min выбирается в качестве разрешающей.

5)Замена переменных.

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

Лекция 9. РЕШЕНИЕ ЗАДАЧИ СО СМЕШАННЫМИ ОГРАНИЧЕНИЯМИ.