Первый подход к поиску базиса.

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

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

    С экономической точки зрения свободные переменные представляют собой неиспользованные ресурсы, следовательно, их «цена» в целевой функции = 0, т. е. они не учитываются в целевой функции.

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

    Симплекс-метод основан на разложении векторов по базису. Условия задачи можно записать в виде векторов.

 = P₁        =P_2……     = P_n

 = P₀  -вектор решений.

 

 

Пример задачи оптимизации и её решение

Симплекс-методом.

    Необходимо загрузить судно в порту 3-мя родами груза а, б, в. Грузоподъёмность судна = 2000т (Q_p); грузовместимость(W) = 3080м³; удельный погрузочный объём каждого груза: W_а  =2, 1м³/т

                                                 W_б = 1, 5м³/т

                                                 W_в = 1, 7м³/т

Max возможное время погрузки (Т_n^max) = 36ч = 2160 мин

Удельное время погрузки каждого рода груза:

                         t_а = 0, 8мин/т

                         t_б = 0, 9мин/т

                         t_в = 1, 3мин/т

Имеется в порту в наличии груза:

                      а = 900т

                      б = 1300т

                         в = неограниченное количество

За перевозку 1т груза взимается провозная плата:

                      Са = 8 у. е.

                      Сб = 7, 5 у. е.

                       Св = 7 у. е.

Необходимо составить оптимальный план загрузки судна на max дохода

Обозначим: х₁ – количество груза а, загруженного в оптимальном плане.

                 х₂ – количество груза б, загруженного в оптимальном плане.

                 х₃ – количество груза в, загруженного в оптимальном плане.

Целевая функция - доход

Z = 8x₁ + 7, 5x₂ + 7x₃ → max

 

                   Ограничения.

    Перейдём от системы неравенств к системе равенств, добавляя свободные переменные.

х₄ – неиспользуемая грузоподъёмность

    х₅ – неиспользуемая грузовместимость

 х₆ – неиспользуемое до max время

           погрузки.

    х₇ – недопогруженное количество груза а.

    х₈ – недопогруженное количество груза б.

 

    Представим условия (т. е. ограничения) в виде векторов.

Р₁ = Р₂ =    Р₃ =    Р₄ =

 

 

Р₅ =     Р₆ =     Р₇ =     Р₈ =     Р₀ =

 

 

    Вектора Р₁, Р₂, Р₃, образованные из коэффициентов при реальных переменных, называются структурными.

    Вектора Р₄, Р₅, Р₆, Р₇, Р₈ называются линейно не зависимыми (свободными) векторами, Р_о – вектор решений.

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

 

Алгоритм решения предусматривает построение симплекс-таблиц.

Сi		Сj	8	7, 5	7	0	0	0	0	0
	базис	P0	P1	P2	P3	P4	P5	P6	P7	P8
0	P4	2000	1	1	1	1	0	0	0	0
0	P5	3080	2, 1	1, 5	1, 7	0	1	0	0	0
0	P6	2160	0, 8	0, 9	1, 3	0	0	1	0	0
0	P7	900	1	0	0	0	0	0	1	0
0	P8	1300	0	1	0	0	0	0	0	1
Zj			0	0	0	0	0	0	0	0
Zj - Cj			- 8	- 7, 5	- 7	0	0	0	0	0

 

Z _j – симплекс-оценка

Zj =

Z _j – C_j – признак оптимальности в симплекс-методе.

    Если задача решается на max и значение последней строки ≥ 0 по всем столбцам, то план является оптимальным.

    Если задача решается на min и значение последней строки 0, то план так же является оптимальным.

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

 Z_j – C_j < 0, то план не оптимален и требует улучшения.

В общем виде первоначальная симплекс-таблица выглядит следующим образом:

 

 

Ci		Cj	c1	-	cj	-	C k	-	cn
	базис	Р0	Р1	-	Рj	-	P k	-	Pn
c1	P1	x1	x11		x1j		x1 k		x1n
C2	P2	x2	x21		x2j		x2 k		x2n
-	-	-	-	-	-	-	-	-	-
Ci	Pi	xi	xi1		xi j		xi k		xi n
-	-	-	-	-	-	-	-	-	-
Cr	Pr	xr	xr1		xr j		xr k		xr n
-	-	-	-	-	-	-	-	-	-
Cm	Pm	xm	xm1		xm j		xm k		xm n
Zj			z1		z j		z k		z n
Zj - Cj			z1-c1		z j-C j		z k-C k		z n-C n

Симплекс-метод . Алгоритм перехода от одного допустимого плана к другому.

Данный алгоритм позволяет превратить неоптимальный план в оптимальный.

Алгоритм имеет следующие этапы:

I. Определятся вектор, который вводится в базис.

Это вектор, который имеет max. нарушение признака оптимальности.

Столбец, который соответствует вводимому в базис вектору, называется ключевым, его индекс обозначается буквой k .

В нашем примере k = 1

II. Определяется вектор, который выводится из базиса. Это тот вектор, у которого имеет место следующее соотношение.

для x_ik > 0

x_i – элементы вектора решений (столбца Р₀)

  x_ik – элементы ключевого столбца.

Строка, которая соответствует минимуму, т. е. выводимому из базиса вектору, называется ключевой строкой, её индекс обозначается буквой r. Элемент таблицы, который находится на пересечении k-ого столбца и r-той строки, называется генеральным элементом и обозначается x_rk.

III. Определяется новые значения элементов вектора решений.

Р^’₀ = P₀ - ΘP_k

х^’_i = x_i - Θxik

Для ключевой строки значение Р₀ = Θ, т.е. х^’r = q

IV. Определяется новое значение ключевой строки

x^’_{r j} =

V. Определяются новые значения всех остальных элементов симплекс-таблицы

x’_ij = x_ij -

Где  – элемент данного вектора в ключевой строке.

 – соответствующий элемент в ключевом столбце.

   – генеральный элемент.                              

  

	Базис	P0	8	7,5	7	0	0	0	0	0
Cj Ci			P1	P2	P3	P4	P5	P6	P7	P8
0	P4	1100	0	1	1	1	0	0	-1	0
0	P5	1190	0	1, 5	1, 7	0	1	0	-2, 1	0
0	P6	1440	0	0, 9	1, 3	0	0	1	-0, 8	0
8	P1	900	1	0	0	0	0	0	1	0
0	P8	1300	0	1	0	0	0	0	0	1
Zj			8	0	0	0	0	0	8	0
Zj - Cj			0	-7, 5	-7	0	0	0	8	0