Реализация методов решения минимизации средневзвешенного суммарного штрафа на компьютере и разработка программы

ФИЛИАЛ ГОСУДАРСТВЕННОГО АВТОНОМНОГО ОБРАЗОВАТЕЛЬНОГО УЧРЕЖДЕНИЯ ВЫСШЕГО ПРОФЕССИОНАЛЬНОГО ОБРАЗОВАНИЯ «КАЗАНСКИЙ (ПРИВОЛЖСКИЙ) ФЕРЕДАЛЬНЫЙ УНИВЕРСИТЕТ» В Г. НАБЕРЕЖНЫЕ ЧЕЛНЫ ФАКУЛЬТЕТ ПМ и ИТ.

Специальность: 8 011 655

«Математические методы в экономике»

КУРСОВАЯ РАБОТА

«Реализация методов решения минимизации средневзвешенного суммарного штрафа на компьютере и разработка программы»

2010 г

• Введение 3
• 1.

  Введение

  в теорию расписаний 4

• 2. Постановка задачи 7
• 3. Методы решения задачи 8
• 3.1 Метод полного перебора 8
• 3.2 Метод оптимальной вставки 9
• 4. Генератор исходных данных для задачи 12
• 4.1 Алгоритм генератора исходных данных для задачи 12
• 4.2 Численный эксперимент 13
• 5. Описание работы приложения 15
• 5.1 Выбор языка программирования 15
• 5.2 Работа с приложением 16
• Заключение 19
• Литература 20
• Приложения 21

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

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

Как правило, одни и те же цели могут быть достигнуты различным образом, с различными затратами труда и материальных ресурсов. Выбрать наиболее экономичный и целесообразный путь, принять обоснованное, наиболее правильное решение — далеко не простая задача и для своего решения требует привлечения современных и научных методов. [1]

Целью данной курсовой работы является реализация методов решения минимизации средневзвешенного суммарного штрафа на компьютере и разработка программы.

Основные задачи:

Изучить методы решения задачи минимизации средневзвешенного суммарного штрафа, генератор исходных данных задачи;

Разработать алгоритмы решения задачи методами полного перебора и оптимальной вставки;

По данным алгоритмам составить программный код на Delphi;

Провести численный эксперимент составленных генератором задач.

задача минимизация алгоритм программа

1.

Введение

в теорию расписаний

Эти методы, которые принято объединять под общим названием «исследование операций». В настоящее время исследование операций — достаточно мощный инструмент количественного анализа сложных целенаправленных процессов, протекающих в различных сферах человеческой деятельности. Методы исследования операций способствуют выработке рациональных, обоснованных решений по управлению этими процессами.

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

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

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

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

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

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

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

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

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

Разнообразие моделей, степень их общности и универсальности постепенно увеличиваются, охватывая все более широкую сферу возможных приложений — календарное планирование производства, транспорта, военных операций, обучения, информационно — вычислительных процессов и т. п. По мере усложнения моделей усложняются и методы принятия плановых решений с использованием этих моделей. [2]

2. Постановка задачи

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

Через обозначим взаимный порядок обслуживания двух операций и; данная запись означает то, что операция выполняется ранее требования. Основной характеристикой выполнения операции () является момент окончания выполнения. Величина называется запаздыванием операции, величину суммарным запаздыванием расписания. Величина называется штрафом за запаздывание, тогда — средневзвешенный суммарный штраф расписания.

Таким образом, необходимо составить такое расписание, при котором будет выполняться следующее условие

такое расписание будем называть оптимальным. [2]

3. Методы решения задачи

3.1 Метод полного перебора

Метод полного перебора заключается в определении всевозможных расписаний и выявлением среди них оптимального.

Определение всевозможных расписаний реализуется перестановками операций в расписании. Количество различных перестановок операций в расписании, состоящего из элементов равно. В этом нетрудно убедиться: на первом месте в перестановке может стоять любой из операций расписания, после того, как мы на первом месте зафиксировали какой-либо элемент, на втором месте может стоять любой из оставшегося элемента и т. д. Таким образом, общее количество вариантов равно. То есть, метод полного перебора мы можем рассматривать только у расписаний, состоящих из не более чем 12 элементов, т.к. 12≠479 001 600. [3]

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

Алгоритм решения:

1. Получаем следующие исходные данные:

2. Считаем по формуле

;

3. Высчитываем величины

;

4. В качестве минимального суммарного штрафа записываем, а в оптимальное расписание запоминаем исходную последовательность расписаний;

5. Вызываем рекурсивную процедуру generate (1,n);

6. Вывод на форму значения и .

Процедура generate () перебирает всевозможные комбинации последовательностей операций и для каждой последовательности высчитывает величины. Если же, то в запоминаем соответствующую последовательность суммарному штрафу. Таким образом, при окончании процедуры generate () мы получаем и, причем не запоминая все комбинации последовательности операций.

3.2 Метод оптимальной вставки

Метод оптимальной вставки заключается в определении очередности операций расписаний и выявлением среди них оптимального расписания.

Этот метод содержит древовидный путь выбора оптимального расписания (см. рис. 1).

Метод оптимальной вставки имеет условие неубывания директивных сроков, , т. е.. [4]

Разберем алгоритм метода на основе рис. 1. Допустим, условие неубывания директивных сроков () выполняется.

1. Берем первые две операции и рассмотрим их очередности операций, т. е. и. Условием принятия выбора той или иной очередности операций является значение величины суммарного штрафа, т. е. выбирается та очередность операций, у которой суммарный штраф минимален. По рисунку видно, что выбрана очередность .

Рис. 1. Древовидный путь выбора оптимального решения.

2. Далее берется следующая по счету операция, третья. Производится вставка третьей операции во всевозможные позиции в расписании, но не нарушая очередность. И для полученных последовательностей операций: (1,2,3), (1,3,2), (3,1,2), вычисляется суммарный штраф, находим минимальный и выбор падает на очередность операций с минимальным суммарным штрафом.

3. Выполняем 2 итерацию до тех пор пока не будет построена очередность из операций.

4. Выводим на форму минимальный суммарный штраф и соответствующая ему очередность операций.

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

4. Генератор исходных данных для задачи

4.1 Алгоритм генератора исходных данных для задачи

Предлагаемый ниже генератор использует идею генерации исходных данных задачи для одной машины. 5]

В этой работе генерация исходных данных основана на двух параметрах: TF (tightness factor) и RDD (range of due dates), — имеющих для задачи следующий смысл:

, (*)

где, .

Алгоритм:

1. Выберем параметры TF и RDD из интервала .

2. Из целых чисел интервала случайно по равномерному закону выберем значения .

3. Из целых чисел интервала случайно по равномерному закону выберем значения, вычислим .

4. Из целых чисел интервала

случайно по равномерному закону выберем значения .

5. Положим, .

6. Вычисляем TF и RDD по формулам (*). Если разница между сгенерированными параметрами TF, RDD и сгенерированными TF, RDD соответственно <0.1, то считается что задача сгенерирована.

Заметим, что TF и RDD были введены как характеристики задачи, и с их помощью можно разбить множество задач на классы, задаваемые интервалами значений TF, RDD. Но в приведенном алгоритме они используются как управляющие параметры генератора. [6]

4.2 Численный эксперимент

Проведем анализ свойств предложенного выше генератора задач для одной машины. Чтобы отличать TF, RDD генератора и задачи, параметры генератора обозначим через TF_gen, RDD_gen, а параметры сгенерированной задачи TF_pr, RDD_pr.

Будем считать, что TF_pr, RDD_pr задачи соответствуют TF_gen, RDD_gen генератора с точностью, если

.

Необходимо провести эксперимент по выявлению соответствия параметров TF_gen, RDD_gen генератора, параметрам TF_pr, RDD_pr сгенерированных задач.

Схема эксперимента такова:

· TF_gen, RDD_gen независимо табулировались от 0.1 до 0.9 с шагом ;

· Для каждой пары TF_gen, RDD_gen было сгенерировано задач;

· Для каждой задачи были вычислены TF_pr, RDD_pr;

· Считается, что сгенерированная задача принадлежит своему классу, если ее TF_pr, RDD_pr соответствуют TF_gen, RDD_gen с точностью .

Значения в таблицах приведены в формате A / B / C, где

А — общее количество задач, оказавшихся в классе;

В — количество задач, сгенерированных при соответствующих параметрах TF_gen, RDD_gen, но не попавших в свой класс (ушедшие задачи);

С — количество задач, попавших в класс, но сгенерированных при несоответствующих классу параметрах TF_gen, RDD_gen (пришедшие задачи). [6]

Из табл. 1 видно, что классы (0,7;0,7), (0,9;0,5), (0,9;0,7), (0,9;0,9) совсем не соответствуют ожиданиям, так как большая часть сгенерированных задач уходит в другие классы. Это чревато тем, что выводы об эффективности методов на классах, потерявших и принявших много чужих задач, будут некорректными.

Таблица1: N=20, n=100.

5. Описание работы приложения

5.1 Выбор языка программирования

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

Среди пользователей персональных компьютеров в нашей стране наиболее популярно семейство операционных систем Windows.

Бурное развитие вычислительной техники, потребность в эффективных средствах разработки программного обеспечения привели к появлению систем программирования, ориентированных на так называемую «быструю разработку», среди которых можно выделить Borland Delphi и MS Visual Basic. В основе систем быстрой разработки (RAD-систем, Rapid Application Development-среда быстрой разработки приложений) лежит технология визуального проектирования и событийного программирования, суть которой заключается в том, что среда разработки берет на себя большую часть генерации кода программы, оставляя программисту работу по конструированию диалоговых окон и функций обработки событий.

Borland Delphi — это среда быстрой разработки, в которой в качестве языка программирования используется Object Pascal. В основе идеологии Delphi лежит технология визуального проектирования и методология объектно-ориентированного событийного программирования. [7]

Для написания программы решения задачи минимизации взвешенного суммарного штрафа использована среда программирования Delphi.

5.2 Работа с приложением

Данный курсовой проект был разработан в среде Delphi 7 с базовым языком программирования Delphi.

После запуска программы на экране появится основное окно приложения.

Ввод исходных данных может производиться вручную или выбрать пункт меню «Файл — Открыть».

Для ввода данных в ручную необходимо ввести значение величины и нажать кнопку «Решить». После этого заполнятся поля «tf (в начале)», «rdd (в начале)», «tf» и «rdd». Для того чтобы сгенерированная задача была решаемой необходимо, чтобы разница между «tf (в начале)» и «tf», и между «rdd (в начале)» и «rdd», была меньше 0,001.

Рис. 2 Главное окно приложения.

Если это условие выполняется, то нажать кнопку «Записать» (рис.3), после этого в нижней части окна приложения появится матрица исходных данных задачи: директивный срок (), продолжительность выполнения (), и штраф за запаздывание выполнения операции ().

Рис. 3. Подбор параметров генератора исходных данных задачи.

Рис. 4. Пример решения задачи минимизации средневзвешенного суммарного штрафа методом полного перебора.

Для решения задачи методами нужно перейти на соответствующие вкладки: «Полный перебор» и «Метод оптимальной вставки», и нажать кнопку «Решить» (рис. 4,5). При решении в поле минимального суммарного штрафа появится значение и отобразится оптимальное расписание.

Рис. 5. Пример решения задачи минимизации средневзвешенного суммарного штрафа методом оптимальной вставки.

Заключение

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

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

Я считаю, что поставленные задачи были решены, а именно:

1. Изучены методы решения задачи минимизации средневзвешенного суммарного штрафа, генератор исходных данных задачи;

2. Разработаны алгоритмы решения задачи методами полного перебора и оптимальной вставки;

3. Проведен численный эксперимент составленных генератором задач.

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

1. Танаев В. С., Шкурба В. В.

Введение

в теорию расписаний. — М.: Наука, 1975.

2. Танаев В. С., Гордон В. С., Шафранский Я. М. Теория Расписаний. Одностадийные системы. — М.: Наука, 1984.

3. Зиндер Я. А. Об алгоритмах решения некоторых задач упорядочения. — В кн.: Алгоритмы и программы. — Горький, 1977, вып. 1, с. 114−123.

4. Ириков В. А. Некоторые задачи упорядочения. -Изв. АН СССР. Техн. кибернетика, 1970, № 4, с. 38−42.

5. Сабиров Р. Г., Фазылов В. Р. О генераторе исходных данных для задачи минимизации суммарного взвешенного запаздывания. Учен. зап. Казан. ун-та. Сер. Физ.-матем. Науки, 2010.-Т.152, кн.1. — с.199−204.

6. Агапеевич И. К., Фазылов В. Р. Генератор исходных данных для задачи минимизации суммарного взвешенного запаздывания в конвейерных системах. — Исследования по прикладной математике и информатике, вып. 26.

7. Мухачева Э. А., Рубинтштейн Г. Ш. Математическое программирование. Новосибирск: наука, 1977. — 319 с.

Приложения

unit Unit1;

interface

uses

Windows, Messages, SysUtils, Variants, Classes, Graphics, Controls, Forms,

Dialogs, StdCtrls, ComCtrls, Menus, Grids;

type

mass=array[1.100]of integer;

matr=array[1.3,1.100]of integer;

matrica=array[1.100,1.100]of integer;

Tfrm_main = class (TForm)

PageControl1: TPageControl;

TabSheet1: TTabSheet;

TabSheet2: TTabSheet;

TabSheet3: TTabSheet;

Label1: TLabel;

edt_n: TEdit;

btn_resh: TButton;

edt_tfn: TEdit;

Label2: TLabel;

edt_rddn: TEdit;

Label3: TLabel;

Label4: TLabel;

Label5: TLabel;

edt_tfc: TEdit;

Label6: TLabel;

edt_rddc: TEdit;

Button1: TButton;

Label7: TLabel;

edt_summstraf: TEdit;

Label8: TLabel;

lbl_posl: TLabel;

Button2: TButton;

Label9: TLabel;

edt_summstr: TEdit;

lbl_posled: TLabel;

Button3: TButton;

StrGrd_matr: TStringGrid;

MainMenu1: TMainMenu;

N1: TMenuItem;

N2: TMenuItem;

N3: TMenuItem;

N4: TMenuItem;

StrGrd_sort: TStringGrid;

SaveDialog1: TSaveDialog;

Memo1: TMemo;

OpenDialog1: TOpenDialog;

Label10: TLabel;

procedure btn_reshClick (Sender: TObject);

procedure Button1Click (Sender: TObject);

procedure Button2Click (Sender: TObject);

procedure Button3Click (Sender: TObject);

procedure N4Click (Sender: TObject);

procedure N2Click (Sender: TObject);

procedure N3Click (Sender: TObject);

procedure FormActivate (Sender: TObject);

private

{ Private declarations }

public

{ Public declarations }

end;

var

frm_main: Tfrm_main;

wi, pi, di, ddi, mmassiv, minmas: mass;

i, j, n, m, kol, minstraf: integer;

mtr:matr;

implementation

uses Math;

{$R *.dfm}

procedure RandomChisla (nach, kol: integer;var mmas: mass);

begin

//рандомно записывает в массив числа

for i:=1 to n do

mmas[i]: =randomrange (nach, kol);

end;

function summ (kol:integer;mmas:mass):real;

var ss: real;

begin

//сумма элементов массива

ss:=0;

for i:=1 to kol do ss:=ss+mmas[i];

summ:=ss;

end;

procedure Tfrm_main.btn_reshClick (Sender: TObject);

var p, tf, tff, rdd, rddd: real;

a, b, kk, nn: real;

t:string;

max, min: integer;

begin

//случайно выбираем числа

tf:=random;

frm_main.edt_tfn.Text:=floattostr (tf);

rdd:=random;

frm_main.edt_rddn.Text:=floattostr (rdd);

n:=StrToInt (frm_main.edt_n.Text);

randomchisla (1,10,wi);

randomchisla (1,100,pi);

p:= summ (n, pi);

a:=p*(1-tf-(rdd/2));

b:=p*(1-tf+(rdd/2));

randomchisla (round (a), round (b), di);

for i:=1 to n do

begin

if (pi[i]>di[i])then ddi[i]: =pi[i];

if (pi[i]

end;

//нахождение максимума и минимума

max:=ddi[1];

min:=ddi[1];

for i:=1 to n do

begin

if (max

if (min>ddi[i])then min:=ddi[i];

end;

//считаем полученные tf rdd

kk:=summ (n, ddi);

nn:=n*p;

tff:=1-(kk/nn);

frm_main.edt_tfc.Text:=floattostr (tff);

rddd:=(max-min)/p;

frm_main.edt_rddc.Text:=floattostr (rddd);

end;

procedure Tfrm_main.Button1Click (Sender: TObject);

begin

//записывает полученную матрицу в таблицу

for i:=1 to n do

begin

mtr[1,i]: =ddi[i]; mtr[2,i]: =pi[i]; mtr[3,i]: =wi[i];

end;

frm_main.StrGrd_matr.RowCount:=4;

frm_main.StrGrd_matr.ColCount:=n+1;

frm_main.StrGrd_matr.Cells[0,1]: ='di';

frm_main.StrGrd_matr.Cells[0,2]:='pi';

frm_main.StrGrd_matr.Cells[0,3]:='wi';

for i:=1 to n do

begin

frm_main.StrGrd_matr.Cells[i, 0]: =inttostr (i);

frm_main.StrGrd_matr.Cells[i, 1]: =inttostr (mtr[1,i]);

frm_main.StrGrd_matr.Cells[i, 2]: =inttostr (mtr[2,i]);

frm_main.StrGrd_matr.Cells[i, 3]: =inttostr (mtr[3,i]);

end;

end;

procedure generate (l, r: integer);

var i, v, cc, s: integer;

c, t, ss:mass;

begin

if (l = r) then

begin

for j:=1 to 100 do

begin

c[j]: =0; t[j]: =0;

end;

cc:=0;

for j:=1 to n do

begin

c[mmassiv[j]]: =cc+mtr[2,mmassiv[j]];

cc:=c[mmassiv[j]];

end;

//выбор значений штрафа

for j:=1 to n do

begin

if (0 > (c[j]-mtr[1,j])) then t[j]: =0;

if (0 < (c[j]-mtr[1,j])) then t[j]: =c[j]-mtr[1,j];

end;

//подсчет суммарных штрафов для последовательности

s:=0;

for j:=1 to n do s:=s+t[j]*mtr[3,j];

if (minstraf>s)then

begin

minstraf:=s;

for j:=1 to n dominmas[j]: =mmassiv[j];

end;

end

else

begin

for i := l to r do

begin

v := mmassiv[l];

mmassiv[l] := mmassiv[i];

mmassiv[i] := v;

generate (l + 1, r); {вызов новой генерации}

v := mmassiv[l];

mmassiv[l] := mmassiv[i];

mmassiv[i] := v;

end;

end;

end;

procedure Tfrm_main.Button2Click (Sender: TObject);

var cc, s: integer;

c, t, ss, masmin: mass;

begin

//метод полного перебора

minstraf:=0;

for j:=1 to 100 do

begin

c[j]: =0; t[j]: =0;

end;

if (n>11)or (n<=0)then

MessageDlg ('Задача выполняет при 0

else

begin

for j:=1 to n do mmassiv[j]: =j;

//считаю сi

cc:=0;

for j:=1 to n do

begin

c[mmassiv[j]]: =cc+mtr[2,mmassiv[j]];

cc:=c[mmassiv[j]];

end;

//выбор значений штрафа

for j:=1 to n do

begin

if (0 > (c[j]-mtr[1,j])) then t[j]: =0;

if (0 < (c[j]-mtr[1,j])) then t[j]: =c[j]-mtr[1,j];

end;

//подсчет суммарных штрафов для последовательности

s:=0;

for j:=1 to n do s:=s+t[j]*mtr[3,j];

//нахождение минимума суммарных штрафов

minstraf:=s;

for j:=1 to n do minmas[j]: =mmassiv[j];

generate (1,n);

frm_main.edt_summstraf.Text:=inttostr (minstraf);

frm_main.lbl_posl.Caption:='';

for i:=1 to n do

frm_main.lbl_posl.Caption:=frm_main.lbl_posl.Caption + inttostr (minmas[i])+ ',';

end;

end;

procedure Tfrm_main.Button3Click (Sender: TObject);

var k, x, y, z, nom, znach, cc, s, min, nomin: integer;

sortmtr:matr;

nommtr, mtrmin: matrica;

mmas, c, t, ss, masmin, put: mass;

begin

//метод оптимальной вставки

if (n<=0)then

MessageDlg ('Задача выполняет при n>0', mtWarning,[mbOk], 0)

else

begin

// сортировка исходной матрицы с данными по возрастанию

frm_main.Label10.Caption:='';

for i:=1 to n do

begin

sortmtr[1,i]: =mtr[1,i]; sortmtr[2,i]: =mtr[2,i]; sortmtr[3,i]: =mtr[3,i];

end;

for i:=1 to n-1 do

begin

x:=sortmtr[1,i]; y:=sortmtr[2,i]; z:=sortmtr[3,i];

k:=i;

for j:=i+1 to n do

if (sortmtr[1,j]

begin

x:=sortmtr[1,j]; y:=sortmtr[2,j]; z:=sortmtr[3,j];

k:=j;

end;

sortmtr[1,k]: =sortmtr[1,i];

sortmtr[1,i]: =x;

sortmtr[2,k]: =sortmtr[2,i];

sortmtr[2,i]: =y;

sortmtr[3,k]: =sortmtr[3,i];

sortmtr[3,i]: =z;

end;

frm_main.StrGrd_sort.RowCount:=4;

frm_main.StrGrd_sort.ColCount:=n+1;

frm_main.StrGrd_sort.Cells[0,1]: ='di';

frm_main.StrGrd_sort.Cells[0,2]: ='pi';

frm_main.StrGrd_sort.Cells[0,3]: ='wi';

for i:=1 to n do

begin

frm_main.StrGrd_sort.Cells[i, 0]: =inttostr (i);

frm_main.StrGrd_sort.Cells[i, 1]: =inttostr (sortmtr[1,i]);

frm_main.StrGrd_sort.Cells[i, 2]: =inttostr (sortmtr[2,i]);

frm_main.StrGrd_sort.Cells[i, 3]: =inttostr (sortmtr[3,i]);

end;

//обнуление

for i:=1 to n do

begin

mmas[i]: =0; t[i]: =0;

ss[i]: =0; c[i]: =0;

end;

//Перестановка

nom:=2; //беру первые два столбца

while nom<=n do

begin

for i:=1 to nom do

begin

//получение всех возможные последовательности путем перестановки

for j:=1 to nom do

mmas[j]: =j;

znach:=mmas[i];

mmas[i]: =mmas[nom];

mmas[nom]: =znach;

for j:=1 to n do nommtr[i, j]: =mmas[j];

//подсчет сi

cc:=0;

for j:=1 to nom do

begin

c[mmas[j]]: =cc+sortmtr[2,mmas[j]];

cc:=c[mmas[j]];

end;

//подсчет штрафов

for j:=1 to nom do

begin

if (0 > (c[j]-sortmtr[1,mmas[j]])) then t[j]: =0;

if (0 < (c[j]-sortmtr[1,mmas[j]])) then t[j]: =c[j]-sortmtr[1,mmas[j]];

end;

//подсчет суммарных штрафов

s:=0;

for j:=1 to nom do s:=s+t[j]*sortmtr[3,j];

ss[i]: =s;

end;

//нахождение минимального суммарного штрафа

min:=ss[1];

for j:=1 to nom do

if (min>=ss[j])then

begin

min:=ss[j];

nomin:=j;

end;

for j:=1 to nom do put[j]: =nommtr[nomin, j];

masmin[nom-1]: = min;

nom:=nom+1;

end;

//вывод полученных данных

for i:=1 to n do

begin

frm_main.Label10.Caption:=frm_main.Label10.Caption + inttostr (put[i]) + ',';

end;

frm_main.edt_summstr.Text:=inttostr (masmin[nom-2]);

///конец else

end;

end;

procedure Tfrm_main.N4Click (Sender: TObject);

begin

frm_main.Close;

end;

procedure Tfrm_main.N2Click (Sender: TObject);

begin

//сохранение данных в файл на компьютере

if frm_main.SaveDialog1.Execute then

begin

frm_main.Memo1.Lines[0]: = inttostr (n);

kol:=0;

for j:=1 to 3 do

for i:=1 to n do

begin

frm_main.Memo1.Lines.Add (frm_main.StrGrd_matr.Cells[i, j]);

kol:=kol+1;

end;

frm_main.Memo1.Lines.SaveToFile (frm_main.SaveDialog1.FileName);

frm_main.Memo1.Clear;

end;

end;

procedure Tfrm_main.N3Click (Sender: TObject);

var r, ii: integer;

begin

//загрузка данных из файла и запись их в таблицу и в исходную матрицу

if frm_main.OpenDialog1.Execute then

begin

frm_main.Memo1.Clear;

frm_main.Memo1.Lines.LoadFromFile (frm_main.OpenDialog1.FileName);

frm_main.edt_n.Text:=frm_main.Memo1.Lines[0];

n:=strtoint (frm_main.edt_n.Text);

frm_main.StrGrd_matr.ColCount:=n+1;

frm_main.StrGrd_matr.RowCount:=4;

kol:=frm_main.Memo1.Lines.Count-1;

frm_main.StrGrd_matr.Cells[0,1]: ='di';

frm_main.StrGrd_matr.Cells[0,2]: ='pi';

frm_main.StrGrd_matr.Cells[0,3]: ='wi';

for i:=1 to n do

frm_main.StrGrd_matr.Cells[i, 0]: =inttostr (i);

r:=1;

ii:=1;

while r<=3 do

begin

for i:=1 to n do

begin

frm_main.StrGrd_matr.Cells[i, r]: =frm_main.Memo1.Lines[ii];

if ii=n*r then

begin

ii:=n*r+1;

break;

end;

ii:=ii+1;

end;

r:=r+1;

end;

for i:=1 to 3 do

for j:=1 to n do

mtr[i, j]: =strtoint (frm_main.StrGrd_matr.Cells[j, i]);

end;

end;

procedure Tfrm_main.FormActivate (Sender: TObject);

begin

frm_main.PageControl1.ActivePage:=TabSheet1;

end;

end.