Решение задачи о минимизации средневзвешенного суммарного штрафа для одной машины
Методы исследования операций для количественного анализа сложных целенаправленных процессов. Решение задач методом полного перебора и оптимальной вставки (определение всевозможных расписаний, их очередности, выбор оптимального). Генератор исходных данных.
| Рубрика | Математика |
| Вид | курсовая работа |
| Язык | русский |
| Дата добавления | 01.05.2011 |
| Размер файла | 476,3 K |
Отправить свою хорошую работу в базу знаний просто. Используйте форму, расположенную ниже
Студенты, аспиранты, молодые ученые, использующие базу знаний в своей учебе и работе, будут вам очень благодарны.
Размещено на http://www.allbest.ru/
Размещено на http://www.allbest.ru/
ФИЛИАЛ ГОСУДАРСТВЕННОГО АВТОНОМНОГО ОБРАЗОВАТЕЛЬНОГО УЧРЕЖДЕНИЯ ВЫСШЕГО ПРОФЕССИОНАЛЬНОГО ОБРАЗОВАНИЯ «КАЗАНСКИЙ (ПРИВОЛЖСКИЙ) ФЕРЕДАЛЬНЫЙ УНИВЕРСИТЕТ» В
Г. НАБЕРЕЖНЫЕ ЧЕЛНЫ
ФАКУЛЬТЕТ ПМ и ИТ.
Специальность: 08011655
«Математические методы в экономике»
КУРСОВАЯ РАБОТА
«Решение задачи о минимизации
средневзвешенного суммарного штрафа для
одной машины»
2010 г
Введение
Расширение масштабов современного производства, усложнение уровня проводимых мероприятий, необходимость координации деятельности больших коллективов людей существенно усложнили функции организационного производства.
В различных областях целенаправленной человеческой деятельности, в сложных, зачастую противоречивых условиях приходится принимать решения, нередко связанные с людьми и большими материальными затратами. Принимаемые решения всегда направлены на достижение некоторых целей и реализуется в рамках некоторой системы ограничений, обусловленных конкретными обстоятельствами проведения мероприятия.
Как правило, одни и те же цели могут быть достигнуты различным образом, с различными затратами труда и материальных ресурсов. Выбрать наиболее экономичный и целесообразный путь, принять обоснованное, наиболее правильное решение - далеко не простая задача и для своего решения требует привлечения современных и научных методов.
Целью данной курсовой работы является реализация методов решения минимизации средневзвешенного суммарного штрафа на компьютере и разработка программы.
Основные задачи:
Изучить методы решения задачи минимизации средневзвешенного суммарного штрафа, генератор исходных данных задачи;
Разработать алгоритмы решения задачи методами полного перебора и оптимальной вставки;
По данным алгоритмам составить программный код на Delphi;
Провести численный эксперимент составленных генератором задач.
1. Введение в теорию расписаний
Эти методы, которые принято объединять под общим названием «исследование операций». В настоящее время исследование операций - достаточно мощный инструмент количественного анализа сложных целенаправленных процессов, протекающих в различных сферах человеческой деятельности. Методы исследования операций способствуют выработке рациональных, обоснованных решений по управлению этими процессами.
При операционном подходе к поиску наиболее эффективных путей достижения цели осуществляется построение математической модели, содержащей описание этой цели и отражающей условия проведения операции. На этом этапе тщательно анализируется содержание операции, определяются необходимые действия, выделяются условия их выполнения, оцениваются разнообразные ограничения и т.п. Методология исследования операций позволяет систематизировать всю эту работу, придать ей большую целенаправленность и определенность.
Оценка и сравнение эффективности возможных способов действий при достижении поставленной цели проводятся на основании построенной модели. Эта же модель позволяет принять и наилучшее в рассматриваемой ситуации решение. В большинстве случаев выработка такого решения требует привлечения соответствующих математических методов оптимизации и сопряжена с большим объемом вычислений.
Анализируемые в рамках исследований операций модели являются разумным компромиссом между двумя естественными, но противоречивыми тенденциями. С одной стороны, желательно, чтобы модель возможно полнее отражала реальные процессы, с другой - она должна быть настолько простой, чтобы можно было получить искомые результаты за практически приемлемое время. Постоянное развитие математических методов и вычислительной техники позволяет расширить круг анализируемых моделей и тем самым расширить сферу практического применения методов исследования операций.
С использованием операционного подхода оказалось возможным разработать эффективную методику управления транспортными перевозками, решить ряд задач распределения ресурсов и размещения производительных сил, выработать наилучшие стратегии управления запасами и т.д.
В середине 50-х годов начались интенсивные исследования по построению и анализу моделей календарного планирования и разработке методов принятия плановых решений с использованием этих моделей. Среди причин, вызвавших появления этого нового направления в исследовании операции, в первую очередь следует отметить все возрастающую необходимость планирования и управления сложными разработками, включающими большое число взаимосвязанных работ, требующих многочисленных исполнителей и значительных материальных затрат.
Все отчетливее осознавалось, что качество функционирования современного производства во многом определяется качеством решений, принимаемых на этапах календарного планирования и оперативного управления. Наряду с улучшением качества плановых решений необходимо было также сократить сроки их выработки, повысить оперативность и гибкость управления.
Временная увязка всего множества действий, сопряженных с достижением заданной цели, уже сама по себе достаточно сложная задача. Если же речь идет о построении наилучшего календарного плана, да еще в кратчайший срок, то сложность этой задачи неизмеримо возрастает.
Круг вопросов, связанных с построением наилучших календарных планов (расписаний), особенно с разработкой математических методов получения решений с использованием соответствующих моделей, изучается в рамках теории расписаний.
Эта теория использует характерный для исследования операций модельный подход к анализу реальных процессов. Изучаемые в теории расписаний модели отражают специфические ситуации, возникающие при календарном планировании различных видов человеческой деятельности.
Разнообразие моделей, степень их общности и универсальности постепенно увеличиваются, охватывая все более широкую сферу возможных приложений - календарное планирование производства, транспорта, военных операций, обучения, информационно - вычислительных процессов и т.п. По мере усложнения моделей усложняются и методы принятия плановых решений с использованием этих моделей.
оптимальный исследование операция расписание
2. Постановка задачи
Задача минимизации средневзвешенного суммарного штрафа за выполнение набора операций одной машиной. Необходимо обслужить операций на одной машине. Операции пронумерованы числами . Все операции поступают на выполнение одновременно. Выполнение более одной операции в любой момент времени запрещено. Задан момент начала выполнения , с которого машина готова начать выполнение операций.
Для операции () заданы следующие параметры: продолжительность выполнения , директивный срок окончания выполнения .
Через обозначим взаимный порядок обслуживания двух операций и ; данная запись означает то, что операция выполняется ранее требования . Основной характеристикой выполнения операции () является момент окончания выполнения
Величин
называется запаздыванием операции , величину
суммарным запаздыванием расписания. Величина называется штрафом за запаздывание, тогда
- средневзвешенный суммарный штраф расписания. Таким образом, необходимо составить такое расписание, при котором будет выполняться следующее условие
такое расписание будем называть оптимальным.
3. Методы решения задачи
3.1 Метод полного перебора
Метод полного перебора заключается в определении всевозможных расписаний и выявлением среди них оптимального.
Определение всевозможных расписаний реализуется перестановками операций в расписании. Количество различных перестановок операций в расписании, состоящего из элементов равно . В этом нетрудно убедиться: на первом месте в перестановке может стоять любой из операций расписания, после того, как мы на первом месте зафиксировали какой-либо элемент, на втором месте может стоять любой из оставшегося элемента и т.д. Таким образом, общее количество вариантов равно . То есть, метод полного перебора мы можем рассматривать только у расписаний, состоящих из не более чем 12 элементов, т.к. 12!=479001600. Метод полного перебора является самым точным из методов нахождения оптимального расписания, однако, как говорилось ранее, имеет недостатки, такие как большая трудоемкость вычислений и заполнение большого объема оперативной памяти компьютера. Алгоритм решения:
1. Получаем следующие исходные данные
|
j |
1 |
2 |
… |
n |
|
|
dj |
d1 |
d2 |
… |
dn |
|
|
pj |
p1 |
p2 |
… |
pn |
|
|
wj |
w1 |
w2 |
… |
wn |
2. Считаем по формуле
3. , ;
4. Высчитываем величины
,
5. В качестве минимального суммарного штрафа записываем
а в оптимальное расписание запоминаем исходную последовательность расписаний;
6. Вызываем рекурсивную процедуру generate(1,n);
7. Вывод на форму значения
и
Процедура generate() перебирает всевозможные комбинации последовательностей операций и для каждой последовательности высчитывает величины
Если же , то в запоминаем соответствующую последовательность суммарному штрафу . Таким образом, при окончании процедуры generate() мы получаем и , причем не запоминая все комбинации последовательности операций.
3.2 Метод оптимальной вставки
Метод оптимальной вставки заключается в определении очередности операций расписаний и выявлением среди них оптимального расписания.
Этот метод содержит древовидный путь выбора оптимального расписания (см. рис. 1).
Метод оптимальной вставки имеет условие неубывания директивных сроков
, , т. е.
Разберем алгоритм метода на основе рис. 1. Допустим, условие неубывания директивных сроков () выполняется.
1. Берем первые две операции и рассмотрим их очередности операций, т. е. и . Условием принятия выбора той или иной очередности операций является значение величины суммарного штрафа, т. е. выбирается та очередность операций, у которой суммарный штраф минимален. По рисунку видно, что выбрана очередность .
Размещено на http://www.allbest.ru/
Размещено на http://www.allbest.ru/
Рис. 1. Древовидный путь выбора оптимального решения
2. Далее берется следующая по счету операция, третья. Производится вставка третьей операции во всевозможные позиции в расписании, но не нарушая очередность . И для полученных последовательностей операций: (1,2,3), (1,3,2), (3,1,2), вычисляется суммарный штраф, находим минимальный и выбор падает на очередность операций с минимальным суммарным штрафом.
3. Выполняем 2 итерацию до тех пор пока не будет построена очередность из операций.
4. Выводим на форму минимальный суммарный штраф и соответствующая ему очередность операций.
Ясно, что при сравнении двух приведенных методов, результаты метода оптимальной вставки хуже, чем у метода полного перебора. Однако метод оптимальной вставки имеет преимущество в быстродействии в составлении расписания из большого количества операций.
4. Генератор исходных данных для задачи
4.1 Алгоритм генератора исходных данных для задачи
Предлагаемый ниже генератор использует идею генерации исходных данных задачи для одной машины.
В этой работе генерация исходных данных основана на двух параметрах: 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. Но в приведенном алгоритме они используются как управляющие параметры генератора.
4.2 Численный эксперимент
Проведем анализ свойств предложенного выше генератора задач для одной машины. Чтобы отличать TF, RDD генератора и задачи, параметры генератора обозначим через TFgen, RDDgen, а параметры сгенерированной задачи TFpr, RDDpr.
Будем считать, что TFpr, RDDpr задачи соответствуют TFgen, RDDgen генератора с точностью , если
,
Необходимо провести эксперимент по выявлению соответствия параметров TFgen, RDDgen генератора, параметрам TFpr, RDDpr сгенерированных задач. Схема эксперимента такова
· TFgen, RDDgen независимо табулировались от 0.1 до 0.9 с шагом ;
· Для каждой пары TFgen, RDDgen было сгенерировано задач;
· Для каждой задачи были вычислены TFpr, RDDpr;
· Считается, что сгенерированная задача принадлежит своему классу, если ее TFpr, RDDpr соответствуют TFgen, RDDgen с точностью .
Значения в таблицах приведены в формате A / B / C, где
А - общее количество задач, оказавшихся в классе;
В - количество задач, сгенерированных при соответствующих параметрах TFgen, RDDgen, но не попавших в свой класс (ушедшие задачи);
С - количество задач, попавших в класс, но сгенерированных при несоответствующих классу параметрах TFgen, RDDgen (пришедшие задачи). [6]
Из табл. 1 видно, что классы (0,7;0,7), (0,9;0,5), (0,9;0,7), (0,9;0,9) совсем не соответствуют ожиданиям, так как большая часть сгенерированных задач уходит в другие классы. Это чревато тем, что выводы об эффективности методов на классах, потерявших и принявших много чужих задач, будут некорректными.
Таблица1: N=20, n=100.
|
TFgen\ RDDgen |
0.1 |
0.3 |
0.5 |
0.7 |
0.9 |
|
|
0.1 |
20/ 0 / 0 |
20 / 0 / 0 |
20 / 0 / 0 |
20 / 0 / 0 |
18 / 2 / 0 |
|
|
0.3 |
20 / 0 / 0 |
20 / 0 / 0 |
20 / 0 / 0 |
20/ 0 / 0 |
18/ 2 / 0 |
|
|
0.5 |
20 / 0 / 0 |
20 / 0 / 0 |
20 / 0 / 0 |
20 / 0 / 0 |
18 / 2 / 0 |
|
|
0.7 |
20 / 0 / 0 |
20 / 0 / 0 |
20 / 0 / 0 |
7 / 13 / 0 |
11/ 8 / 0 |
|
|
0.9 |
20 / 0 / 0 |
14 / 6 / 8 |
0 / 20 / 9 |
0 / 20 / 0 |
0 / 20 / 0 |
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]<di[i])then ddi[i]:=di[i];
end;
//нахождение максимума и минимума
max:=ddi[1];
min:=ddi[1];
for i:=1 to n do
begin
if(max<ddi[i])then max:=ddi[i];
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<n<=11',mtWarning,[mbOk],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]<x)then
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.
Размещено на Allbest.ru
Подобные документы
Суть задачи коммивояжера, ее применение. Общая характеристика методов ее решения: метод полного перебора, "жадные" методы, генетические алгоритмы и их обобщения. Особенности метода ветвей и границ и определение наиболее оптимального решения задачи.
курсовая работа [393,2 K], добавлен 18.06.2011Численные методы поиска безусловного экстремума. Задачи безусловной минимизации. Расчет минимума функции методом покоординатного спуска. Решение задач линейного программирования графическим и симплексным методом. Работа с программой MathCAD.
курсовая работа [517,9 K], добавлен 30.04.2011Математическая модель задачи. Решение транспортной задачи методом потенциалов. Значение целевой функции. Система, состоящая из 7 уравнений с 8-ю неизвестными. Решение задач графическим методом. Выделение полуплоскости, соответствующей неравенству.
контрольная работа [23,5 K], добавлен 12.06.2011Графическое решение задачи линейного программирования. Общая постановка и решение двойственной задачи (как вспомогательной) М-методом, правила ее формирования из условий прямой задачи. Прямая задача в стандартной форме. Построение симплекс таблицы.
задача [165,3 K], добавлен 21.08.2010Составление математической модели задачи. Определение всевозможных способов распила 5-метровых бревен на брусья 1,5, 2,4, 3,2 в отношении 1:2:3 так, чтобы минимизировать общую величину отходов. Решение задачи линейного программирования симплекс-методом.
задача [26,1 K], добавлен 27.11.2015Сущность понятия "дифференциальное уравнение". Главные этапы математического моделирования. Задачи, приводящие к решению дифференциальных уравнений. Решение задач поиска. Точность маятниковых часов. Решение задачи на определение закона движения шара.
курсовая работа [918,7 K], добавлен 06.12.2013О происхождении задачи удвоения куба (одной из пяти знаменитых задач древности). Первая известная попытка решения задачи, решение Архита Тарентского. Решение задачи в Древней Греции после Архита. Решения с помощью конических сечений Менехма и Эратосфена.
реферат [630,3 K], добавлен 13.04.2014Основные сведения о симплекс-методе, оценка его роли и значения в линейном программировании. Геометрическая интерпретация и алгебраический смысл. Отыскание максимума и минимума линейной функции, особые случаи. Решение задачи матричным симплекс-методом.
дипломная работа [351,2 K], добавлен 01.06.2015Решение первой задачи, уравнения Пуассона, функция Грина. Краевые задачи для уравнения Лапласа. Постановка краевых задач. Функции Грина для задачи Дирихле: трехмерный и двумерный случай. Решение задачи Неймана с помощью функции Грина, реализация на ЭВМ.
курсовая работа [132,2 K], добавлен 25.11.2011Формирование нижних и верхних оценок целевой функции. Алгоритм метода ветвей и границ, решение задач с его помощью. Решение задачи коммивояжера методом ветвей и границ. Математическая модель исследуемой задачи, принципы ее формирования и порядок решения.
курсовая работа [153,2 K], добавлен 25.11.2011
