Составление первого опорного плава

Определить вектор =(x1,x2,...,xn), который удовлет-

воряет ограничениям вида

aij·xj ≤ bi i =

xj ≥ 0, j =

и обеспечивает максимальное значение целевой функции

F ()= cj·xj → max

Система ограничений задачи, решаемой симплексным методом, задана в виде системы неравенств смысла «≤», правые части которых b ≥ 0

Перейдем от системы неравенств к системе уравнений путем введения неотри­цательных дополнительных переменных.

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

где xn+1 — базисные переменные, i =

xj — свободные переменные, j = .

Решим эту систему относительно базисных переменных:

а функцию цели перепишем в виде уравнения

Полагая, что основные переменные х1=х2=x3=...хn=0 получим первый опорный план =(0,0,...0, b1,b2,...,bn), который заносим в симплексную таблицу.

По­следняя строка таблицы называется индексной и заполняется коэф­фициентами функции цели, взятыми с противоположным знаком.

с1

с2

...

сi

...

сm

cm+1

...

cj

...

cn

Базис

Сб

А0

A1

A2

...

A i

...

A m

A m +1

...

A j

...

A n

A1

с1

b1

...

...

a 1, m +1

...

a 1, j

...

a 1, n

A2

с2

b2

...

...

a 2, m +1

...

a 2, j

...

a 2, n

...

...

...

...

...

...

...

...

...

...

...

...

...

...

A i

сi

bi

...

...

ai , m +1

...

ai , j

...

ai , n

...

...

...

...

...

...

...

...

...

...

...

...

...

...

A m

сm

bm

...

...

am , m +1

...

am , j

...

am , n

Zj-cj

D0

...

...

D m+ 1

...

D j

...

D n

Проверка плана на оптимальность.

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

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