Курсовая работа.
Тема: Программная реализация симплекс-метода.
Задача о диете (примерная задача).
ПЛАН
Содержание задачи
Решение задачи
Описание математики
Литература
СОДЕРЖАНИЕ ЗАДАЧИ
Назовем
белки, жиры и витамины питательными
веществами (ПВ), а борщ ,хлеб, шоколад
видами пищи(ВП). Зависимость между ПВ и
ВП задает разработанная диетологами
матрица 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.StringGrid1GetEditText(Sender: TObject; ACol,
ARow: Integer; 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.FormClose(Sender: TObject; var Action: TCloseAction);
var i,j: integer;
F: TextFile;
begin
AssignFile(F, ExtractFilePath(Application.ExeName)+'simpex.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)+'simpex.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 := 999999.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 не добавляются - их наличие неявно предполагается самим симплекс-методом и уже реализовано программным путем.
Литература
Бородич Ю.С. и др. Паскаль для персональных компьютеров: Справ. пособие / Ю.С. Бородич, А.Н. Вальвачев, А.И. Кузьмич.-Мн.: Выш.шк.: БФ ГИТМП «Ника», 1991.-365с.:ил.
Бородич Ю.С. Разработка программных систем на языке Паскаль: Справ. пособие. – Мн.: Выш.шк.,1992. 143 с.:ил.
Вальвачев А.Н., Крисевич В.С. Программирование на языке Паскаль для персональных ЭВМ ЕС. –Мн.:Выш.шк.,1989. –223с
Вальвачев А.Н. Графическое программирование на языке Паскаль: Справ.пособие. – Мн.: Выш.шк.,1992. –143 с.:ил.
Вирт Н. Алгоритмы и структуры данных. М.: Мир, 1989
Епанешников А.М., Епанешников В.А. Turbo Vision 2.0. Основы практического использования. – М.: «ДИАЛОГ-МИФИ», 1995. –240 с.
Климов Ю.С. и др. Программирование в среде Turbo Pascal 6.0: Справ.пособие/ Ю.С. Климов, А.И. Касаткин, С.М. Мороз. –Мн.: Выш.шк., 1992. 158 с.:ил.
Кнут Д. Искусство программирования для ЭВМ. –М.:Мир, 1978. Т 3. – 844с.
Котов В.М., Волков И.А., Харитонович А.И. Методы алгоритмизации. Мн.: Нар.асвета, 1996. –127 с.:ил.
Липский В. Комбинаторика для программистов. М.: Мир, 1988. -213c.ил.
Мануйлов В.Г.Разработка программного обеспечения на Паскале. –М.: “Приор”., 1996. –238 с.
Офицеров Д.В. и др. Программирование на персональных ЭВМ.: Практикум: Учеб.пособие – Мн.:Выш.шк., 1993. –256с.
Фаронов В.В. Delphi 4. Учебный курс. Учебное пособие. –М.: “Нолидж”, 1999. –464 с.ил.
Фаронов В.В. Турбо Паскаль 7.0. Начальный курс. Учебное пособие. –М.: “Нолидж”, 1997. –616 с.ил.
Хьюз Дж., Мичтом Дж. Структурный подход к программированию. М.: Мир, 1980. –278 с.
Чип С. Turbo Pascal 6.0 Professional. ООП: Теория и практика. –Мн.:SCI, 1992. –138 с.,ил.