Курсовая работа: Багатокритеріальна задача лінійного програмування
{Зсуваємо рядки з усіма іншими типами вгору (і рядки з заданими
типами залишаються внизу):}
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
(AllowNegatCellIfZero or
(CurTable [CurRowNum, Length (Self. CurHeadRow) – 1]<>0) or
(CurTable [CurRowNum, CurColNum]>0)) and
((ValSign (CurTable[CurRowNum, Length (Self. CurHeadRow) – 1])*
ValSign (CurTable[CurRowNum, CurColNum]))>=0) then
Begin
CurRelat:=CurTable [CurRowNum, Length (Self. CurHeadRow) – 1]/
CurTable [CurRowNum, CurColNum];
{Якщо знайшли менше, або знайшли перше значення:}
If (CurRelat<MNN) or (FoundRow=-1) then
Begin
MNN:=CurRelat; FoundRow:=CurRowNum;
End;
End;
End;
If (Self. CurOutConsole<>Nil) and (FoundRow<0) then
Self. CurOutConsole. Lines. Add (sc_CurProcName+sc_NoMNN+sc_Space+
IntToStr (CurColNum+1)+sc_Space+sc_TriSpot);
DRowNum:=FoundRow;
End;
Label LStopLabel;
Begin
If Self. TaskWidth<=0 then {Якщо таблиця пуста, то задача пуста:}
Begin
If Self. CurOutConsole<>Nil then
Self. CurOutConsole. Lines. Add (sc_CurProcName + sc_EmptyTable);
SolveLTaskToMax:=False;
Exit;
End;
HeadRowNum:=Self.CHeadRowNum;
HeadColNum:=Self.CHeadColNum;
If Self. CurOutConsole<>Nil then
Begin
Self. CurOutConsole. Lines. Add (sc_CurProcName + sc_StartSolving);
Self. CurOutConsole. Lines. Add (sc_CurProcName + sc_ExcludingFreeVars);
End;
{############## Виключаємо незалежні змінні: ##############}
CurRowNum:=0;
Repeat
WasNothingToDo:=True; AllExcluded:=True;
CurColNum:=0;
While CurColNum<(Length (Self. CurHeadRow) – 1) do {усі стовпці окрім останнього}
Begin
ColDeleted:=False;
{Координати розв'язувальної комірки для помітки кольором в екранній
таблиці:}
Self. CurGridSolveCol:=CurColNum+HeadColNum+bc_LTaskColsBeforeVars;
Self. CurGridSolveRow:=CurRowNum+HeadRowNum+bc_LTaskRowsBeforeVars;
{Якщо поточна змінна незалежна:}
If Self. CurHeadRow[CurColNum].ElmType=bc_IndependentVar then
Begin {Перевіряємо, чи не дійшли до рядка функції
(або взагалі за низ таблиці):}
If CurRowNum<(Length (Self. CurHeadCol) – 1) then
Begin {якщо рядки для виключення ще залишились:}
{Шукаємо ненульову комірку серед коефіцієнтів поточної
незалежної змінної (окрім останнього рядка, що є
рядком поточної функції мети):}
If SearchNozeroSolveCell (CurRowNum, CurColNum,
Length (Self. CurHeadCol) – 2, Length (Self. CurHeadRow) – 2,
HeadRowNum, HeadColNum, False) then
Begin {якщо змінну можна виключити:}
WaitForNewStep (HeadColNum, HeadRowNum);
If Self. Stop then Goto LStopLabel;
{Обробляємо таблицю модифікованим Жордановим виключенням:}
If Not (Self.GI (CurColNum, CurRowNum, Self. CurHeadRow,
Self. CurHeadCol, Self. CurTable, ColDeleted, True,
True)) then
Begin
SolveLTaskToMax:=False; Exit;
End;
WasNothingToDo:=False;
{Переходимо до наступного рядка, бо даний рядок тепер вже є
рядком виключеної вільної змінної (і змінна виражена як
функція-нерівність):}
Inc(CurRowNum);
End
Else {якщо для незалежної змінної усі коефіцієнти обмежень – нулі}
Begin {то змінна зовсім незалежна:}
{І якщо в рядку функції мети теж нуль, то:}
If Self. CurTable [Length(Self. CurHeadCol) – 1, CurColNum]=0 then
Begin {хоч змінна й незалежна, від неї теж нічого тут не залежить:}
If Self. CurOutConsole<>Nil then
Begin
st1:=sc_CurProcName+sc_FreeVar;
If Self. CurHeadRow[CurColNum].ElmType=bc_Number then
st1:=st1+sc_Space+
FloatToStr (Self. CurHeadRow[CurColNum].AsNumber)
Else st1:=st1+sc_Space+sc_DoubleQuot+
Self. CurHeadRow[CurColNum].AsVarName+sc_DoubleQuot;
Self. CurOutConsole. Lines. Add(st1);
End;
WaitForNewStep (HeadColNum, HeadRowNum);
If Self. Stop then Goto LStopLabel;
{Видаляємо стовпець цієї змінної:}
DeleteFromArr (Self. CurHeadRow, CurColNum, 1);
DelColsFromMatr (Self. CurTable, CurColNum, 1);
ColDeleted:=True;
WasNothingToDo:=False;
End
Else AllExcluded:=False; {не усі вільні вдалося виключити}
End;
End
Else AllExcluded:=False; {не усі вільні вдалося виключити}
End;
If Not(ColDeleted) then Inc(CurColNum);
End; {While (CurColNum<(Length (Self. CurHeadRow) – 1)) do…}
Until AllExcluded or WasNothingToDo;
If Not(AllExcluded) then
Begin
If Self. CurOutConsole<>Nil then
Self. CurOutConsole. Lines. Add (sc_CurProcName+sc_CantExcludeFreeVars);
Self. WriteTableToGrid (HeadColNum, HeadRowNum, True);
SolveLTaskToMax:=True; Exit;
End;
{Переміщаємо рядки з усіма незалежними змінними вгору:}
HiNoIndepRow:=Self. ShiftRowsUp([bc_IndependentVar], False);
If Self. CurOutConsole<>Nil then
Self. CurOutConsole. Lines. Add (sc_CurProcName+sc_AllFreeVarsExcluded);
{Ховаємо розв'язувальну комірку у екранній таблиці:}
Self. CurGridSolveCol:=0; Self. CurGridSolveRow:=0;
WaitForNewStep (HeadColNum, HeadRowNum);
If Self. Stop then Goto LStopLabel;
{Якщо усі рядки є рядками незалежних змінних, то номер найвищого рядка
іншого типу вважаємо нижче таблиці (бо нема таких рядків):}
If HiNoIndepRow<0 then HiNoIndepRow:=Length (Self. CurHeadCol);
{Якщо після виключення незалежних змінних не залишилося рядків, окрім
рядка функції:}
If HiNoIndepRow>=(Length (Self. CurHeadCol) – 1) then
Begin
If Self. CurOutConsole<>Nil then
Self. CurOutConsole. Lines. Add (sc_CurProcName+sc_NoTableAreaToWork);
End;
If Self. CurOutConsole<>Nil then
Self. CurOutConsole. Lines. Add (sc_CurProcName+sc_ExcludingZeroRows);
{############## Виключаємо 0-рядки. Шукаємо їх: ##############}
CurRowNum:=HiNoIndepRow;
While CurRowNum<=(Length (Self. CurHeadCol) – 2) do
Begin
RowDeleted:=False;
If Self. CurHeadCol[CurRowNum].ElmType=bc_Number then
Begin
If Self. CurHeadCol[CurRowNum].AsNumber=0 then {якщо знайшли 0-рядок:}
Begin {Для помітки 0-рядка на екранній таблиці:}
Self. CurGridSolveCol:=HeadColNum;
Self. CurGridSolveRow:=CurRowNum+HeadRowNum+bc_LTaskRowsBeforeVars;
WaitForNewStep (HeadColNum, HeadRowNum);
If Self. Stop then Goto LStopLabel;
{Перевіряємо вільний член рядка, чи він невід'ємний.
Якщо від'ємний, то множимо обидві частини рівняння на -1:}
If CurTable [CurRowNum, Length (Self. CurHeadRow) – 1]<0 then
ChangeSignsInRow(CurRowNum);
{Шукаємо у рядку перший додатний коефіцієнт:}
For CurColNum:=0 to Length (Self. CurHeadRow) – 2 do
If CurTable [CurRowNum, CurColNum]>0 then Break;
If CurColNum>(Length (Self. CurHeadRow) – 2) then {Якщо усі недодатні:}
Begin
Страницы: 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24
