Задача составления оптимального графика ремонта инструмента (стр. 3 из 5)

.

Для решения задачи симплекс-методом на каждой итерации заполняют симплекс-таблицу 2.2.

Таблица 2.2.

Последняя строка таблицы - индексная служит для определения направляющего столбца. Ее элементы ∆_j определяют по формуле (2.2.21). Очевидно, для всех базисных векторов {A_i} i=1,.,m оценки ∆_i=a_0i=0.

Значение целевой функции a₀₀ определяется из соотношения

.

В столбце B_x записываем базисные переменные {x_i} i= 1, ..., т. Их значения определяются столбиком свободных членов a_i0, то есть x_i = a_i0, i=1, 2,.,m.

Направляющие строка A_i и столбец A_j указываются стрелками. Если в качестве направляющего элемента выбран a_ij, то переход от данной симплекс таблицы к следующей определяется соотношениями (2.2.16) - (2.2.18).

Алгоритм решения задачи ЛП табличным симплексом-методом состоит из этапов.

1. Рассчитывают и заполняют начальную симплекс-таблицу с допустимым единичным базисом, включая индексную строку.

2. В качестве направляющего столбца выбирают A_j, для которого

.

3. Направляющая строка A_і выбирают из условия

4. Делают один шаг (итерацию) метода полного исключения Гаусса с направляющим элементом a_ij, для чего используют соотношения (2.2.16) - (2.2.18). В частности, элементы индексной строки новой таблицы вычисляют в соответствии с формулой

l=1,2, ..., n.

Правильность вычислений контролируют по формулам непосредственного счета:

(2.2.23)

(2.2.24)

В столбце B_x новой таблицы заменяют x_i на x_j, а в столбце С c_i на c_j.

5. Если все a_0l^(k+1)≥0, l=1,.,n, то новое базисное решение x_i= a_i0^(k+1), i € I_б^(k+1) - оптимально. В противном случае переходят к этапу 2 и выполняют очередную итерацию.

6. Второй, третий и четвертый этапы повторяют до тех пор, пока одна из итераций не закончится одним из двух исходов:

а) все a_0l ≥0. Это признак (критерий) оптимальности базисного решения последней симплекс-таблицы;

б) найдется такой a_0j=∆_j<0, что все элементы этого столбца a_rj≤0, (r = 1, ., m). Это признак неограниченности целевой функции z = ∑c_jx_j на множестве допустимых решений задачи.

3.2 Метод искусственных переменных

Пусть ограничения задачи ЛП имеют вид A_x≤A₀.

Если все b_i ≥ 0, i = 1, 2,..., m, то свободные векторы, образующие единичную подматрицу, составляют базис, а соответствующие им переменные - начальное базисное решение.

В общем случае, когда некоторые ограничения имеют знак «≥», например a_i1x₁ + a_i2x₂ +...+a_inx_n≥b_i , i=1,2,...., m,

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

a₁₁x₁ + a₁₂x₂ +…+ a_1nx_n - 1x_n+1 + 0x_n+2 +…+0x_n+m = b₁;

a₂₁x₁ + a₂₂x₂ +…+ a_2nx_n +0x_n+1-1x_n+2 +…+0x_n+m = b₂; (2.3.1)

. . . . . . . . . . . . . . . . . . . . . .

a_m1x₁ + a_m2x₂ +...+ a_mnx_n + 0x_n+1 + 0x_n+2 +...-1x_n+m = b_m.

Свободные переменные {x_n+1,…,x_n+m}в этом случае уже невозможно использовать в качестве начального базиса, так как x_n+1<0,...,x_n+m<0. Поэтому в уравнения (2.3.1) дополнительно вводят искусственные переменные x_n+m+1,…,x_n+m+k. Эти переменные не имеют ничего общего с реальной задачей, и потому их надо вывести из базиса как можно быстрее. Для этого перед началом итераций искусственным переменным в целевой функции приписывают для задач максимизации очень большие по модулю отрицательные коэффициенты (-М), где M>>c_i , (i = 1, 2, ..,m).

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

Знаки искусственных переменных x_n+m+1,...,x_n+m+kдолжны совпадать со знаками соответствующих свободных членов. Искусственные переменные образуют начальное базисное решение. Применив симплекс-метод, необходимо вывести из базиса все искусственные переменные. Если удается доказать (или показать), что искусственные переменные полностью вывести из базиса невозможно, то это означает, что задача не имеет решения, то есть ее ограничения противоречивы.

4. Проверка достоверности полученных результатов

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

· Значения элементов строки, содержащей ∆_j, вычисляются как элементы симплекс-таблицы (за исключением первой симплекс-таблицы, где такие вычисления невозможны).

· Значения элементов строки, содержащей ∆_j, вычисляются вторым способом, а именно по формулам непосредственного счета:

· Значения, полученные этими двумя способами, сравниваются. Если значения равны, значит вычисления проведены верно. В обратном случае, пользователю выдается сообщение об ошибке вычислений.

Дополнительным средством проверки достоверности является использование «Инженерного режима», реализованного в программе. В данном режиме можно посмотреть каждый этап вычисления задачи.

В программе также реализованы следующие методы обработки ошибок вычислений:

1. В случае если происходит «зацикливание» программы (в данной программе, если количество итераций больше 100), пользователю выдается сообщение об ошибке. Данная ситуация может возникнуть в случае вырожденности матрицы – вектор, который был ранее выведен из базиса, снова вводится в базис.

2. В случае если из базиса не удается вывести искусственные переменные, пользователю выдается сообщение об ошибке. Это означает, что ограничения задачи противоречивы и задача не имеет решения.

5. Алгоритм решения задачи

1. Проверка правильности ввода данных.

2. Построение симплекс-таблицы по введённым данным.

3. Добавление искусственных переменных.

4. Выбор направляющего элемента.

5. Деление направляющей строки на направляющий элемент.

6. Подсчет остальных элементов новой симплекс таблицы.

7. Если во время решения достоверность результатов нарушается, прекращаются дальнейшие вычисления, пользователю выдается информация об ошибке.

8. Если цикл расчета симплекс-таблиц не прекращается, принудительно прекращается процесс, пользователю выдается информация об ошибке.

9. Если из базисного решения не выведены все искусственные переменные, пользователю выдается информация об ошибке.

10. Если решение получено, результаты выводятся на экран.

6. Листинг программы, реализующий алгоритм задачи

const

m=25;

n=25;

type

TFirstKoef=array[1..m,1..n] of real; //начальная матрица коэфицентов

Simplex=array[1..m,1..n+m] of real; //новая матрица коэфицентов с искусственными переменными

FullSimplex=array[1..m+2,1..n+m+2] of real;

TE=array[1..n] of integer; //начальный неполный базис

TAddBas=array[1..m] of integer; //искусственные переменные вводимые для получения базиса

TFullBas=array[1..m+n] of integer; //полныйбазис

TTarFunc=array[1..60] of integer; //Целеваяфункция

var

Form1: TForm1;

Fkoef: TFirstKoef;

NumOfNewVars: integer;

fullBasis: TFullBas;

EngFull: FullSimplex;

F: File of Trec;

TarFunc: TTarFunc;

{------------------------------------------------------------------}

function Sort(E: TE): TE; //сортировка массива типа ТЕ

var

i,k,tmp,nn,p,q:integer;

begin

p:=strtoint(Form1.Edit1.Text);

q:=strtoint(Form1.Edit3.Text);

nn:=2*(Form1.TrackBar1.Position-1)+(Form1.TrackBar1.Position-2-p)+(Form1.TrackBar1.Position-2-q);

for k:=nn downto 2 do

for i:=1 to k-1 do

if E[i]>E[i+1] then

begin

tmp:=E[i];

E[i]:=E[i+1];

E[i+1]:=tmp;

end;

Sort:=E;

end;

{------------------------------------------------------------------}

function NullCheck(j: integer; Fkoef: TFirstKoef): boolean; //функцияпроверкистолбцовматрицынаналичиевозможныхбазисных (одна "1" остальные "0")

var

k,mm:integer;

Summ: real;

begin

Summ:=0;

mm:=2*(Form1.TrackBar1.Position-1);

for k:=1 to mm do

Summ := Summ + Fkoef[k,j];

if summ=1 then

NullCheck:=true

else

NullCheck:=false;

end;

{------------------------------------------------------------------}

functionAddVars(Basis: TE):TFullBas; //функция добавления столбцов с искусственными переменными

var

Base: TE;

newBase:TAddBas;

full:TFullBas;

j,k,count,inc,i,maxel,ncols,mm,nn,p,q: integer;

begin

p:=strtoint(Form1.Edit1.Text);

q:=strtoint(Form1.Edit3.Text);

mm:=2*(Form1.TrackBar1.Position-1);

nn:=1+2*(Form1.TrackBar1.Position-1)+(Form1.TrackBar1.Position-2-p)+(Form1.TrackBar1.Position-2-q);

for j:=1 to mm do

newBase[j]:=0;

NumOfNewVars:=0;

Base:=Sort(Basis);

count:=1;

//код ниже реализует поиск и добавление искусственных переменных в случае когда их требуется добавить в начало и середину единичной матрицы

for j:=2 to nn do

begin

k:=Base[j]-Base[j-1];

if (k<>0) and (k<>1) then

begin

inc:=1;

for i:=1 to k-1 do

begin

newBase[count]:=Base[j-1]+inc;