Вход

Программная реализация симплекс-метода

Курсовая работа* по программированию
Дата добавления: 27 мая 2007
Язык курсовой: Русский
Word, rtf, 1.1 Мб (архив zip, 57 кб)
Курсовую можно скачать бесплатно
Скачать
Данная работа не подходит - план Б:
Создаете заказ
Выбираете исполнителя
Готовый результат
Исполнители предлагают свои условия
Автор работает
Заказать
Не подходит данная работа?
Вы можете заказать написание любой учебной работы на любую тему.
Заказать новую работу
* Данная работа не является научным трудом, не является выпускной квалификационной работой и представляет собой результат обработки, структурирования и форматирования собранной информации, предназначенной для использования в качестве источника материала при самостоятельной подготовки учебных работ.
Очень похожие работы










Курсовая работа.


Тема: Программная реализация симплекс-метода.


Задача о диете (примерная задача).







































ПЛАН


  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.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 не добавляются - их наличие неявно предполагается самим симплекс-методом и уже реализовано программным путем.



Литература

  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 с.,ил.


20



© Рефератбанк, 2002 - 2024