Решение задачи симплекс-методом (Delphi исходники) ключ на сайте http://iopa4.narod.ru

Курсовая работа. Тема: Программная реализация симплекс-метода. Задача о диете (примерная задача). ПЛАН 1. Содержание задачи 2. Решение задачи 3. Описание математики 4. Литература СОДЕРЖАНИЕ ЗАДАЧИ Назовем белки, жиры и витамины питательными веществами (ПВ), а борщ ,хлеб, шоколад видами пищи(ВП). Зависимость между ПВ и ВП задает разработанная диетологами матрица

D, размером m*n, где элемент d определяет, сколько единиц измерения i-го ПВ содержится в единице j-го ВП. Пусть даны c , с , …, с всех ВП и биологические нормы b , b , …, b , например, для человека на месяц для каждого ПВ. Считается, что потреблять меньше нормы нельзя. Пусть x , x , …, x - неизвестные нам количества ВП, которые надо купить.

Если будет куплено x , x , …, x ВП, то тем самым будет введено в диету количества ПВ всех видов, стоящие слева в неравенствах . Справа в неравенствах стоят биологические нормы, служащие ограничениями снизу. Нужно, чтобы выполнялись условия неотрицательности: x j= Если все, что нас интересует при составлении диеты это соблюдение минимальной биологической нормы, то найдем самую дешевую из допустимых диет, т.е. оптимизируем общую цену купленных продуктов:

РЕШЕНИЕ ЗАДАЧИ Для решения задачи запустим редактор Delphi и выберем опцию: «Файл» -> «Создать» -> «Приложение», затем на форму Form1 положим Panel1, Panel2. Установим свойства : Form1.BorderIcon biMaximize = False Form1.BorderStyle bsSingle Panel1.Align Left Panel2.Align Right Остальные свойства панелей по умолчанию.

Добавим на Panel1 StringGrid1 со свойствами: StringGrid1.Align Client StringGrid1.Options goEditing = True StringGrid1.RowCount 5 StringGrid1.ColCount 5 (Количество строк и колонок выставляем по пять. Нулевые колонки и строки служат для надписей, а 1 4 для ввода данных.) На Panel2 добавим GroupBox1 и установим GroupBox1.Caption=Сумма:

0.00 руб. Также добавим кнопку Button1 со свойством Button1.Caption=Расчет. На GroupBox1 положим Memo1 и настроем размер. Memo1.Allign=Bottom. В результате наших манипуляций примерно получится такое: Для того, что программа не давала сбой из-за неправильного ввода данных (ввод нецифровых значений, более одного децимального знака) – необходимо написать обработчик событий ввода с клавиатуры.

Выбираем StringGrid1, переходим на панель «События» и выбираем OnKeyPress. Делаем двойной клик мышкой и получаем заготовку этого события. Вписываем следующие строки: procedure TForm1.StringGrid1KeyPress(Sender: TObject; var Key: Char); begin case key of '0 9': ; //только цифры (отрицательные значания исключены) #8: ; //забой ://точка и запятая if Pos(DecimalSeparator,

StringGrid1.Cells[CurCol,CurRow]) = 0 then Key := DecimalSeparator else Key := #0; else key := #0; end; end; В этой процедуре есть глобальные переменные CurCol, CurRow, которые необходимо объявить в секции: var Form1: TForm1; CurCol, CurRow: integer; Чтобы получать автоматически значение строки и колонки во время

редактирования, необходимо прописать еще один обработчик события, аналогично описанному выше: procedure TForm1.StringGrid1Integer; var Value: String); begin CurCol:=ACol; CurRow:=ARow; end; Поступим так: «Файл» -> «Создать» -> «Модуль». Затем выберем «Сохранить проект как…» и сохраним основной модуль, как

Main.pas, а дополнительный модуль, как Simplex.pas, а сам проект, как Diet.dpr в отдельную папку. Теперь необходимо в модуль Simplex.pas дописать глобальные константы RC, CC (RowCount и ColCount) в секцию ниже interface до implementation, а в Main.pas в секции Uses дописать Simplex. Для того, чтобы при закрытии, разрабатываемой программы данные

из таблицы сохранялись в файл, в программу необходимо добавить функцию сохранения данных. Легче всего ее прописать в обработчик события Form1.onClose: procedure TForm1.ExeName)+'si mpex.dat'); Rewrite(F); With StringGrid1 do begin for i:=1 to

RC do begin for j:=1 to CC do begin if Cells[i,j]<> then Writeln(F,Cells[i,j]) else Writeln(F 0'); end; end; end; CloseFile(F); end; После описания этой процедуры, необходимо запустить программу на исполнение, нажав кнопку F9. Программа будет откомпилирована и выполнена. В результате этих действий, автоматически будет создан файл simpex.dat в директории с исполняемым файлом.

За этим проследит функция ExtractFilePath(Application.ExeName) строкового значения. Последовательность этой операции обязательна. Так как если сразу написать функцию загрузки файла, которую мы опишем ниже, то программа выдаст ошибку, что файла с таким именем нет. Приступим к написанию подпрограммы загрузки данных из файла, следующего содержания: procedure TForm1.FormCreate(Sender: TObject); var i,j: integer;

F: TextFile; s: string; begin R1:=1; //Для чего эта переменная, будет пояснено ниже AssignFile(F, ExtractFilePath(Application.ExeName)+'si mpex.dat'); Reset(F); With StringGrid1 do begin for i:=1 to RC do begin for j:=1 to CC do begin Readln(F,s); Cells[i,j]:=s; end; end; end; CloseFile(F); WriteBtnLabel; end; Переходим на вкладку

Simpex и дописываем следующие переменные: var NC, NV, NOPTIMAL, P1, P2, XERR: Integer; TS: Array[0 RC-1,0 CC-1] of Double; R1,R2: double; • NV – количество переменных в оптимизируемой функции. • NC – количество констант. • TS – массив, для ввода матрицы. • R1 – переменная, для выбора направления оптимизации (-1 – по минимуму,

1 – по максимуму). • R2 – промежуточная переменная для внутренних расчетов. • NOPTIMAL – булевая переменная, если значение False, то продолжить итерацию. • XMAX- переменная для сохранения высшего коэффициента, просчитываемой функции. • RAP – для сохранения наименьшей величины, но более 0. • V – вспомогательная переменная. • P1,P2 – линия, колонка (индексы) центрирования. •

XERR – булевая переменная (если True – нет решения). Ниже описания переменных дописываем процедуры: procedure Pivot; procedure Formula; procedure Optimize; А после секции implementation размещаем текст самих процедур. procedure Pivot; // В этой секции находится центр матрицы var RAP,V,XMAX: Double; I,J: Integer; begin XMAX := 0.0; for

J := 2 to NV + 1 do begin if (TS[1, J] > 0) and (TS[1, J] > XMAX) then begin XMAX := TS[1, J]; P2 := J end end; RAP := 9.0; for I := 2 to NC + 1 do begin if Not (TS[I, P2] >= 0) then begin V := ABS(TS[I, 1] / TS[I, P2]); if V < RAP then begin RAP := V; P1 := I end; end; end;

V := TS[0, P2]; TS[0, P2] := TS[P1, 0]; TS[P1, 0] := V end; procedure Formula; //Находим опорный базис Label 60,70,100; var I,J: Integer; begin for I := 1 to NC + 1 do begin if I = P1 then GOTO 70; for J := 1 to NV + 1 do begin if J = P2 then GOTO 60; TS[I, J] := TS[I, J] - TS[P1,

J] * TS[I, P2] / TS[P1, P2]; 60: end; 70: end; TS[P1, P2] := 1.0 / TS[P1, P2]; for J := 1 to NV + 1 do begin if J = P2 then GOTO 100; TS[P1, J] := TS[P1, J] * ABS(TS[P1, P2]); 100: end; for I := 1 to NC + 1 do begin if I = P1 then Exit; TS[I, P2] := TS[I, P2] * TS[P1, P2]; end end; procedure

Optimize;// Определяется, закончен ли процесс итерации var I,J: Integer; begin for I := 2 to NC + 1 do if TS[I, 1] < 0 then XERR := 1; NOPTIMAL := 0; if XERR = 1 then Exit; for J := 2 to NV + 1 do if TS[1, J] > 0 then NOPTIMAL := 1; end; В основном модуле опишем процедуру заполнения данных в матрицу, вывода результатов

и программу вывода надписей на зафиксированных колонках, строках StringGrid1 в секции private. private procedure ReadData; procedure Results; procedure WriteBtnLabel; Поставим курсор на процедуры и нажмем «Ctrl+C». Автоматически заполнятся заготовки заготовки процедур. Опишем каждую из них: procedure TForm1.ReadData; var i,j: integer; begin

NC:=CC-2; NV:=RC-2; for j:=1 to NV do begin R2:=StrToFloat(StringGrid1.Cells[j,1]); TS[1,j+1]:=R2*R1; end; R2:=StrToFloat(StringGrid1.Cells[CC,1]); TS[1,1]:=R2*R1; for i:=1 to NC do begin for j:=1 to NV do begin R2:=StrToFloat(StringGrid1.Cells[j,i+1]) ; TS[i+1,j+1]:=-R2; end; TS[i+1,1]:=StrToFloat(StringGrid1.Cells[

CC-1,i+1]); end; for j:=1 to NV do TS[0,j+1]:=j; for i:=NV+1 to NV+NC do TS[i-NV+1,0]:=i; end; procedure TForm1.Button1Click(Sender: TObject); begin XERR:=0; NOPTIMAL := 0; ReadData; repeat PIVOT; FORMULA; OPTIMIZE; until not (NOPTIMAL = 1); Results; end; procedure TForm1.Results; var i,j: Integer; begin

Memo1.Lines.Clear; if XERR <> 0 then begin GroupBox1.Caption:='Нет решения ; Exit; end else for I := 1 to NV do for J := 2 to NC + 1 do begin if TS[J, 0] = I then Memo1.Lines.Add(StringGrid1.Cells[i,0]+' : '+FormatFloat('##0.00 TS[j,1])); end; GroupBox1.Caption:='Сумма: '+FormatFloat('##0.00 TS[1, 1])+' руб ; end; procedure TForm1.WriteBtnLabel; begin

With StringGrid1 do begin Cells[0,1]:='Цена'; Cells[0,2]:='Белки'; Cells[0,3]:='Жиры'; Cells[0,4]:='Витам ; Cells[4,0]:='Норма'; Cells[3,0]:='Шоколад'; Cells[2,0]:='Хлеб '; Cells[1,0]:='Борщ '; end; end; Двойным кликом мышки по Button1 создадим процедуру обработки события: procedure TForm1.Button1Click(Sender: TObject); begin XERR:=0;

NOPTIMAL := 0; ReadData; repeat PIVOT; FORMULA; OPTIMIZE; until not (NOPTIMAL = 1); Results; end; Запустим на выполнение программу, нажав F9 и попробуем поэкспериментировать с данными, введя цены, количества питательных веществ и видов пищи. Изменив данные, щелкаем по кнопке «Расчет». Проверяем расчеты с помощью калькулятора. Описание математики Данный модуль (simplex.pas) реализует обычный симплекс-метод с десятичными числами

типа double для решения задачи вида: С =С1*X1+ С2 *X2+ + Сn*Xn > min (где С – цена) при ограничениях: b1*x1+ b2*x2+ + bn*xn <= (ПВ1) bm1*x1+ bm2*x2+ + bmn*xn <= (ПВn) (b – биологические нормы продукта, ПВ1-ПВn – общая норма питательных веществ по видам продуктов ВП) Ограничения вида x[j]>=0 не добавляются - их наличие неявно предполагается самим симплекс-методом

и уже реализовано программным путем. Литература 1. Бородич Ю.С. и др. Паскаль для персональных компьютеров: Справ. пособие / Ю.С. Бородич, А.Н. Вальвачев, А.И. Кузьмич Мн.: Выш.шк.: БФ ГИТМП «Ника», 1991 365с.:ил. 2. Бородич Ю.С. Разработка программных систем на языке

Паскаль: Справ. пособие. – Мн.: Выш.шк 1992. 143 с.:ил. 3. Вальвачев А.Н Крисевич В.С. Программирование на языке Паскаль для персональных ЭВМ ЕС. –Мн.:Выш.шк 1989. –223с 4. Вальвачев А.Н. Графическое программирование на языке Паскаль: Справ.пособие. – Мн.: Выш.шк 1992. –143 с.:ил.

5. Вирт Н. Алгоритмы и структуры данных. М.: Мир, 1989 6. Епанешников А.М Епанешников В.А. Turbo Vision 2.0. Основы практического использования. – М.: «ДИАЛОГ-МИФИ», 1995. –240 с. 7. Климов Ю.С. и др. Программирование в среде Turbo Pascal 6.0: Справ.пособие/ Ю.С. Климов, А.И.

Касаткин, С.М. Мороз. –Мн.: Выш.шк 1992. 158 с.:ил. 8. Кнут Д. Искусство программирования для ЭВМ. –М.:Мир, 1978. Т 3. – 844с. 9. Котов В.М Волков И.А Харитонович А.И. Методы алгоритмизации. Мн.: Нар.асвета, 1996. –127 с.:ил. 10. Липский В. Комбинаторика для программистов. М.:

Мир, 1988. -213c.ил. 11. Мануйлов В.Г.Разработка программного обеспечения на Паскале. –М.: “Приор” 1996. –238 с. 12. Офицеров Д.В. и др. Программирование на персональных ЭВМ.: Практикум: Учеб.пособие – Мн.:Выш.шк 1993. –256с. 13. Фаронов В.В. Delphi 4. Учебный курс. Учебное пособие. –М.: “Нолидж”,

1999. –464 с.ил. 14. Фаронов В.В. Турбо Паскаль 7.0. Начальный курс. Учебное пособие. –М.: “Нолидж”, 1997. –616 с.ил. 15. Хьюз Дж Мичтом Дж. Структурный подход к программированию. М.: Мир, 1980. –278 с. 16. Чип С. Turbo Pascal 6.0 Professional. ООП: Теория и практика. –Мн.:SCI, 1992. –138 с ил.