p>  task.Items.Add('');

  task.Items.Add('Èòåðàöèÿ '+InttoStr(IterCount));

  for i:=0 to GoalChild.ColCount-1 do

  begin

    for j:=0 to length(SimplexTable[0])-1 do

    if i+1=SimplexTable[0,j] then

    begin

    task.Items.Add('  '+GoalChild.Cells[i,0]+'='+FloatToStr(SimplexTable[1,j]));

    bil:=true;

    end;

  if not bil then task.Items.Add('  '+GoalChild.Cells[i,0]+'=0');

  bil:=false;

  end;

end;

end;

 

until false;

fin:

if art then

  begin

  art:=false;

  SetLength(SimplexTable,Length(SimplexTable)-MoreCount,Length(SimplexTable[0])-1);

  goto up;

  end;

//Ðåçóëüòàò

with MainForm.ActiveMDIChild as TChildForm do

  begin

  task.Items.Add('');

  task.Items.Add('Ðåçóëüòàò');

  for i:=0 to GoalChild.ColCount-1 do

  begin

    for j:=0 to length(SimplexTable[0])-1 do

    if i+1=SimplexTable[0,j] then

    begin

    task.Items.Add('  '+GoalChild.Cells[i,0]+'='+FloatToStr(SimplexTable[1,j]));

    bil:=true;

  end;

  if not bil then task.Items.Add('  '+GoalChild.Cells[i,0]+'=0');

  bil:=false;

  end;

  task.Items.Add('');

  if parametersForm.Min.Checked then

  task.Items.Add('Ìèíèìàëüíîå çíà÷åíèå ôóíêöèè '+FloatToStr(-1*(SimplexTable[1,length(SimplexTable[0])-1])))

  else

  task.Items.Add('Ìàêñèìàëüíîå çíà÷åíèå ôóíêöèè '+FloatToStr(SimplexTable[1,length(SimplexTable[0])-1]));

  end;

end;

 

procedure TMainForm.SaveAsClick(Sender: TObject);

var

  FExt: String;

begin

  with SaveDialog1 do

  begin

    if ActiveMDIChild.Caption[1]='Ç' then

    FileName:=ActiveMDIChild.Caption+'.tsk'

    else

    FileName:=ActiveMDIChild.Caption;

    FExt:=ExtractFileExt(FileName);

    if length(Fext)=0 then

     FExt:='.tsk';

    filter:='Files (*'+FExt+')|*'+FExt;

    if Execute then

    with ActiveMDIchild as TChildForm do

      SaveData(FileName);

  end;

end;

 

 

procedure TMainForm.OpenClick(Sender: TObject);

var

  s:string;

  i,k:integer;

begin

  if OpenDialog1.Execute then

  begin

     with fileMenu do

       begin

       if not N11.Visible then N11.Visible:=true;

       k:=IndexOf(N1Name1);

       for i:=count-3 downto k+1 do

         begin

         s:=items[i-1].caption;

         s[2]:=chr(ord('0')+(i-k+1));

         Items[i].Caption:=S;

         Items[i].Visible:=Items[i-1].Visible;

         end;

       n1name1.Caption:='&1 '+OpenDialog1.FileName;

       n1name1.Visible:=true;

       end;

    CreateChild(OpenDialog1.FileName);

    with ActiveMDIChild as TChildForm do

      LoadData(OpenDialog1.FileName);

    ParametersForm.FormShow(Sender);

    ParametersForm.Button3Click(Sender);

  end;

end;

 

procedure TMainForm.SaveClick(Sender: TObject);

begin

if pos('Çàäà÷à',activemdichild.caption)=1 then

SaveAsClick(Sender) else with activemdichild as TChildForm do

    SaveData(Caption);

end;

 

procedure TMainForm.DelLimClick(Sender: TObject);

var i:byte;

begin

with ActiveMDIChild as TChildForm do

begin

if ItemDel<4 then MessageDlg('Îãðàíè÷åíèå  íå âûáðàíî',mtWarning,[mbOK],0) else

  begin

  ParametersForm.FormShow(Sender);

  for i:=0 to ItemDel-5 do ParametersForm.BitBtn3Click(Sender);

  ParametersForm.BitBtn1Click(Sender);

  ParametersForm.Button3Click(Sender);

  end;

  end;

end;

 

procedure TMainForm.N8Click(Sender: TObject);

var i:byte;

begin

with Mainform.ActiveMDIChild as TChildForm do

begin

  GoalChild.ColCount:=2;

  LimChild.ColCount:=2;

  LimChild.RowCount:=1;

  BChild.RowCount:=1;

  SignsChild.RowCount:=1;

for i:=0 to 1 do

  GoalChild.Cells[i,1]:='0';

  GoalChild.Cells[0,0]:='X1';

  GoalChild.Cells[1,0]:='X2';

  Task.Clear;

end;

end;

 

procedure TMainForm.N1Name1Click(Sender: TObject);

var FileName:string;

begin

with sender as TMenuItem do

   begin

   FileName:=caption;

   System.Delete(FileName,1,2);

   end;

   CreateChild(OpenDialog1.FileName);

    with ActiveMDIChild as TChildForm do

      LoadData(OpenDialog1.FileName);

    ParametersForm.FormShow(Sender);

    ParametersForm.Button3Click(Sender);

end;

 

end.

4.Контрольный пример

Пример 1.

Завод выпускает продукцию 1-го и 2-го типа. Прибыль от реализации единицы  продукции соответственно составляет 30 и 40 у.е.

На выпуск единицы продукции 1-го типа расходуется 4 единиц сырья категории  А, 4 ед. – категории В. Для выпуска  единицы продукции 2-го типа расходуется  сырья категории А - 3 ед., категории  С – 12 единицы.

Имеющиеся в наличие запасы сырья  категории А – 120 единиц, В – 252 единицы.

 

Необходимо определить количество продукции, при выпуске которой  прибыль является максимальной.

Таким образом, приходим к  следующей математической задаче: дана система

4x₁ +4х₂ ≤ 120,

3x₁ + 12х₂ ≤ 252,       (2)

двух линейных неравенств с двумя неизвестными х_j (j=1..2) и линейная функция относительно этих же переменных

F= 30x₁ + 40х₂        (3)

Требуется среди всех неотрицательных  решений системы неравенств (2) найти  такое, при котором функция (3) принимает  максимальное значение, т.е.

F=30x₁+40x₂ max

 

 

Ответ:

x₁ = 12, x₂ = 18, F_опт=1080

Таким образом, если предприятие изготовит 12 единиц изделий вида А и 18 единиц изделий В, то оно получит максимальную прибыль, равную 1080 у.е.

Пример 2

Рассмотрим задачу:

z=3x1 + 9x2   - >max

x1 + 4x2 <=8 ,

x1 + 2x2 <=4 ,

x1, x2 >= 0.

Введя остаточные переменные x3 и x4, представим результаты итераций

симплекс-метода в виде сводной  таблицы.

 

 

 

 

 

 

 

 

 

 

 

На  начальной итерации в качестве исключаемой  переменной можно выбрать как x3 , так и x4. Выбрана переменная x3 , тогда переменная x4, оставаясь базисной на итерации 1, принимает нулевое значение, а это приводит к получению вырожденного базисного решения. Оптимальное решение задачи получается на следующей итерации.

Сравнивая итерации 1 и 2, заметим следующее: хотя состав базисных и небазисных переменных на этих итерациях различен, значения всех переменных и целевой функции не изменяются:

x1 = 0, x2 = 2, x3 = 0, x4 = 0, z = 18.

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

 

 

Пример3

z =2x1 + 4x2 -> max

x1 + 2x2 <= 5 ,

x1 + x2 <= 4 ,

x1 , x2 >= 0.

Приведем задачу к стандартному виду и решим симплекс-методом.

Как известно, в симплекс-методе используются координаты только угловых точек пространства решений. Из симплекс-таблиц видно, что  оптимум

x₁ *=0 ,

 x₂* = 5/ 2, z max = 10, получен на итерации 1. На этой итерации можно узнать о наличии альтернативных оптимальных решений по нулевому значению коэффициента (небазисной) переменной x1 в строкеz, которое свидетельствует о том, что ее включение в базис не изменит значения целевой функции, но приведет к изменению значений других переменных. Именно это и происходит на итерации 2, когда переменная x1 вводится в базис вместо x4. В результате получается новое оптимальное решение

 x ₁*=  3

x₂* =1 , z max = 10.

Два полученных оптимальных решения соответствуют  двум угловым точкам A и B, через которые проходит граница ОДР, параллельная линии уровня. Любое другое альтернативное оптимальное решение, т.е. координаты любой точки (x¢1, x¢2 ) отрезка AВ, можно получить с помощью координат точек A и B по формулам

x¢1 = a x1A + (1—a) x1B , x¢2 = a x2A + (1—a) x2B , где 0 <= a <= 1.

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

Пример 4

z =2x1 + x2 ->max

x1 – 2x2 <=10 ,

2x1 <=40 ,

x1, x2 >= 0.

 

 

 

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

Анализ  этой таблицы показывает, что во все коэффициенты столбца x2 либо отрицательны, либо равны нулю. Это означает, что x2 можно бесконечно увеличивать, не нарушая ни одного из ограничений модели.

Общее правило выявления неограниченного  решения заключается в следующем: если на некоторой итерации небазисная переменная имеет в ограничениях неположительные коэффициенты, пространство решений соответствующей задачи в данном направлении не ограничено. Если, кроме того, коэффициент при этой переменной в строке z отрицательный, а z подлежит максимизации или данный коэффициент положительный, а z подлежит ми-