Багатокритеріальна задача лінійного програмування

Розв’язок багатокритеріальної задачі лінійного програмування з отриманням компромісного рішення (для задач з кількома функціями мети) за допомогою теоретико-ігрового підходу. Матриця мір неоптимальності та рядок функції мети. Модуль опису класу.

Рубрика Программирование, компьютеры и кибернетика
Вид курсовая работа
Язык русский
Дата добавления 15.05.2011
Размер файла 588,8 K

Отправить свою хорошую работу в базу знаний просто. Используйте форму, расположенную ниже

Студенты, аспиранты, молодые ученые, использующие базу знаний в своей учебе и работе, будут вам очень благодарны.

Begin

Self. CurHeadCol[CurRow].ElmType:=bc_IndependentVar;

Self. CurHeadCol[CurRow].VarInitInRow:=True;

{Формуємо назву змінної двоїстої задачі

(залежно від назви функції мети поданої задачі):}

If Pos (sc_DualDestFuncHdr,

Self. CurHeadCol [Length(Self. CurHeadCol) - 1].AsVarName)>0 then

Self. CurHeadCol[CurRow].AsVarName:=sc_XVarName+IntToStr (CurRow+1)

Else Self. CurHeadCol[CurRow].AsVarName:=sc_DualTaskVarNameStart+

IntToStr (CurRow+1);

End;

End {Якщо заголовок рядка функції мети:}

Else if Self. CurHeadCol[CurRow].ElmType=OldDFuncType then

Begin

Self. CurHeadCol[CurRow].ElmType:=bc_Number;

Self. CurHeadCol[CurRow].AsNumber:=1; {буде множник стовпця вільних членів}

End;

End;

{Міняємо рядок і стовпець-заголовки таблиці місцями:}

SafeMas:=Self. CurHeadRow;

Self. CurHeadRow:=Self. CurHeadCol;

Self. CurHeadCol:=SafeMas;

{У новому стовпці-заголовку шукаємо комірки-заголовки нерівностей «>=».

Їх заміняємо на «<=» множенням рядка на -1:}

For CurRow:=0 to Length (Self. CurHeadCol) - 1 do

Begin

If Self. CurHeadCol[CurRow].ElmType=bc_FuncVal then

Begin

If ValSign (Self. CurHeadCol[CurRow])=bc_Negative then

Self. ChangeSignsInRow(CurRow);

End;

End;

{У новому рядку-заголовку шукаємо комірки-заголовки залежних змінних,

які мають умову «<=0». Змінюємо цю умову на «>=0» множенням стовпця на -1:}

For CurCol:=0 to Length (Self. CurHeadRow) - 1 do

Begin

If Self. CurHeadRow[CurCol].ElmType=bc_DependentVar then

Begin

If ValSign (Self. CurHeadRow[CurCol])=bc_Negative then

Self. ChangeSignsInCol(CurCol);

End;

End;

{Відображаємо отриману таблицю у екранній таблиці:}

Self. WriteTableToGrid (Self.CHeadColNum, Self.CHeadRowNum);

MakeDualLTask:=True;

End;

Function TGridFormattingProcs. PrepareToSolveEqsWithM1: Boolean;

Const sc_CurProcName='PrepareToSolveEqsWithM1';

Var CurRow, ColToDel: Integer;

Begin

If (Self. CurFormatState=fs_EnteringEqs) or

(Self. CurFormatState=fs_NoFormatting) then

Begin

{Якщо таблиця не зчитана, то читаємо:}

If (Self. CurGridModified) and (Self. CurFormatState=fs_EnteringEqs) then

Begin

If Not (Self. GetTask) then

Begin

PrepareToSolveEqsWithM1:=False; Exit;

End;

End;

If Self. TaskHeight<=0 then {Якщо таблиця пуста:}

Begin

If Self. CurOutConsole<>Nil then

Self. CurOutConsole. Lines. Add (sc_CurProcName+sc_EmptyTable);

PrepareToSolveEqsWithM1:=False;

Exit;

End;

If Not (Self. EqM1TaskPrepared) then

Begin

{Копіюємо стовпець вільних членів (правих частин рівнянь) із

останнього стовпця таблиці до стовпця-заголовка:}

For CurRow:=0 to Length (Self. CurHeadCol) - 1 do

Begin

Self. CurHeadCol[CurRow].ElmType:=bc_Number;

Self. CurHeadCol[CurRow].AsNumber:=

Self. CurTable [CurRow, Length (CurTable[CurRow]) - 1];

End;

{Видаляємо цей останній стовпець із таблиці:}

ColToDel:=Length (Self. CurTable[0]) - 1;

DelColsFromMatr (Self. CurTable, ColToDel, 1);

DeleteFromArr (Self. CurHeadRow, ColToDel, 1);

End;

{Позиціювання відображення таблиці у даному режимі вирішування:}

Self.CHeadColNum:=CurGrid. FixedCols;

Self.CHeadRowNum:=CurGrid. FixedRows-1;

{Відображаємо таблицю, що підготована для розв'язування:}

Self. WriteTableToGrid (Self.CHeadColNum, Self.CHeadRowNum);

{Якщо таблиця пуста після перенесення останнього стовпця у

стовпець-заголовок:}

If Self. TaskHeight<=0 then

Begin

PrepareToSolveEqsWithM1:=False;

Exit;

End;

Self. EqM1TaskPrepared:=True;

PrepareToSolveEqsWithM1:=True;

End

Else

Begin

If Self. CurOutConsole<>Nil then

Self. CurOutConsole. Lines. Add (sc_CurProcName+sc_WrongEditMode);

PrepareToSolveEqsWithM1:=False;

End;

End;

Function TGridFormattingProcs. PrepareToSolveEqsWithM2: Boolean;

Const sc_CurProcName='PrepareToSolveEqsWithM2';

Var CurRow: Integer;

Begin

If (Self. CurFormatState=fs_EnteringEqs) or

(Self. CurFormatState=fs_NoFormatting) then

Begin {Якщо таблиця не зчитана, то читаємо:}

If (Self. CurGridModified) and (Self. CurFormatState=fs_EnteringEqs) then

Begin

If Not (Self. GetTask) then

Begin

PrepareToSolveEqsWithM2:=False; Exit;

End;

End;

If Self. TaskHeight<=0 then {Якщо таблиця пуста:}

Begin

If Self. CurOutConsole<>Nil then

Self. CurOutConsole. Lines. Add (sc_CurProcName+sc_TableIsNotReady);

PrepareToSolveEqsWithM2:=False; Exit;

End;

If Not (Self. EqM2TaskPrepared) then

Begin

For CurRow:=0 to Length (Self. CurHeadCol) - 1 do

Begin

{Заповнюємо стовпець-заголовок нулями:}

Self. CurHeadCol[CurRow].ElmType:=bc_Number;

Self. CurHeadCol[CurRow].AsNumber:=0;

{Змінюємо знаки у останньому стовпці таблиці - стовпці вільних

членів. Так як вони у правих частинах рівнянь, то знаходячись у

таблиці коефіцієнтів лівих частин, повинні бути з протилежними

знаками:}

Self. CurTable [CurRow, Length (CurTable[CurRow]) - 1]:=

- Self. CurTable [CurRow, Length (CurTable[CurRow]) - 1];

End;

End;

{Позиціювання відображення таблиці у даному режимі вирішування:}

Self.CHeadColNum:=CurGrid. FixedCols;

Self.CHeadRowNum:=CurGrid. FixedRows-1;

{Відображаємо таюдицю, що підготована для розв'язування:}

Self. WriteTableToGrid (Self.CHeadColNum, Self.CHeadRowNum);

Self. EqM2TaskPrepared:=True;

PrepareToSolveEqsWithM2:=True;

End

Else

Begin

If Self. CurOutConsole<>Nil then

Self. CurOutConsole. Lines. Add (sc_CurProcName+sc_WrongEditMode);

PrepareToSolveEqsWithM2:=False;

End;

End;

{TTableFormatState=(fs_EnteringEqs, fs_EnteringLTask, fs_SolvingEqsM1,

fs_SolvingEqsM2, fs_SolvingLTask,

fs_NoFormatting, fs_FreeEdit);}

Function TGridFormattingProcs. PrepareToSolveLTask: Boolean;

Const sc_CurProcName='PrepareToSolveLTask';

Begin

If (Self. CurFormatState=fs_EnteringLTask) or

(Self. CurFormatState=fs_NoFormatting) then

Begin {Якщо таблиця у режимі редагування задачі, і модифікована, то зчитуємо:}

If (Self. CurGridModified) and (Self. CurFormatState=fs_EnteringLTask) then

Begin

If Not (Self. GetTask) then {зчитуємо таблицю (умову) з екранної таблиці}

Begin

PrepareToSolveLTask:=False; Exit;

End;

End;

If Self. TaskHeight<=0 then {Якщо таблиця пуста:}

Begin

If Self. CurOutConsole<>Nil then

Self. CurOutConsole. Lines. Add (sc_CurProcName+sc_TableIsNotReady);

PrepareToSolveLTask:=False; Exit;

End;

If Not (Self.LTaskPrepared) then {якщо ця підготовка ще не виконувалася:}

Begin

{Зсуваємо рядки цільових функцій вниз. При цьому позначки порядку

рядків залишаємо на тих самих місцях (і присвоюємо тим рядкам, які

стають на ці місця):}

Self. ShiftRowsDown([bc_DestFuncToMax, bc_DestFuncToMin], True);

{Позиціювання відображення таблиці у даному режимі вирішування:}

Self.CHeadColNum:=CurGrid. FixedCols;

Self.CHeadRowNum:=CurGrid. FixedRows-1;

{Відображаємо таблицю, що підготована для розв'язування:}

Self. WriteTableToGrid (Self.CHeadColNum, Self.CHeadRowNum);

Self.LTaskPrepared:=True;

End;

PrepareToSolveLTask:=True;

End

Else

Begin

If Self. CurOutConsole<>Nil then

Self. CurOutConsole. Lines. Add (sc_CurProcName+sc_WrongEditMode);

PrepareToSolveLTask:=False;

End;

End;

Function TGridFormattingProcs. PrepareDFuncForSimplexMaximize: Boolean;

Var ToMax: Boolean; Row, Col, CurWidth, DFuncRowNum: Integer;

Const sc_CurProcName='PrepareDFuncForSimplexMaximize';

Begin

CurWidth:=Length (Self. CurHeadRow);

DFuncRowNum:=Length (Self. CurHeadCol) - 1;

Case Self. CurHeadCol[DFuncRowNum].ElmType of {перевіряємо тип функції мети:}

bc_DestFuncToMax: ToMax:=True;

bc_DestFuncToMin: ToMax:=False;

Else {якщо заданий рядок виявився не функцією мети:}

Begin

If Self. CurOutConsole<>Nil then

Self. CurOutConsole. Lines. Add (sc_CurProcName+

sc_CurRowNotMarkedAsDestFunc+IntToStr (DFuncRowNum+1));

PrepareDFuncForSimplexMaximize:=False; Exit;

End;

End;

{Готуємо умову для вирішування симплекс-методом максимізації:}

{Міняємо знаки у елементів рядка-заголовка, окрім знака останньої

комірки - то множник для стовпця правих частин. Це є

інтерпретацією перенесення усіх доданків у праву частину, і

форматом для виконання модифікованих Жорданових виключень:}

For Col:=0 to CurWidth-2 do

ChangeSignForValOrVarName (Self. CurHeadRow[Col]);

{Якщо треба шукати максимум, то множимо коефіцієнти функції мети

на -1 (окрім вільгого члена), бо помножили і усі x1xn на -1.

Якщо треба мінімум, то ці коефіцієнти не множимо

(бо x1xn вже помножені), але множимо вільний член функції. Тоді

отримаємо протилежну функцію, щоб знайти її максимум

(це протилежний мінімум заданої функції):}

Row:=Length (Self. CurHeadCol) - 1; {рядок функції мети}

If ToMax then

Begin

For Col:=0 to CurWidth-2 do {коефіцієнти функції мети міняють знаки:}

Self. CurTable [Row, Col]:=-Self. CurTable [Row, Col];

End

Else {Якщо треба знайти мінімум:}

Begin {Множимо вільний член функції мети на -1:}

Self. CurTable [Row, CurWidth-1]:=-Self. CurTable [Row, CurWidth-1];

{Назва функції теж міняє знак:}

ChangeSignForValOrVarName (Self. CurHeadCol[Row]);

{Тепер це протилежна функція для максимізації:}

Self. CurHeadCol[Row].ElmType:=bc_DestFuncToMax;

End;

PrepareDFuncForSimplexMaximize:=True;

End;

Function TGridFormattingProcs. PrepareDestFuncInMultiDFuncLTask (

SFuncRowNum, MinDestFuncRowNum: Integer):Boolean;

{Готує таблицю для розв'язування задачі ЛП відносно одної заданої функції

мети із багатокритеріальної задачі.

Вхідні дані:

SFuncRowNum - номер рядка у таблиці Self. CopyTable (і комірки у

стовпці-заголовку Self. CopyHeadCol), в якому записана портібна

функція мети;

DestFuncMinRowNum - номер найвищого (з найменшим номером) рядка

функції мети. Усі функції мети мають бути зібрані внизу таблиці;

Self. CopyTable - таблиця коефіцієнтів та вільних членів;

Self. CopyHeadRow - рядок-заголовок зі змінними та одиницею-множником

стовпця вільних членів (має бути останнім);

Self. CopyHeadCol - стовпець-заголовок з іменами функцій-нерівностей,

нулями (заголовки рядків-рівнянь), іменами функцій мети

(що максимізуються (тип комірки bc_DestFuncToMax) або мінімізуються

(тип bc_DestFuncToMin)).

Вихідні дані:

Умова для одної функції:

Self. CurTable - таблиця коефіцієнтів та вільних членів з одною

функцією мети в останньому рядку, для максимізації симплекс-методом;

Self. CurHeadRow - рядок-заголовок;

Self. CurHeadCol - стовпець-заголовок з іменами функцій-нерівностей,

нулями (заголовки рядків-рівнянь), і одною коміркою функції мети

(остання, найнижча комірка), яку треба максимізувати. Якщо у цій

комірці перед назвою функції стоїть знак «-», то після максимізації

її треба замінити на протилежну функцію (і отримати мінімізацію

тої функції, яка була задана в умові).

Підпрограма повертає ознаку успішності підготовки умови із одною

заданою функцією мети.}

Var Row, Col, CurWidth, CurHeight: Integer;

Const sc_CurProcName='PrepareDestFuncInMultiDFuncLTask';

Label LStopLabel;

Begin

If Not (Self. GoToEnd) then

Begin {Демонструємо функцію мети у таблиці, з якою будемо працювати:}

{Таблиця багатокритеріальної задачі для відображення:}

Self. CurHeadRow:=Self. CopyHeadRow; Self. CurHeadCol:=Self. CopyHeadCol;

Self. CurTable:=Self. CopyTable;

{Координати рядка функції для помітки його кольором:}

Self. CurGridSolveCol:=Self.CHeadColNum;

Self. CurGridSolveRow:=SFuncRowNum+Self.CHeadRowNum+bc_LTaskRowsBeforeVars;

{Відображаємо і чекаємо реакції користувача:}

WaitForNewStep (Self.CHeadColNum, Self.CHeadRowNum);

If Self. Stop then Goto LStopLabel;

End;

CurWidth:=Length (Self. CopyHeadRow);

CurHeight:=Length (Self. CopyHeadCol);

If (SFuncRowNum<0) or (MinDestFuncRowNum<0) or

(SFuncRowNum>=CurHeight) or (MinDestFuncRowNum>=CurHeight) then

Begin

If Self. CurOutConsole<>Nil then

Self. CurOutConsole. Lines. Add (sc_CurProcName+sc_RowNumsIsOutOfTable);

PrepareDestFuncInMultiDFuncLTask:=False; Exit;

End;

{Формуємо умову однокритеріальної задачі лінійного програмування із

копії умови багатокритеріальної задачі:}

{Копіюємо заголовки і таблицю коефіцієнтів:}

SetLength (Self. CurHeadRow, CurWidth); {довжина для рядка заголовка така сама}

For Col:=0 to CurWidth-1 do Self. CurHeadRow[Col]:=Self. CopyHeadRow[Col];

{Стовпець-заголовок і висота таблиці мають усі рядки умов (рівнянь

та нерівностей) і один рядок функції мети:}

SetLength (Self. CurHeadCol, MinDestFuncRowNum+1);

SetLength (Self. CurTable, MinDestFuncRowNum+1, CurWidth);

For Row:=0 to MinDestFuncRowNum-1 do {копіюємо рядки умов:}

Begin

Self. CurHeadCol[Row]:=Self. CopyHeadCol[Row];

For Col:=0 to CurWidth-1 do

Self. CurTable [Row, Col]:=Self. CopyTable [Row, Col];

End;

{В останній рядок таблиці однокритеріальної задачі копіюємо заданий

рядок функції мети із багатокритеріальної задачі:}

Row:=MinDestFuncRowNum; {номер останнього рядка у однокритеріальній задачі}

Self. CurHeadCol[Row]:=Self. CopyHeadCol[SFuncRowNum];

For Col:=0 to CurWidth-1 do

Self. CurTable [Row, Col]:=Self. CopyTable [SFuncRowNum, Col];

PrepareDestFuncInMultiDFuncLTask:=Self. PrepareDFuncForSimplexMaximize;

Exit;

LStopLabel:

PrepareDestFuncInMultiDFuncLTask:=False; Exit;

End;

Procedure TGridFormattingProcs. ShowLTaskResultCalc (DualTaskVals: Boolean);

{Процедура зчитує значення функції мети у таблиці розв'язаної

однокритеріальної задачі, і значення усіх змінних або функцій в цьому

розв'язку. Відображає значення цих змінних, функцій-нерівностей, і

функції мети в Self. CurOutConsole.

Вхідні дані:

DualTaskVals - вмикач режиму відображення значень двоїстої задачі:

читаються значення змінних і функцій двоїстої задачі. Їхні

значення розміщені не на місці стовпця вільних членів, а у рядку

коефіцієнтів функції мети (функції мети прямої задачі). Вони є

значеннями змінних чи функцій, імена яких у рядку-заголовку.

Змінні чи функції-нерівності двоїстої задачі з іменами у

стовпці-заголовку є рівними нулю.

Таблиця розв'язаної однокритеріальної (з одною функцією мети) задачі:

Self. CurTable - таблиця коефіцієнтів та вільних членів;

Self. CurHeadRow - рядок-заголовок з іменами змінних, іменами

функцій-нерівностей (що перейшли в рядок-заголовок) та

одиницею-множником стовпця вільних членів (має бути останнім);

Self. CurHeadCol - стовпець-заголовок з іменами функцій-нерівностей,

іменами змінних (виключених), іменем функції мети.}

Const DestFuncsTypes=[bc_DestFuncToMax, bc_DestFuncToMin];

Var st1: String; CurColNum, CurRowNum, LastColNum, LastRowNum: Integer;

Begin

If Self. CurOutConsole<>Nil then

Begin

LastColNum:=Length (Self. CurHeadRow) - 1;

LastRowNum:=Length (Self. CurHeadCol) - 1;

st1:=sc_ResultIs;

If DualTaskVals then

st1:=st1+sc_ForDualTask

Else st1:=st1+sc_ForDirectTask;

Self. CurOutConsole. Lines. Add(st1);

Self. CurOutConsole. Lines. Add (sc_InHeadRow);

{Показуємо значення змінних (або функцій) у рядку-заголовку:}

For CurColNum:=0 to LastColNum-1 do

Begin

st1:='';

If Self. CurHeadRow[CurColNum].ElmType=bc_Number then

st1:=st1+FloatToStr (Self. CurHeadRow[CurColNum].AsNumber)

Else st1:=st1+Self. CurHeadRow[CurColNum].AsVarName;

st1:=st1 + sc_Space+sc_Equal+sc_Space;

{Усі змінні прямої задачі (або функції) у рядку-заголовку в точці

задачі рівні нулю, а змінні двоїстої - у рядку коефіцієнтів функції

мети:}

If DualTaskVals then

st1:=st1+ FloatToStr (Self. CurTable [LastRowNum, CurColNum])

Else st1:=st1+'0';

st1:=st1+sc_KrKm;

Self. CurOutConsole. Lines. Add(st1);

End;

Self. CurOutConsole. Lines. Add (sc_InHeadCol);

For CurRowNum:=0 to LastRowNum do

Begin

st1:='';

If Self. CurHeadCol[CurRowNum].ElmType=bc_Number then

st1:=st1+FloatToStr (Self. CurHeadCol[CurRowNum].AsNumber)

Else st1:=st1+Self. CurHeadCol[CurRowNum].AsVarName;

st1:=st1 + sc_Space+sc_Equal+sc_Space;

{Усі змінні прямої задачі (або функції) у стовпці-заголовку в точці

задачі мають свої значення у стовпці вільних членів,

а змінні двоїстої - рівні нулю:}

If (Self. CurHeadCol[CurRowNum].ElmType in DestFuncsTypes) or

Not(DualTaskVals) then

st1:=st1+ FloatToStr (Self. CurTable [CurRowNum, LastColNum])

Else st1:=st1+'0';

If (Self. CurHeadCol[CurRowNum].ElmType in DestFuncsTypes) then

st1:=sc_ResFunc+sc_Space+st1;

If CurRowNum=LastRowNum then st1:=st1+sc_Spot

Else st1:=st1+sc_KrKm;

Self. CurOutConsole. Lines. Add(st1);

End;

End;

End;

Procedure TGridFormattingProcs. ReadCurFuncSolution (Var SDValVecs:TFloatMatrix;

Var SDDestFuncVals:TFloatArr; SVecRow: Integer;

ToReadFuncVals: Boolean; DualTaskVals: Boolean);

{Процедура зчитує значення функції мети у таблиці розв'язаної

однокритеріальної задачі, і значення усіх змінних або функцій в цьому

розв'язку.

Вхідні дані:

SVecRow - номер поточної функції мети (нумерація з нуля) у масивах

SDValVecs і SDDestFuncVals;

ToReadFuncVals - перемикач: якщо рівний False, то зчитуються значення

змінних (і значення функції мети); True - зчитуються значення

функцій-нерівностей (і значення функції мети);

DualTaskVals - вмикач режиму читання змінних двоїстої задачі:

читаються значення змінних і функцій двоїстої задачі. Їхні

значення розміщені не на місці стовпця вільних членів, а у рядку

коефіцієнтів функції мети (функції мети прямої задачі). Вони є

значеннями змінних чи функцій, імена яких у рядку-заголовку.

Змінні чи функції-нерівності двоїстої задачі з іменами у

стовпці-заголовку є рівними нулю.

Таблиця розв'язаної однокритеріальної (з одною функцією мети) задачі:

Self. CurTable - таблиця коефіцієнтів та вільних членів;

Self. CurHeadRow - рядок-заголовок з іменами змінних, іменами

функцій-нерівностей (що перейшли в рядок-заголовок) та

одиницею-множником стовпця вільних членів (має бути останнім);

Self. CurHeadCol - стовпець-заголовок з іменами функцій-нерівностей,

іменами змінних (виключених), іменем функції мети. Функція мети

має бути в останньому рядку, і бути одна;

SDValVecs - масив для запису векторів значень змінних;

SDDestFuncVals - масив для запису значень функцій мети

(для цих двох останніх масивів пам'ять має бути вже виділеною).

Вихідні дані:

SDValVecs - масив векторів значень змінних із заповненим вектором

номер SVecRow. Змінні, яких немає в таблиці розв'язку, вважаються

такими що можуть мати будь-яке значення, і приймаються рівними нулю;

SDDestFuncVals - масив значень функцій мети з поточни значенням

у комірці номер SVecRow.}

Var CurColNum, CurRowNum, LastColNum, LastRowNum: Integer;

WorkCellTypes:THeadLineElmTypes;

Begin

{Ініціюємо нулями поточний вектор значень.

Змінні чи функції, імена яких у рядку-заголовку, рівні нулю

для прямої задачі (для двоїстої - у стовпці-заголовку).

Змінні і функції, яких немає в таблиці, теж вважаємо рівними нулю:}

For CurColNum:=0 to Length (SDValVecs[SVecRow]) - 1 do

SDValVecs [SVecRow, CurColNum]:=0;

{Читаємо стовпець-заголовок і значення із останнього стовпця таблиці:}

LastColNum:=Length (Self. CurHeadRow) - 1;

LastRowNum:=Length (Self. CurHeadCol) - 1;

{Значення функції мети:}

SDDestFuncVals[SVecRow]:=Self. CurTable [LastRowNum, LastColNum];

{Функції-нерівності прямої задачі відповідають змінним двоїстої задачі

за позиціюванням в заголовках (не за значеннями, значення різні!),

змінні прямої - функціям двоїстої:}

If (ToReadFuncVals) xor (DualTaskVals) then

WorkCellTypes:=[bc_FuncVal]

Else WorkCellTypes:=[bc_IndependentVar, bc_DependentVar];

{Читаємо змінні або функції-нерівності (в залежності від того, що

задано прочитати):}

If DualTaskVals then

Begin

For CurColNum:=0 to LastColNum-1 do {усі стовпці крім стовпця вільних членів}

Begin {значення записуємо у заданий вектор (SVecRow):}

If (Self. CurHeadRow[CurColNum].ElmType in WorkCellTypes) then

SDValVecs [SVecRow, Self. CurHeadRow[CurColNum].VarInitPos]:=

Self. CurTable [LastRowNum, CurColNum];

End

End

Else

Begin

For CurRowNum:=0 to LastRowNum-1 do {усі рядки крім рядка функції мети}

Begin {значення записуємо у заданий вектор (SVecRow):}

If (Self. CurHeadCol[CurRowNum].ElmType in WorkCellTypes) then

SDValVecs [SVecRow, Self. CurHeadCol[CurRowNum].VarInitPos]:=

Self. CurTable [CurRowNum, LastColNum];

End

End;

End;

Procedure TGridFormattingProcs. BuildPaymentTaskOfOptim (

Const SOptimXVecs:TFloatMatrix; Const SOptimFuncVals:TFloatArr;

SFirstDFuncRow: Integer);

{Будує однокритеріальну задачу максимізації для пошуку вагових

коефіцієнтів і компромісного вектора значень змінних для

усіх заданих функцій мети.

Вхідні дані:

SOptimXVecs - масив векторів оптимальних значень змінних для

кожної з фунуцій мети;

SOptimFuncVals - масив оптимальних значень функцій мети;

SFirstDFuncRow - номер першої (найвищої) функції мети

у Self. CopyTable і Self. CopyHeadCol;

Self. CopyTable - матриця коефіцієнтів умови багатокритеріальної задачі;

Вихідні дані:

Однокритеріальна задача ЛП для максимізації:

Self. CurTable - матриця коефіцієнтів оптимальності,

вільних членів і коефіцієнтів функції мети;

Self. CurHeadCol - імена змінних двоїстої задачі (як

функції-нерівності прямої задачі);

Self. CurHeadRow - імена функцій-нерівностей двоїстої задачі

(як залежні (тільки більше нуля) змінні прямої задачі).}

Var jCol, iRow, FuncCount, FuncRow: Integer; MinQ, CurQ:TWorkFloat;

Const sc_CurProcName='BuildPaymentTaskOfOptim';

Function CalcQ (ZjFuncRow: Integer; Const XiVals:TFloatArr;

Const ZjXj:TWorkFloat):TWorkFloat;

{Підраховує міру неоптимальності.

Вхідні дані:

ZjFuncRow - номер рядка j-ої функції мети у таблиці Self. CopyTable;

Self. CopyTable - таблиця коефіцієнтів умови багатокритеріальної

задачі ЛП;

XiVals - оптимальні значення змінних для i-ої функції мети

(для формування iо рядка матриці неоптимальності);

ZjXj - значення jї функції мети за jо набору оптимальних

значень змінних (тобто оптимальне значення цієї функції). Для

формування jо стовпця матриці неоптимальності.

Вихідні дані: міра неоптимальності.}

Var VarNum: Integer; ZjXi:TWorkFloat;

Begin

ZjXi:=0;

{Шукаємо суму добутків значень змінних і коефіцієнтів при них -

значення функції у точці, координатами якої є подані значення змінних:}

For VarNum:=0 to Length(XiVals) - 1 do

ZjXi:=ZjXi + Self. CopyTable [ZjFuncRow, VarNum]*XiVals[VarNum];

CalcQ:=-Abs((ZjXi/ZjXj) - 1); {qij=-|(ZjXi-ZjXj)/(ZjXj)|}

End;

{Заповнення імен змінних - імен фукнцій двоїстої задачі у рядку-заголовку:}

Procedure FillHRowVarName (SCol: Integer);

Begin

Self. CurHeadRow[SCol].VarInitPos:=SCol;

Self. CurHeadRow[SCol].VarInitInRow:=True;

Self. CurHeadRow[SCol].ElmType:=bc_DependentVar;

Self. CurHeadRow[SCol].AsVarName:=sc_Minus+sc_DualTaskFuncNameStart+

IntToStr (SCol+1);

End;

{Заповнення у комірки рядка-заголовка числом:}

Procedure FillHRowWithNum (SCol: Integer; Const SNumber:TWorkFloat);

Begin

Self. CurHeadRow[SCol].VarInitPos:=SCol;

Self. CurHeadRow[SCol].VarInitInRow:=True;

Self. CurHeadRow[SCol].ElmType:=bc_Number;

Self. CurHeadRow[SCol].AsNumber:=SNumber;

End;

{Заповнення імен функцій - імен змінних двоїстої задачі у стовпці-заголовку:}

Procedure FillHColFuncName (SRow: Integer);

Begin

Self. CurHeadCol[SRow].VarInitPos:=SRow;

Self. CurHeadCol[SRow].VarInitInRow:=False;

Self. CurHeadCol[SRow].ElmType:=bc_FuncVal;

Self. CurHeadCol[SRow].AsVarName:=sc_Minus+sc_DualTaskVarNameStart+

IntToStr (SRow+1);

End;

{Заповнення імені функції мети:}

Procedure FillHColDFuncName (SRow: Integer);

Begin

Self. CurHeadCol[SRow].VarInitPos:=SRow;

Self. CurHeadCol[SRow].VarInitInRow:=False;

Self. CurHeadCol[SRow].ElmType:=bc_DestFuncToMax;

Self. CurHeadCol[SRow].AsVarName:=sc_DestFuncHdr;

End;

Label LStopLabel;

Begin

FuncCount:=Length(SOptimFuncVals);

If Self. CurOutConsole<>Nil then

Self. CurOutConsole. Lines. Add (sc_CurProcName+sc_CalculatingNoOptMeasures);

{Таблиця мір неоптимальності квадратна: кількість стовпців рівна

кількості функцій мети; кількість рядків рівна кількості оптимальних

векторів значень змінних для кожної з цих функцій (тобто тій же самій

кількості). Додатково виділимо один стовпець для вільних членів

і один рядок для коефіцієнтів функції мети задачі-інтерпретації

гри двох гравців з нульовою сумою, що буде сформована далі:}

SetLength (Self. CurTable, FuncCount + 1, FuncCount + 1);

{Відповідну довжину задаємо і заголовкам таблиці:}

SetLength (Self. CurHeadCol, FuncCount + 1);

SetLength (Self. CurHeadRow, FuncCount + 1);

{Підраховуємо міри неоптимальності векторів значень змінних для

кожної функції мети, і записуємо їх у таблицю коефіцієнтів -

формуємо матрицю неоптимальності:}

{Шукаємо мінімальну (найбільшу за модулем) міру неоптимальності.

Спочатку за неї беремо міру у верхньому лівому куті матриці:}

MinQ:=CalcQ (SFirstDFuncRow, SOptimXVecs[0], SOptimFuncVals[0]);

Self. CurTable [0, 0]:=MinQ; {записуємо одразу цю міру в матрицю}

For jCol:=0 to FuncCount-1 do

Begin

FuncRow:=SFirstDFuncRow+jCol;

{Комірка [0, 0] вже порахована, її обходимо. Для всіх інших виконуємо:}

For iRow:=Ord (jCol=0) to FuncCount-1 do {Ord (0=0)=1; Ord (<не нуль>=0)=0}

Begin {Підраховуємо міру неоптимальності:}

CurQ:=CalcQ (FuncRow, SOptimXVecs[iRow], SOptimFuncVals[jCol]);

If MinQ>CurQ then MinQ:=CurQ; {шукаємо найбільшу за модулем міру}

Self. CurTable [iRow, jCol]:=CurQ; аписуємо міру в матрицю неоптимальності}

End;

End;

MinQ:=-MinQ; {найбільше абсолютне значення (модуль) усіх мір в матриці}

{Заповнюємо заголовки таблиці (це будуть заголовки задачі ЛП):}

For jCol:=0 to FuncCount-1 do FillHRowVarName(jCol);

For iRow:=0 to FuncCount-1 do FillHColFuncName(iRow);

FillHRowWithNum (FuncCount, 1);

FillHColDFuncName(FuncCount);

{Коефіцієнти функції мети: усі однакові і рівні одиниці (бо

відхилення чи наближення будь-якої з цільових функцій від свого

оптимального значення пропорційно (у відсотках) має однакову ціну):}

For jCol:=0 to FuncCount-1 do Self. CurTable [FuncCount, jCol]:=1;

{Вільні члени: усі рівні одиниці:}

For iRow:=0 to FuncCount-1 do Self. CurTable [iRow, FuncCount]:=1;

{Комірка значення функції мети:}

Self. CurTable [FuncCount, FuncCount]:=0;

{Ховаємо розв'язувальну комірку у екранній таблиці:}

Self. CurGridSolveCol:=0; Self. CurGridSolveRow:=0;

WaitForNewStep (Self.CHeadColNum, Self.CHeadRowNum); {показуємо матрицю}

If Self. Stop then Goto LStopLabel;

{Якщо MinQ=0, то усі міри рівні нулю (бо MinQ тут насправді є

максимальним абсолютним значенням). Якщо кількість функцій мети

багатокритеріальної задачі рівна одній (тобто задача однокритеріальна),

то і міра є лише одна, і для неї MinQ=-q [0,0], тому при додаванні

q [0,0]+MinQ=q [0,0] - q [0,0]=0.

Щоб в обох цих випадках розв'язування симплекс-методом працювало

коректно, замінимо MinQ на інше число:}

If MinQ=0 then

Begin

If Self. CurOutConsole<>Nil then

Self. CurOutConsole. Lines. Add (sc_CurProcName+sc_AllMeasurIsZero);

MinQ:=1 {одиниця, якщо всі нулі (отримаємо матрицю із одиниць)}

End

Else if Length(SOptimFuncVals)=1 then {якщо всього одна функція мети:}

Begin

If Self. CurOutConsole<>Nil then

Self. CurOutConsole. Lines. Add (sc_CurProcName+sc_UniqueMeasureCantSetZero);

MinQ:=MinQ+1; {збільшимо на 1 - отримаємо матрицю з одною одиницею.}

End;

{Додаємо до усіх мір неоптимальності максимальну за модулем, і

отримуємо матрицю коефіцієнтів, до якої можна застосувати

симплекс-метод:}

For iRow:=0 to FuncCount-1 do

For jCol:=0 to FuncCount-1 do

Self. CurTable [iRow, jCol]:=Self. CurTable [iRow, jCol]+MinQ;

LStopLabel:

End;

Procedure TGridFormattingProcs. CalcComprVec (Const SVarVecs:TFloatMatrix;

Const SWeightCoefs:TFloatArr; Var DComprVec:TFloatArr);

{Обчислює компромісний вектор (масив) значень змінних із

із заданих векторів значень і вагових коефіцієнтів для кожного із

цих векторів.

Вхідні дані:

SVarVecs - вектори значень змінних;

SWeightCoefs - вагові коефіцієнти для кожного вектора.

Вихідні дані:

DComprVec - компромісний вектор значень змінних.}

Var VecNum, VarNum: Integer; CurComprVal:TWorkFloat;

Begin

DComprVec:=Nil;

If Length(SVarVecs)<=0 then Exit;

SetLength (DComprVec, Length (SVarVecs[0]));

For VarNum:=0 to Length(DComprVec) - 1 do {для кожної змінної:}

Begin

CurComprVal:=0;

{Множимо значення змінної з кожного вектора на свій ваговий

коефіцієнт, і знаходимо суму:}

For VecNum:=0 to Length(SVarVecs) - 1 do

CurComprVal:=CurComprVal + SVarVecs [VecNum, VarNum]*SWeightCoefs[VecNum];

DComprVec[VarNum]:=CurComprVal;

End;

End;

Function TGridFormattingProcs. CalcDFuncVal (Const SVarVec:TFloatArr;

SDestFuncRowNum: Integer):TWorkFloat;

{Обчислює значення функції мети за заданих значень змінних.

Вхідні дані:

SVarVec - вектор значень змінних (в такому порядку, в якому змінні

йдуть в рядку-заголовку умови багатокритеріальної задачі);

SDestFuncRowNum - номер рядка функції мети в умові задачі у

Self. CopyTable;

Self. CopyTable - матриця коефіцієнтів умови

багатокритеріальної лінійної задачі оптимізації.

Вихідні дані:

Повертає значення функції мети.}

Var VarNum: Integer; FuncVal:TWorkFloat;

Begin

FuncVal:=0;

For VarNum:=0 to Length(SVarVec) - 1 do {для кожної змінної:}

Begin

FuncVal:=FuncVal + SVarVec[VarNum]*Self. CopyTable [SDestFuncRowNum, VarNum];

End;

CalcDFuncVal:=FuncVal;

End;

Function TGridFormattingProcs. SolveMultiCritLTask: Boolean;

{Вирішування задачі багатокритеріальної оптимізації лінійної форми

з використанням теоретико-ігрового підходу.

Умовою задачі є умови-нерівності, рівняння та умови на невід'ємність

окремих змінних, і декілька функцій мети, для яких треба знайти

якомога більші чи менші значення.

Вхідні дані:

Self. CurTable - таблиця коефіцієнтів та вільних членів;

Self. CurHeadRow - рядок-заголовок зі змінними та одиницею-множником

стовпця вільних членів (має бути останнім);

Self. CurHeadCol - стовпець-заголовок з іменами функцій-нерівностей,

нулями (заголовки рядків-рівнянь), іменами функцій мети

(що максимізуються (тип комірки bc_DestFuncToMax) або мінімізуються

(тип bc_DestFuncToMin)).

Функція повертає ознаку успішності вирішування.}

Var Row, CurWidth, CurHeight, FirstDestFuncRow,

DestFuncCount, VarCount: Integer;

Res1: Boolean;

st1: String;

OptimXVecs, DualUVec:TFloatMatrix;

OptimFuncVals, OptGTaskVal, ComprXVec:TFloatArr;

Const sc_CurProcName='SolveMultiCritLTask';

sc_TextMarkRow='############';

Procedure ShowWeightCoefs (Const SCoefs:TFloatArr; FirstDestFuncRow: Integer);

Var i: Integer;

Begin

If Self. CurOutConsole<>Nil then

Begin

Self. CurOutConsole. Lines. Add (sc_WeightCoefs);

For i:=0 to Length(SCoefs) - 1 do

Begin

{Відображаємо вагові коефіцієнти для кожної з функцій мети

багатокритеріальної задачі:}

Self. CurOutConsole. Lines. Add ('l['+

Self. CopyHeadCol [FirstDestFuncRow+i].AsVarName+'] = '+

FloatToStr (SCoefs[i]));

End;

End;

End;

Procedure ShowComprVarVec (Const ComprXVec:TFloatArr);

Var Col: Integer; st1: String;

Begin

If Self. CurOutConsole<>Nil then

Begin

Self. CurOutConsole. Lines. Add (sc_ComprVarVals);

For Col:=0 to Length(ComprXVec) - 1 do

Begin

st1:=Self. CopyHeadRow[Col].AsVarName + ' = ';

st1:=st1 + FloatToStr (ComprXVec[Col]);

Self. CurOutConsole. Lines. Add(st1);

End;

End;

End;

Procedure ShowDFuncVals (Const ComprXVec:TFloatArr; FirstDFuncRow: Integer);

Var Row: Integer; st1: String;

Begin

If Self. CurOutConsole<>Nil then

Begin

Self. CurOutConsole. Lines. Add (sc_DestFuncComprVals);

For Row:=FirstDFuncRow to Length (Self. CopyTable) - 1 do

Begin

st1:=Self. CopyHeadCol[Row].AsVarName + ' = ';

st1:=st1 + FloatToStr (Self. CalcDFuncVal (ComprXVec, Row));

Self. CurOutConsole. Lines. Add(st1);

End;

End;

End;

Label LStopLabel, LFinish;

Begin

Res1:=True; {прапорець успішності}

Self. GetTaskSizes (CurWidth, CurHeight);

If CurWidth<=0 then {Якщо таблиця пуста, то задача пуста:}

Begin

If Self. CurOutConsole<>Nil then

Self. CurOutConsole. Lines. Add (sc_CurProcName + sc_EmptyTable);

Self. WasNoRoots:=True;

SolveMultiCritLTask:=False;

Exit;

End;

If Self. CurOutConsole<>Nil then

Begin

Self. CurOutConsole. Lines. Add('');

Self. CurOutConsole. Lines. Add (sc_CurProcName + sc_StartSolving);

End;

{Зберігаємо посилання на масиви умови багатокритеріальної задачі:}

Self. CopyHeadRow:=Self. CurHeadRow;

Self. CopyHeadCol:=Self. CurHeadCol;

Self. CopyTable:=Self. CurTable;

{Шукаємо цільові функції внизу таблиці:}

For Row:=CurHeight-1 downto 0 do

Begin

Case Self. CopyHeadCol[Row].ElmType of

bc_DestFuncToMax:;

bc_DestFuncToMin:;

{Якщо знизу вгору дійшли до рядка, що не є функцією мети - завершуємо:}

Else Break;

End;

End;

If Row>=CurHeight-1 then {якщо рядків функцій мети взагалі немає:}

Begin

If Self. CurOutConsole<>Nil then

Self. CurOutConsole. Lines. Add (sc_CurProcName + sc_NoDestFuncs);

Self. WasNoRoots:=True;

Res1:=False; Goto LFinish;

End

Else if Row<0 then {якщо в таблиці є тільки рядки функцій мети:}

Begin

If Self. CurOutConsole<>Nil then

Self. CurOutConsole. Lines. Add (sc_CurProcName + sc_OnlyDestFuncsPresent);

Res1:=False; Goto LFinish;

(* Row:=-1; *)

End;

FirstDestFuncRow:=Row+1; {найвищий у таблиці рядок функції мети}

DestFuncCount:=CurHeight-FirstDestFuncRow; {кількість функцій мети}

{Змінні: усі стовпці окрім останнього (стовпця вільних членів з

одиницею в заголовку):}

VarCount:=CurWidth-1;

{Вектори змінних в оптимальних розв'язках задач:}

SetLength (OptimXVecs, DestFuncCount, VarCount);

{Оптимальні значення функцій (максимальні або мінімальні значення):}

SetLength (OptimFuncVals, DestFuncCount);

{############ Шукаємо min або max кожної функції мети окремо: ############}

For Row:=FirstDestFuncRow to CurHeight-1 do {для усіх функцій мети:}

Begin

If Self. CurOutConsole<>Nil then

Begin

st1:=sc_TextMarkRow+sc_CurProcName + sc_ForDestFunc+

sc_DoubleQuot+ Self. CopyHeadCol[Row].AsVarName +sc_DoubleQuot+sc_Space;

If Self. CopyHeadCol[Row].ElmType=bc_DestFuncToMin then

st1:=st1+sc_SearchingMin

Else st1:=st1+sc_SearchingMax;

st1:=st1+sc_TriSpot+sc_TextMarkRow;

Self. CurOutConsole. Lines. Add(st1);

End;

{Формуємо умову однокритеріальної задачі максимізації:}

If Not (Self. PrepareDestFuncInMultiDFuncLTask (Row, FirstDestFuncRow)) then

Begin

Res1:=False; Break;

End;

If Self. Stop then Break;

{Ховаємо розв'язувальну комірку у екранній таблиці (її нема тут):}

Self. CurGridSolveCol:=0; Self. CurGridSolveRow:=0;

{Відображаємо підготовану однокритеріальну задачу:}

WaitForNewStep (Self.CHeadColNum, Self.CHeadRowNum);

If Self. Stop then Break;

{Запускаємо вирішування однокритеріальної задачі максимізації лінійної

форми (так як поточна функція є функцією максимізації, або зведена

до такої):}

Self. WasNoRoots:=False; Self. WasManyRoots:=False; Self. SolWasFound:=False;

If Not (Self. SolveLTaskToMax(False)) then

Begin

Res1:=False; Break;

End;

{Якщо функція мети необмежена або система умов несумісна:}

If Not (Self. SolWasFound) then

Begin

{Якщо функцій мети більше одної, то так як компромісний вектор

через необмеженість принаймні одної з функцій мети знайти неможливо:}

If (FirstDestFuncRow+1)<CurHeight then Res1:=False

Else Res1:=True;

Goto LFinish;

End;

If Self. Stop then Break;

{Читаємо вектор значень змінних та оптимальне значення функції мети

з таблиці:}

Self. ReadCurFuncSolution (OptimXVecs, OptimFuncVals, Row-FirstDestFuncRow,

False, False);

End;

If Not(Res1) then Goto LFinish;

If Self. Stop then Goto LStopLabel;

{############ Шукаємо міри неоптимальності і будуємо задачу: ############}

{######## пошуку компромісних вагових коефіцієнтів, вирішуємо її: ########}

If Self. CurOutConsole<>Nil then Self. CurOutConsole. Lines. Add (sc_TextMarkRow);

BuildPaymentTaskOfOptim (OptimXVecs, OptimFuncVals, FirstDestFuncRow);

If Self. Stop then Goto LStopLabel;

If Self. CurOutConsole<>Nil then

Self. CurOutConsole. Lines. Add (sc_TextMarkRow);

{Готуємо задачу до максимізації симплекс-методом:}

Res1:=Self. PrepareDFuncForSimplexMaximize;

If Not(Res1) then Goto LFinish;

{Запускаємо вирішування цієї задачі:}

Self. WasNoRoots:=False; Self. WasManyRoots:=False; Self. SolWasFound:=False;

{«True» - з відображенням значень двоїстої:}

If Not (Self. SolveLTaskToMax(True)) then

Begin

Res1:=False; Goto LFinish;

End;

{Якщо функція мети необмежена або система умов несумісна:}

If Not (Self. SolWasFound) then

Begin

Res1:=False; Goto LFinish;

End;

If Self. Stop then Goto LStopLabel;

{############ Обчислюємо вагові коефіцієнти: ############}

{Якщо задача-інтерпретація гри вирішена і знайдено оптимальне

значення функції, то читаємо це значення і значення змінних

двоїстої задачі:}

SetLength (OptGTaskVal, 1); {для запису значення функції мети}

SetLength (DualUVec, 1, DestFuncCount); {для запису значень змінних}

Self. ReadCurFuncSolution (DualUVec, OptGTaskVal, 0, False, True);

{Обчислюємо вагові коефіцієнти:}

For Row:=0 to DestFuncCount-1 do

DualUVec [0, Row]:=(DualUVec [0, Row]/OptGTaskVal[0]); {Li=ui/(W(U))}

If Self. CurOutConsole<>Nil then Self. CurOutConsole. Lines. Add (sc_TextMarkRow);

ShowWeightCoefs (DualUVec[0], FirstDestFuncRow);

{############ Обчислюємо компромісний вектор: ############}

Self. CalcComprVec (OptimXVecs, DualUVec[0], ComprXVec);

ShowComprVarVec(ComprXVec);

ShowDFuncVals (ComprXVec, FirstDestFuncRow);

Goto LFinish;

LStopLabel: {Якщо вирішування було перервано:}

{Повертаємо початкову умову на попереднє місце:}

Self. CurHeadRow:=Self. CopyHeadRow;

Self. CurHeadCol:=Self. CopyHeadCol;

Self. CurTable:=Self. CopyTable;

LFinish:

{Обнуляємо посилання на копію умови. Так як це динамічні масиви і

щодо них йде відлік кількості посилань, то для них не створюватимуться

зайві копії у пам'яті, і при роботі з CurHeadRow, CurHeadCol, CurTable

пам'ять буде виділена завжди тільки для їхніх поточних даних:}

Self. CopyHeadRow:=Nil;

Self. CopyHeadCol:=NIl;

Self. CopyTable:=Nil;

SolveMultiCritLTask:=Res1;

End;

Procedure TGridFormattingProcs. ChangeSignsInRow (CurRowNum: Integer);

{Зміна знаків у рядку таблиці і відповідній комірці у стовпці-заголовку.}

Var CurColNum: Integer;

Begin

For CurColNum:=0 to Length (Self. CurHeadRow) - 1 do

CurTable [CurRowNum, CurColNum]:=-CurTable [CurRowNum, CurColNum];

ChangeSignForValOrVarName (Self. CurHeadCol[CurRowNum]);

End;

Procedure TGridFormattingProcs. ChangeSignsInCol (CurColNum: Integer);

{Зміна знаків у стовпці таблиці і відповідній комірці у рядку-заголовку.}

Var CurRowNum: Integer;

Begin

For CurRowNum:=0 to Length (Self. CurHeadCol) - 1 do

CurTable [CurRowNum, CurColNum]:=-CurTable [CurRowNum, CurColNum];

ChangeSignForValOrVarName (Self. CurHeadRow[CurColNum]);

End;

Function TGridFormattingProcs. ShiftRowsUp (SHeadColElmTypes:THeadLineElmTypes;

ToChangeInitPosNums: Boolean=False):Integer;

{Функція переміщує рядки таблиці CurTable (разом із відповідними

комірками у стовпці-заголовку CurHeadCol) з заданими типами комірок

стовпця-заголовка вгору.

Вхідні дані:

SHeadColElmTypes - множина типів комірок, що мають бути переміщені вгору

(у стовпці-заголовку);

ToChangeInitPosNums - вмикач зміни позначок номера по порядку та

позначки розташування в таблиці як рядка чи стовпця.

Якщо рівний True, то рядки при переміщенні змінюють ці позначки

на позначки тих рядків, що були в тих місцях, на які рядки переміщені;

Self. CurTable - таблиця коефіцієнтів;

Self. CurHeadCol - стовпець-заголовок.

Вихідні дані:

Self. CurTable і Self. CurHeadCol - таблиця коефіцієнтів і

стовпець-заголовок з перенесеними вгору рядками і комірками;

функція повертає номер найвищого рядка із тих, що не було задано

переміщувати вгору (вище нього - ті, що переміщені вгору).}

Var HiNotInSetRow, CurRowToUp, CurRowNum: Integer;

Begin

{Номер найвищого рядка, що не є в множині тих, які переміщуються вгору.

Спочатку ставимо тут номер неіснуючого рядка:}

HiNotInSetRow:=-1;

{Йдемо по рядкам згори вниз:}

For CurRowNum:=0 to Length (Self. CurHeadCol) - 1 do

Begin {Шукаємо перший рядок з типом комірки, що не має переміщуватися вгору:}

If Not (Self. CurHeadCol[CurRowNum].ElmType in SHeadColElmTypes) then

Begin

HiNotInSetRow:=CurRowNum;

{шукаємо найнижчий рядок, який портібно переміщувати вгору:}

For CurRowToUp:=Length (Self. CurHeadCol) - 1 downto CurRowNum+1 do

Begin

If Self. CurHeadCol[CurRowToUp].ElmType in SHeadColElmTypes then Break;

End;

{Якщо таких рядків не знайдено, то усі вони вже вгорі:}

If CurRowToUp<=CurRowNum then Break

Else {Міняємо місцями рядок, що має бути вгорі, і рядок, що не має,

але розташований вище:}

ChangeRowsPlaces (Self. CurTable, Self. CurHeadCol, CurRowNum,

CurRowToUp, ToChangeInitPosNums);

End;

End;

ShiftRowsUp:=HiNotInSetRow;

End;

Function TGridFormattingProcs. ShiftRowsDown (

SHeadColElmTypes:THeadLineElmTypes;

ToChangeInitPosNums: Boolean=False):Integer;

{Функція переміщує рядки таблиці CurTable (разом із відповідними

комірками у стовпці-заголовку CurHeadCol) з заданими типами комірок

стовпця-заголовка вниз.

Вхідні дані:

SHeadColElmTypes - множина типів комірок, що мають бути переміщені вниз

(у стовпці-заголовку);

ToChangeInitPosNums - вмикач зміни позначок номера по порядку та

позначки розташування в таблиці як рядка чи стовпця.

Якщо рівний True, то рядки при переміщенні змінюють ці позначки

на позначки тих рядків, що були в тих місцях, на які рядки переміщені;

Self. CurTable - таблиця коефіцієнтів;

Self. CurHeadCol - стовпець-заголовок.

Вихідні дані:

Self. CurTable і Self. CurHeadCol - таблиця коефіцієнтів і

стовпець-заголовок з перенесеними донизу рядками і комірками;

функція повертає номер найвищого рядка із тих, що переміщені вниз

(вище нього - рядки тих типів, що не було задано переміщувати донизу).}

Var AllOtherHeadTypes:THeadLineElmTypes;

Begin

{Отримуємо протилежну множину типів комірок:}

AllOtherHeadTypes:=[bc_IndependentVar..bc_OtherType] - SHeadColElmTypes;

{Зсуваємо рядки з усіма іншими типами вгору (і рядки з заданими

типами залишаються внизу):}

ShiftRowsDown:=Self. ShiftRowsUp (AllOtherHeadTypes, ToChangeInitPosNums);

End;

Function TGridFormattingProcs. SolveLTaskToMax (DualTaskVals: Boolean):Boolean;

{Вирішування задачі максимізації лінійної форми (що містить умови-

нерівності, рівняння та умови на невід'ємність окремих змінних і

одну функцію мети, для якої треба знайти максимальне значення).

Вхідні дані:

DualTaskVals - вмикач режиму відображення змінних двоїстої задачі

(після завершення розв'язування, якщо оптимальне значення знайдено):

читаються значення змінних і функцій двоїстої задачі. Їхні

значення розміщені не на місці стовпця вільних членів, а у рядку

коефіцієнтів функції мети (функції мети прямої задачі). Вони є

значеннями змінних чи функцій, імена яких у рядку-заголовку.

Змінні чи функції-нерівності двоїстої задачі з іменами у

стовпці-заголовку є рівними нулю.

Вихідні дані:

DResult - тип результату вирішування, який досягнутий (у випадку

успішного вирішування);

Функція повертає ознаку успішності вирішування.}

Const sc_CurProcName='SolveLTaskToMax';

Var CurRowNum, CurRow2N, CurColNum: Integer;

HeadRowNum, HeadColNum: Integer;

HiNoIndepRow: Integer;

ColDeleted, RowDeleted, AllExcluded, WasNothingToDo: Boolean;

st1: String;

Procedure SearchMNNCellForCol (CurColNum: Integer;

StartRowNum, EndRowNum: Integer;

Var DRowNum: Integer; AllowNegatCellIfZero: Boolean=False);

{Пошук у стовпці CurColNum комірки з МНВ (мінімального невід'ємного

відношення вільного члена до значення комірки у стовпці).

AllowNegatCellIfZero - дозволити від'ємне значення комірки і при

нульовому вільному члені.}

Var CurRowNum, FoundRow: Integer; MNN, CurRelat:TWorkFloat;

Begin

{Шукаємо МНВ у заданому інтервалі рядків:}

FoundRow:=-1; MNN:=-1;

For CurRowNum:=StartRowNum to EndRowNum do

Begin {Перевірка виконання умов невід'ємного відношення:}

If (CurTable [CurRowNum, CurColNum]<>0) and


Подобные документы

  • Задача лінійного програмування. Розв’язання задачі геометричним методом. Приведення системи рівнянь до канонічного вигляду. Розв’язання симплекс-методом. Розв’язок двоїстої задачі. Задача цілочислового програмування і дробово-лінійного програм.

    контрольная работа [385,2 K], добавлен 04.06.2009

  • Лінійне програмування як один з найбільш популярних апаратів математичної теорії оптимального управління рішень. Опис існуючих методів розв’язку задач лінійного програмування. Завдання, основні принципи, алгоритми і головна мета лінійного програмування.

    курсовая работа [363,8 K], добавлен 03.12.2009

  • Теоретичні основи та приклади економічних задач лінійного програмування. Розробка математичної моделі задачі (запис цільової функції і системи обмежень) і програмного забезпечення її вирішення за допомогою "Пошуку рішень" в Excel симплекс-методом.

    курсовая работа [993,9 K], добавлен 10.12.2010

  • Використання мови програмуванння Java при виконанні "задачі лінійного програмування": її лексична структура і типи даних. Методи розв’язання задачі. Особливості логічної структури програми, побудова її зручного інтерфейсу за допомогою симплекс методу.

    курсовая работа [437,9 K], добавлен 24.01.2011

  • Загальний вид двовимірного завдання лінійного програмування. Алгоритм рішення задач графічним методом. Максимізація (мінімізація) цільової функції. Послідовність рішення завдань лінійного програмування симплексом-методом. Принцип перетворення Гауса.

    контрольная работа [149,8 K], добавлен 24.11.2010

  • Початковий опорний план, перехід від одного до іншого. Оптимальний розв’язок, його головні критерії. Знаходження опорного плану задачі, складання симплексної таблиці. Приклад оформлення першої та другої таблиці для розв’язку задач лінійного програмування.

    лекция [479,7 K], добавлен 10.10.2013

  • Застосування симплекс-методу для розв’язання оптимізаційних задач лінійного програмування, що містять три змінні. Функції ітераційної обчислювальної процедури, що виконують приведення до зручного для розв’язання оптимального вигляду ЗЛП за кілька кроків.

    курсовая работа [359,5 K], добавлен 18.09.2013

  • Основні визначення дослідження операцій. Модель "затрати-випуск" В.В. Леонтьєва. Загальний вигляд задачі лінійного програмування. Розв'язання за допомогою симплекс-методу. Економічна інтерпретація основної та спряженої задач. Поліпшення плану перевезень.

    учебное пособие [1,1 M], добавлен 27.12.2010

  • Метод Якобі є узагальненням симплекса-методу лінійного програмування. Він використовується для дослідження чутливості оптимального значення функції до змін у правих частинах обмежень. Умови існування екстремумів функцій при відсутності обмежень.

    курсовая работа [326,6 K], добавлен 09.01.2009

  • Постановка задачі багатокритеріальної оптимізації та її та математична модель. Проблеми і класифікація методів вирішення таких задач, способи їх зведення до однокритеріальних. Метод послідовних поступок. Приклад розв'язування багатокритеріальної задачі.

    курсовая работа [207,3 K], добавлен 22.12.2013

Работы в архивах красиво оформлены согласно требованиям ВУЗов и содержат рисунки, диаграммы, формулы и т.д.
PPT, PPTX и PDF-файлы представлены только в архивах.
Рекомендуем скачать работу.