Реализация целочисленного программирования (метод Гомори)

 

МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РОССИЙСКОЙ ФЕДЕРАЦИИ

"САХАЛИНСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ"

САХАЛИНСКИЙ КОЛЛЕДЖ БИЗНЕСА И ИНФОРМАТИКИ

Курсовой проект

По дисциплине Математические Методы

Тема: Реализация целочисленного программирования (метод Гомори)

алгоритм гомори компьютерный программирование

Студента:

Токарева Игоря Вячеславовича

Форма обучения: Очная

Научный руководитель:

Сливчак С.И.

Южно-Сахалинск

Содержание

Оглавление

Введение

Глава 1. Метод Гомори

1.1 Экономическая сущность задачи

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

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

.4 Функциональные тесты

Глава 2. Моделирование, алгоритмизация и программирование метода

2.1 Математическая модель задачи

.2 Входные - выходные данные задачи

.3 Блок - схема решения задачи

.4 Тестирование

Глава 3. Руководство пользователя

Заключение

Список литературы

Приложение

Введение

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

Среди практически важных задач отыскания условного экстремума линейной функции важное место занимают задачи с требованием целочисленности всех (части) переменных. Они получили название задач целочисленного (частично целочисленного) программирования.

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

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

Цель курсового проекта: реализовать в среде разработки borland delphi 7 решение задач целочисленного программирования методом гомори.

Задачи курсовой работы:

·Изучить предметную область ЗЦП

·Определить входные, выходные данные задач линейного программирования

·Определить метод решения целочисленного программирования

·Выполнить структурное программирование задачи

·Спроектировать интерфейсные формы "Gomori"

·Разработать программный продукт "Gomori"

·Произвести анализ надежности и качества ПП "Gomori"

Глава 1. Метод Гомори

.1 Экономическая сущность задачи

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

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

Постановка задачи на максимум выглядит следующим образом:

При производстве n видов продукции используется m видов ресурсов. Известно: b1, b2, …, bm - запасы ресурсов; aij (i=1, 2, …, m; j=1, 2, …, n)- расход каждого i-го вида ресурса на изготовление единицы j-й продукции; cj (j=1, 2, …, n)- прибыль, получаемая при реализации единицы j-й продукции. Составить план выпуска продукции, обеспечивающий максимальную прибыль. Ответ должен иметь целочисленные значения.

Постановка задачи на минимум выглядит следующим образом:

Животные должны получать ежедневно m питательных веществ в количестве не менее b1, b2, …, bm. В рацион животных входят корма n видов. Известно: aij (i=1, 2, …, m; j=1, 2, …, n)- содержание i-го питательного вещества в единице j-го вида корма; cj (j=1, 2, …, n)- стоимость единицы j-го вида корма. Составить суточный рацион кормления животных, обеспечивающий минимальные затраты. Ответ должен иметь целочисленные значения.

1.3 Метод решения задач

Согласно методу Гомори задача линейного программирования сначала решается симплексным методом без учета целочисленности переменных

1)Поставленную описательную задачу переводят в математическую форму (целевая функция и ограничения).

2)Полученное математическое описание приводят к канонической форме.

)Каноническую форму приводят к матричному виду.

)Ищут первое допустимое решение. Для этого матрица должна быть правильной. Матрица в ЗЛП называется правильной, если она содержит минимум m правильных (базисных) столбцов, где m - число строк в матрице. Столбец в канонической ЗЛП называется правильным (базисным), если все его элементы равны нулю, кроме единственного равного единице.

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

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

)Составление дополнительного ограничения (сечения) и решение расширенной задачи обычным симплекс-методом. Дополнительное ограничение (сечение) отсекает нецелочисленные решения.

1.4 Функциональные тесты

Задача 1

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

Определим максимальное значение целевой функции F(X) = 16x1 + 9x2 при следующих условиях-ограничений.

5x1 + 2x2?201 + x2?6

Для построения первого опорного плана систему неравенств приведем к системе уравнений путем введения дополнительных переменных .В 1-м неравенстве смысла (?) вводим базисную переменную x3. В 2-м неравенстве смысла (?) вводим базисную переменную x4.

5x1 + 2x2 + 1x3 + 0x4 = 20

x1 + 1x2 + 0x3 + 1x4 = 6

Матрица коэффициентов A = a(ij) этой системы уравнений имеет вид:

БазисBx1x2x3x4x3205210x461101F(X0)0-16-900БазисBx1x2x3x4x32052104x4611016F(X1)0-16-9000БазисBx1x2x3x4minx1412/51/5010x4203/5-1/5131/3F(X2)640-23/531/500БазисBx1x2x3x4x122/3101/3-2/3x231/301-1/312/3F(X3)722/30021/341/3

Оптимальный план можно записать так:

x1 = 22/32 = 31/3(X) = 1622/3 + 931/3 = 722/3

В Оптимальном векторе есть нецелые числа, следует применить метод Гомори

БазисBx1x2x3x4x5x122/3101/3-2/30x231/301-1/312/30x5-2/300-1/3-1/31F(X0)-722/300-21/3-41/30БазисBx1x2x3x4x5x122/3101/3-2/30x231/301-1/312/30x5-2/300-1/3-1/31F(X)-722/300-21/341/30?0 - - -21/3 : (-1/3) = 7-41/3 : (-1/3) = 13 - БазисBx1x2x3x4x5x12100-11x240102-1x320011-3F(X0)-68000-2-7БазисBx1x2x3x4x5x12100-11x240102-1x320011-3F(X0)-68000-2-7

Решение получилось целочисленным. Оптимальный целочисленный план можно записать так:

Fопт(X) = 68, Хопт(2; 4)

Задача 2

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

Определим максимальное значение целевой функции F(X) = 7x1 + 9x2 при следующих условиях-ограничений.

- x1 + 3x2?6

x1 + x2?35

Для построения первого опорного плана систему неравенств приведем к системе уравнений путем введения дополнительных переменных (переход к канонической форме). В 1-м неравенстве смысла (?) вводим базисную переменную x3. В 2-м неравенстве смысла (?) вводим базисную переменную x4.

-1x1 + 3x2 + 1x3 + 0x4 = 6

x1 + 1x2 + 0x3 + 1x4 = 35

Матрица коэффициентов A = a(ij) этой системы уравнений имеет вид:

БазисBx1x2x3x4x36-1310x4357101F(X0)0-7-900БазисBx1x2x3x4x36-13102x435710135F(X1)0-7-9000БазисBx1x2x3x4minx22-1/311/30-x43371/30-1/3141/2F(X2)18-100300БазисBx1x2x3x4x231/2017/221/22x141/210-1/223/22F(X3)630026/1114/11

Оптимальный план можно записать так:

x2 = 31/21 = 41/2(X) = 931/2 + 741/2 = 63

В Оптимальном векторе есть нецелые числа, следует применить метод Гомори

БазисBx1x2x3x4x5x231/2017/221/220x141/210-1/223/220x5-1/200-7/22-1/221F(X0)-6300-26/11-14/110БазисBx1x2x3x4x5x231/2017/221/220x141/210-1/223/220x5-1/200-7/22-1/221F(X)-6300-26/11-14/110?0- - -26/11 : (-7/22) = 8-14/11 : (-1/22) = 30 - БазисBx1x2x3x4x5x2301001x144/71001/7-1/7x314/70011/7-31/7F(X0)-59000-1-8БазисBx1x2x3x4x5x2301001x141000-1x310010-4x4400016F(X0)-550000-2

Решение получилось целочисленным. Оптимальный целочисленный план можно записать так:

Fопт(X) = 55, Хопт(4; 3)

Задача 3

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

Определим максимальное значение целевой функции F(X) = 7x1 + 3x2 при следующих условиях-ограничений.

5x1 + 2x2?20

x1 + 4x2?38

Для построения первого опорного плана систему неравенств приведем к системе уравнений путем введения дополнительных переменных (переход к канонической форме).

В 1-м неравенстве смысла (?) вводим базисную переменную x3. В 2-м неравенстве смысла (?) вводим базисную переменную x4.

5x1 + 2x2 + 1x3 + 0x4 = 20

x1 + 4x2 + 0x3 + 1x4 = 38

Матрица коэффициентов A = a(ij) этой системы уравнений имеет вид:

БазисBx1x2x3x4x3205210x4388401F(X0)0-7-300БазисBx1x2x3x4minx32052104x438840143/4F(X1)0-7-3000БазисBx1x2x3x4minx1412/51/5010x4604/5-13/5171/2F(X2)280-1/512/500БазисBx1x2x3x4x11101-1/2x271/201-211/4F(X3)291/20011/4

Оптимальный план можно записать так:

x1 = 12 = 71/2(X) = 71 + 371/2 = 291/2

В Оптимальном векторе есть нецелые числа, следует применить метод Гомори

БазисBx1x2x3x4x5x11101-1/20x271/201-211/40x5-1/2000-1/41F(X0)-291/200-1-1/40БазисBx1x2x3x4x5x11101-1/20x271/201-211/40x5-1/2000-1/41F(X)-291/200-1-1/40?0 - - - -1/4 : (-1/4) = 1 - БазисBx1x2x3x4x5x121010-2x2501-205x420001-4F(X0)-2900-10-1

Решение получилось целочисленным. Оптимальный целочисленный план можно записать так:

Fопт(X) = 29, Хопт(2; 5)

Глава 2. Моделирование, алгоритмизация и программирование метода

2.1 Математическая модель задачи

Необходимо найти максимум или минимум функции

при условиях

где Z - множество целых чисел.

Для решения задачи ЦЛП может быть применен метод Гомори.

Метод Гомори содержит два этапа.

Этап 1. Решение исходной задачи обычным симплекс-методом и проверка решения на целочисленноесть. Если решение содержит хотя бы одно дробное значение, то переходят к этапу 2, в противном случае расчет заканчивается.

Этап 2. Составление дополнительного ограничения (сечения) и решение расширенной задачи обычным симплекс-методом. Дополнительное ограничение (сечение) отсекает нецелочисленные решения. Сечение обладает следующими двумя свойствами:

) любое целочисленное решение ему удовлетворяет;

) любое не целочисленное решение задачи ему не удовлетворяет.

Объясним, как составляется сечение.

Пусть выполнен этап 1;

- дробное число.

Рассмотрим i-е ограничение:

bi = xi +aim+lxm+1 +aim+2xm+2+…+ainxn .

Так как bi - дробное, а в правой части все переменные целые, хотя бы одно значение aij, должно быть дробным.

Возьмем дробную часть от левой и правой частей ограничения.

Обозначим через {r} дробную часть числа r.

Дробная часть суммы не превосходит суммы дробных частей слагаемых, поэтому

Дробная часть произведения не превосходит произведения целого на дробную часть, следовательно:

В результате имеем

Обозначим

Тогда из последнего неравенства получаем

Отняв от левой части неравенства дополнительную неотрицательную переменную, переходим к уравнению

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

Эту задачу решают обычным симплекс-методом, т.е. переходя к этапу 1.

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

2.2 Входные - выходные данные задачи

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

2.3 Блок - схема решения задачи

2.4 Тестирование

Для проверки правильности работы разрабатываемого продукта, проведем тестирование по ранее решенным задачам в главе 1.

Задача 1

Определим максимальное значение целевой функции F(X) = 16x1 + 9x2 при следующих условиях-ограничений.

5x1 + 2x2?201 + x2?6

Ответ при ручном способе: Fопт(X) = 68, Хопт(2; 4)

Задача 2

Определим максимальное значение целевой функции F(X) = 7x1 + 9x2 при следующих условиях-ограничений.

- x1 + 3x2?6

x1 + x2?35

Ответ при ручном способе: Fопт(X) = 55, Хопт(4; 3)

Задача 3

Определим максимальное значение целевой функции F(X) = 7x1 + 3x2 при следующих условиях-ограничений.

5x1 + 2x2?20

x1 + 4x2?38

Ответ при ручном способе: Fопт(X) = 29, Хопт(2; 5)

Сопоставив ответы при решении ручным способом и разрабатываемым продуктом, было доказана правильность работы программного продукта.

Глава 3. Руководство пользователя

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

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

После этого активируется кнопка "Найти симплекс решение", которое найдет, если в данной задачи линейного программирования есть оптимальное решение (Рисунок 3).

Если же решения нет появится диалоговое окно

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

Заключение

Для достижения поставленной цели потребовалось реализовать алгоритмы Гомори на языке программирования Object Pascal. При использовании среды разработки Borland Delphi 7.

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

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

Проверка качества разрабатываемого продукта была проведена с помощью "сборника задач по высшей математике для экономистов" под редакцией проф. В.И. Ермакова, откуда были взяты десять задач и ответы к ним. Решив эти задачи с помощью разрабатываемого продукта, было получено 8 совпадений, таким образом, коофицент качества составил .

В ходе курсового проекта были выполнены все поставленные задачи и была достигнута основная цель.

Список литературы

1.Алгоритм Гомори//Википедия. [Электронный ресурс]. URL:#"justify">Приложение

Unit1;, Messages, SysUtils, Variants, Classes, Graphics, Controls, Forms,, StdCtrls, ComCtrls, Grids, Spin, ExtCtrls, jpeg, XPMan;= class(TForm): TStringGrid;: TSpinEdit;: TLabel;: TStringGrid;: TSpinEdit;: TLabel;: TButton;: TStringGrid;: TButton;: TRadioGroup;: TLabel;: TButton;: TSpinEdit;: TLabel;: TLabel;: TLabel;: TLabel;: TLabel;: TGroupBox;: TLabel;: TLabel;_str: TStringGrid;: TButton;: TXPManifest;: TLabel;SpinEdit1Change(Sender: TObject);SpinEdit2Change(Sender: TObject);FormCreate(Sender: TObject);Button2Click(Sender: TObject);Button1Click(Sender: TObject);Button3Click(Sender: TObject);ChelevayaKeyPress(Sender: TObject; var Key: Char);Button4Click(Sender: TObject);

{ Private declarations }

{ Public declarations };: TForm1;,j,str_um,stolb_um,minmax_zn:Integer;_za:real;Math;

{$R *.dfm}

procedure TForm1.SpinEdit1Change(Sender: TObject);REshenie doi:=0 to colcount-1 doj:=0 to rowcount-1 do[i,j]:='';StringGrid1 doi:=0 to colcount-1 doj:=1 to rowcount-1 do[i,j]:='';Chelevaya doi:=0 to colcount-1 doj:=1 to rowcount-1 do[i,j]:='';.Cells[0,1]:='Ci';.Cells[1,1]:='Áï';.ColCount:=SpinEdit1.Value;.ColCount:=SpinEdit1.Value+SpinEdit2.Value+3;.ColCount:=SpinEdit1.Value+2;.Cells[SpinEdit1.Value-1,0]:='X'+IntToStr(SpinEdit1.Value);.Cells[SpinEdit1.Value-1,0]:='X'+IntToStr(SpinEdit1.Value);.Cells[SpinEdit1.Value,0]:='Çíàê';.Cells[SpinEdit1.Value+1,0]:='#';_um:=REshenie.RowCount;_um:=REshenie.ColCount;;TForm1.SpinEdit2Change(Sender: TObject);REshenie doi:=0 to colcount-1 doj:=0 to rowcount-1 do[i,j]:='';.Cells[0,1]:='Ci';.Cells[1,1]:='Áï';.RowCount:=SpinEdit2.Value+1;.ColCount:=SpinEdit1.Value+SpinEdit2.Value+3;.RowCount:=SpinEdit2.Value+3;_um:=REshenie.RowCount;_um:=REshenie.ColCount;;TForm1.FormCreate(Sender: TObject);_um:=REshenie.RowCount;_um:=REshenie.ColCount;.Cells[0,0]:='X1';.Cells [1,0]:='X2';.Cells[0,0]:='X1';.Cells[1,0]:='X2';.Cells[2,0]:='Çíàê';.Cells [3,0]:='#';.Cells[0,1]:='Ci';.Cells[1,1]:='Áï';;TForm1.Button2Click(Sender: TObject);stolb,strok:Integer;,d:real;.Visible:=true;.RowCount:=str_um;.ColCount:=stolb_um;

with REshenie doi:=0 to colcount-1 doj:=0 to rowcount-1 do[i,j]:='';i:=2 to REshenie.ColCount-1 doj:=0 to REshenie.RowCount-1 do.Cells[i,j]:='0';.Cells[0,1]:='Ci';.Cells[1,1]:='Áï';i:=2 to REshenie.RowCount-2 do.Cells[0,i]:='0';strok:=1 to SpinEdit2.Value+2 dostolb:=2 to SpinEdit1.Value+1 do.Cells[stolb,strok]:=StringGrid1.Cells[stolb-2,strok-1];;stolb:=2 to SpinEdit1.Value+1 do.Cells[stolb,0]:=Chelevaya.Cells[stolb-2,1];;strok:=1 to SpinEdit2.Value do.Cells[REshenie.ColCount-1,strok+1]:=StringGrid1.Cells[StringGrid1.colcount-1,strok];strok:=1 to SpinEdit2.Value do.Cells[1,strok+1]:='X'+inttostr(SpinEdit1.Value+strok);.Cells[strok+SpinEdit1.Value+1,1]:='X'+inttostr(SpinEdit1.Value+strok);;strok:=2 to SpinEdit2.Value+1 doStringGrid1.Cells[SpinEdit1.Value,strok-1]='<=' then.Cells[strok+SpinEdit1.Value,strok]:='+1';StringGrid1.Cells[SpinEdit1.Value,strok-1]='>=' then.Cells[strok+SpinEdit1.Value,strok]:='-1';;

// Расчёт оценок

for stolb:=2 to REshenie.ColCount-1 doj:=2 to REshenie.RowCount-2 do:=StrTofloat( REshenie.cells[stolb,j])*StrTofloat(REshenie.Cells[0,j]);:=s+d;;.Cells[stolb,REshenie.RowCount-1]:=FloatToStr(s-StrTofloat(REshenie.Cells[stolb,0]));;TForm1.Button1Click(Sender: TObject);itera,kluch_stolb,kluch_strok:integer;,min2,d,z,f1,f2,f3,f4,s:real;: integer;_of_min:array[1..10]of real;_of_zna:array[1..10,1..10]of real;

chet:=0;

//Количество итераций

for itera:=1 to SpinEdit3.Value doRadioGroup1.ItemIndex=1 then:=99;

//Нахождение ключ столбца

for i:=1 to REshenie.ColCount-3 doStrToFloat(REshenie.Cells[i+1,REshenie.rowcount-1])<min1 then:=StrToFloat(REshenie.Cells[i+1,REshenie.rowcount-1]);_stolb:=i+1;;;i:=1 to REshenie.RowCount-3 doREshenie.Cells[kluch_stolb,i+1]<>'0' then_of_min[i]:=strtofloat(REshenie.Cells[REshenie.Colcount-1,i+1]) /strtofloat(REshenie.Cells[kluch_stolb,i+1])_of_min[i]:=0;;

//Поиск минимальной строки

min2:=9999;

for i:=1 to REshenie.RowCount-3 do(mas_of_min[i]<min2) and (mas_of_min[i]>0) then:=mas_of_min[i];_strok:=i+1;;:=StrToFloat(REshenie.Cells[kluch_stolb,kluch_strok]);

//Замена базиса

REshenie.Cells[0,kluch_strok]:=REshenie.Cells[kluch_stolb,0];.Cells[1,kluch_strok]:=REshenie.Cells[kluch_stolb,1];

//Правило прямоугольника

for i:=2 to REshenie.RowCount-2 doj:=2 to REshenie.ColCount-1 doi<>kluch_strok thenj<>kluch_stolb then:=StrToFloat(REshenie.Cells[j,i]);:=StrToFloat(REshenie.Cells[j,kluch_strok]);:=StrToFloat(REshenie.Cells[kluch_stolb,i]);_of_zna[j,i]:=((f1*f4)-(f2*f3))/f4;;;;

//Нули в столбцеi:=2 to REshenie.RowCount-1 do.Cells[kluch_stolb,i]:='0';;.Cells[kluch_stolb,kluch_strok]:=floattostr(f4);

//Строки делятся на ключевой элемент

for i:=2 to REshenie.ColCount-1 do.Cells[i,kluch_strok]:=floattostr(strtofloat(REshenie.Cells[i,kluch_strok])/f4);;:=StrToFloat(REshenie.Cells[kluch_stolb,kluch_strok]);i:=2 to REshenie.RowCount-2 doj:=2 to REshenie.ColCount-1 doi<>kluch_strok thenj<>kluch_stolb then.Cells[j,i]:=FloatToStr(mas_of_zna[j,i]);;;;

// Подсчёт оценок

for i:=2 to REshenie.ColCount-1 doj:=2 to REshenie.RowCount-2 do:=StrTofloat( REshenie.cells[i,j])*StrTofloat(REshenie.Cells[0,j]);:=s+d;;.Cells[i,REshenie.RowCount-1]:=FloatToStr(s-StrToInt(REshenie.Cells[i,0]));:=0;;i:=2 to REshenie.ColCount-2 doStrToFloat( REshenie.Cells[i,REshenie.RowCount-1])>= 0 then:=chet+1

else

end;

//Проверка на оптимальность

if chet=REshenie.ColCount-3 then('Решение Найдено,mtWarning,[mbOK],1);.Visible:=true;.Visible:=false;;elseitera=SpinEdit3.Value then(Решение не найдено, увеличьте количество итераций или отсутствует '+RadioGroup1.items[RadioGroup1.itemindex]+' функции',mtWarning,[mbOK],1);.Visible:=false;.Visible:=false;;:=0;:=-99;

//Накождение ключ столбца

for i:=1 to REshenie.ColCount-3 doStrToFloat(REshenie.Cells[i+1,REshenie.rowcount-1])>min1 then:=StrToFloat(REshenie.Cells[i+1,REshenie.rowcount-1]);_stolb:=i+1;;;i:=1 to REshenie.RowCount-3 doREshenie.Cells[kluch_stolb,i+1]<>'0' then_of_min[i]:=strtofloat(REshenie.Cells[REshenie.Colcount-1,i+1]) /strtofloat(REshenie.Cells[kluch_stolb,i+1])_of_min[i]:=0;;

//Поиск Минимальной строки

min2:=9999;

for i:=1 to REshenie.RowCount-3 do(mas_of_min[i]<min2) and (mas_of_min[i]>0) then:=mas_of_min[i];_strok:=i+1;;:=StrToFloat(REshenie.Cells[kluch_stolb,kluch_strok]);

//Замена базиса

REshenie.Cells[0,kluch_strok]:=REshenie.Cells[kluch_stolb,0];.Cells[1,kluch_strok]:=REshenie.Cells[kluch_stolb,1];

//Правило прямоугольника

for i:=2 to REshenie.RowCount-2 doj:=2 to REshenie.ColCount-1 doi<>kluch_strok thenj<>kluch_stolb then:=StrToFloat(REshenie.Cells[j,i]);:=StrToFloat(REshenie.Cells[j,kluch_strok]);:=StrToFloat(REshenie.Cells[kluch_stolb,i]);_of_zna[j,i]:=((f1*f4)-(f2*f3))/f4;;;;

//Нули в столбцеi:=2 to REshenie.RowCount-1 do.Cells[kluch_stolb,i]:='0';;.Cells[kluch_stolb,kluch_strok]:=floattostr(f4);

//Строка делится на ключевой элемент

for i:=2 to REshenie.ColCount-1 do.Cells[i,kluch_strok]:=floattostr(strtofloat(REshenie.Cells[i,kluch_strok])/f4);;:=StrToFloat(REshenie.Cells[kluch_stolb,kluch_strok]);i:=2 to REshenie.RowCount-2 doj:=2 to REshenie.ColCount-1 doi<>kluch_strok thenj<>kluch_stolb then.Cells[j,i]:=FloatToStr(mas_of_zna[j,i]);;;;

// Подсчёт оценок

for i:=2 to REshenie.ColCount-1 doj:=2 to REshenie.RowCount-2 do:=StrTofloat( REshenie.cells[i,j])*StrTofloat(REshenie.Cells[0,j]);:=s+d;;.Cells[i,REshenie.RowCount-1]:=FloatToStr(s-StrToInt(REshenie.Cells[i,0]));:=0;;i:=2 to REshenie.ColCount-2 doStrToFloat( REshenie.Cells[i,REshenie.RowCount-1])<= 0 then:=chet+1

else

end;

//Проверка на оптимальность

if chet=REshenie.ColCount-3 then('Решение найдено',mtWarning,[mbOK],1);.Visible:=true;.Visible:=false;;elseitera=SpinEdit3.Value then(Решение не найдено, увеличьте количество итераций или отсутствует '+RadioGroup1.items[RadioGroup1.itemindex]+' функции',mtWarning,[mbOK],1);.Visible:=false;.Visible:=false;;:=0;;;.Caption:=IntToStr(kluch_stolb);.Caption:=IntToStr(kluch_strok);;TForm1.Button3Click(Sender: TObject);,finals;,f1,f2,f3,f4,s,d:real;_of_zna:array[1..10,1..10]of real;_of_min:array[1..10]of real;_drob_n,kluch_stolb,kluch_strok:Integer;_of_q:array[1..10]of real;,max,max_drob_z,x,min2,m,min1:real;:=-9999;

//i:=2 to REshenie.rowCount-2 do(frac(StrToFloat(REshenie.Cells[REshenie.colcount-1,i]))<>0) and (frac(StrToFloat( REshenie.Cells[REshenie.ColCount-1,i]))>max) then:=frac(StrToFloat(REshenie.Cells[REshenie.colcount-1,i]));_drob_n:=i;_drob_z:=StrToFloat(REshenie.Cells[REshenie.colcount-1,i]);;

finals:

//Проверка на наличие дроби

if (max_drob_z<>0) or (frac(StrToFloat(REshenie.Cells[REshenie.ColCount-1,REshenie.RowCount-1]))<>0)then.Caption:=FloatToStr(max_drob_z);.Caption:=IntToStr(REshenie.ColCount-1);.Caption:=IntToStr(max_drob_n);

//Нахождение элементов дополнительного ограничения

mas_of_q[REshenie.ColCount]:=StrToFloat(REshenie.Cells[REshenie.ColCount-1,max_drob_n])-trunc(StrToFloat(REshenie.Cells[REshenie.ColCount-1,max_drob_n]));_of_q[REshenie.ColCount-1]:=1;i:=2 to REshenie.ColCount-2 do(StrToFloat(REshenie.Cells[i,max_drob_n])<0) and (frac(StrToFloat(REshenie.Cells[i,max_drob_n]))<>0) then_of_q[i]:=StrToFloat(REshenie.Cells[i,max_drob_n])-Trunc(StrToFloat(REshenie.Cells[i,max_drob_n])-1)_of_q[i]:=StrToFloat(REshenie.Cells[i,max_drob_n])-Trunc(StrToFloat(REshenie.Cells[i,max_drob_n]));;

//Вывод ключевых

for i:=2 to REshenie.ColCount do_str.Cells[i-2,0]:=floattostr( mas_of_q[i]);;.Caption:=FloatToStr(mas_of_q[1]);

//Добавление новой строки.RowCount:=REshenie.RowCount+1;

//перенос оценок на последнюю строкуi:=2 to REshenie.ColCount do.Cells[i,REshenie.RowCount-1]:=REshenie.Cells[i,REshenie.RowCount-2];.Cells[i,REshenie.RowCount-2]:='';;.Cells[1,REshenie.RowCount-2]:='X'+IntToStr(strtoint(REshenie.Cells[REshenie.colcount-2,1][2])+1);.Cells[0,REshenie.RowCount-2]:='0';

//добавление нового столбца.ColCount:=REshenie.COlCount+1;

//перенос на последний столбец

for i:=2 to REshenie.rowCount do.Cells[REshenie.COlCount-1,i]:=REshenie.Cells[REshenie.colcount-2,i];.Cells[REshenie.COlCount-2,i]:='';;

//Добавление значений коофицента

REshenie.Cells[REshenie.ColCount-2,1]:=REshenie.Cells[1,REshenie.Rowcount-2];.Cells[REshenie.ColCount-2,0]:='0';

//Заполнение 0

for i:=2 to REshenie.RowCount-1 do.Cells[REshenie.ColCount-2,i]:='0';;

//Заполнение строки q1i:=2 to REshenie.ColCount-1 do(mas_of_q[i]<>0) and (mas_of_q[i]<>1) then.Cells[i,REshenie.RowCount-2]:='-'+FloatToStr(mas_of_q[i]).Cells[i,REshenie.RowCount-2]:=FloatToStr(mas_of_q[i]);;

//Знак - или +i:=2 to REshenie.ColCount-3 do(RadioGroup1.ItemIndex=1) and (REshenie.Cells[i,reshenie.rowcount-1][1]<>'-') and (StrToFloat(REshenie.Cells[i,reshenie.rowcount-1])>0) then.Cells[i,reshenie.rowcount-1]:='-'+REshenie.Cells[i,reshenie.rowcount-1];;

min1:=99;

//Нахождение ключ столбца для гомори

for i:=1 to REshenie.ColCount-3 do(StrToFloat(REshenie.Cells[i+1,REshenie.rowcount-2]) <>0) thenStrToFloat(REshenie.Cells[i+1,REshenie.rowcount-1])<>0 then(StrToFloat(REshenie.Cells[i+1,REshenie.rowcount-1])/StrToFloat(REshenie.Cells[i+1,REshenie.rowcount-2]) <min1 ) and (StrToFloat(REshenie.Cells[i+1,REshenie.rowcount-1]) <>0) then:=StrToFloat(REshenie.Cells[i+1,REshenie.rowcount-1])/StrToFloat(REshenie.Cells[i+1,REshenie.rowcount-1]);_stolb:=i+1;;;i:=1 to REshenie.RowCount-3 doREshenie.Cells[kluch_stolb,i+1]<>'0' then_of_min[i]:=strtofloat(REshenie.Cells[REshenie.Colcount-1,i+1]) /strtofloat(REshenie.Cells[kluch_stolb,i+1])_of_min[i]:=0;;

//Поиск мин строки

min2:=9999;

for i:=1 to REshenie.RowCount-3 do(mas_of_min[i]<min2) and (mas_of_min[i]>0) then:=mas_of_min[i];_strok:=i+1;;:=StrToFloat(REshenie.Cells[kluch_stolb,kluch_strok]);

//Замена базиса

REshenie.Cells[0,kluch_strok]:=REshenie.Cells[kluch_stolb,0];.Cells[1,kluch_strok]:=REshenie.Cells[kluch_stolb,1];

//Правило прямоугольника

for i:=2 to REshenie.RowCount-2 doj:=2 to REshenie.ColCount-1 doi<>kluch_strok thenj<>kluch_stolb then:=StrToFloat(REshenie.Cells[j,i]);:=StrToFloat(REshenie.Cells[j,kluch_strok]);:=StrToFloat(REshenie.Cells[kluch_stolb,i]);_of_zna[j,i]:=((f1*f4)-(f2*f3))/f4;;;;

//Нули в столбцеi:=2 to REshenie.RowCount-1 do.Cells[kluch_stolb,i]:='0';;.Cells[kluch_stolb,kluch_strok]:=floattostr(f4);

//Строка делится на ключевой элемент

for i:=2 to REshenie.ColCount-1 do.Cells[i,kluch_strok]:=floattostr(strtofloat(REshenie.Cells[i,kluch_strok])/f4);;:=StrToFloat(REshenie.Cells[kluch_stolb,kluch_strok]);i:=2 to REshenie.RowCount-2 doj:=2 to REshenie.ColCount-1 doi<>kluch_strok thenj<>kluch_stolb then.Cells[j,i]:=FloatToStr(mas_of_zna[j,i]);;;;

//Подсчёт оценок

for i:=2 to REshenie.ColCount-1 doj:=2 to REshenie.RowCount-2 do:=StrTofloat( REshenie.cells[i,j])*StrTofloat(REshenie.Cells[0,j]);:=x+m;;i=REshenie.ColCount-1 then.Cells[i,REshenie.RowCount-1]:=FloatToStr(x).Cells[i,REshenie.RowCount-1]:=FloatToStr(x-StrTofloat(REshenie.Cells[i,0]));:=0;;

//Округление

for j:=2 to REshenie.RowCount-1 do((REshenie.Cells[REshenie.Colcount-1,j][3]='0') and (REshenie.Cells[REshenie.Colcount-1,j][4]='0') and (REshenie.Cells[REshenie.Colcount-1,j][5]='0'))((REshenie.Cells[REshenie.Colcount-1,j][1]='-') and (REshenie.Cells[REshenie.Colcount-1,j][4]='0') and (REshenie.Cells[REshenie.Colcount-1,j][5]='0') and (REshenie.Cells[REshenie.Colcount-1,j][6]='9'))((REshenie.Cells[REshenie.Colcount-1,j][3]='9') and (REshenie.Cells[REshenie.Colcount-1,j][4]='9') and (REshenie.Cells[REshenie.Colcount-1,j][5]='9'))((REshenie.Cells[REshenie.Colcount-1,j][1]='-') and (REshenie.Cells[REshenie.Colcount-1,j][4]='9') and (REshenie.Cells[REshenie.Colcount-1,j][5]='9') and (REshenie.Cells[REshenie.Colcount-1,j][6]='9')).Cells[REshenie.Colcount-1,j]:=inttostr(round(StrToFloat(REshenie.Cells[REshenie.Colcount-1,j])));;.Caption:=FloatToStr(kluch_stolb);.Caption:=FloatToStr(kluch_strok);

else

begin

MessageDlg(Дробей в решении нет, следовательно ответ целочисленный,mtWarning,[mbOK],1);

Button3.Visible:=false;i:=1 to Q_str.ColCount-1 do_str.Cells[i,0]:='';i:=1 to SpinEdit1.Value do_str.Cells[i-1,0]:='X'+IntToStr(i);;i:=2 to REshenie.RowCount-2 doj:=1 to SpinEdit1.Value doREshenie.Cells[1,i]='X'+IntToStr(j) then_str.Cells[j-1,1]:=REshenie.Cells[REshenie.colcount-1,i];;TForm1.ChelevayaKeyPress(Sender: TObject; var Key: Char);not (key in ['0'..'9',#8,'-','<','=','>','.',#13]) then key:=#0;;TForm1.Button4Click(Sender: TObject);.Cells[0,1]:='2';.Cells[1,1]:='-1';.Cells[0,1]:='-1';.Cells[0,2]:='1';.Cells[0,3]:='1';.Cells[1,1]:='2';.Cells[1,2]:='2';.Cells[1,3]:='-2';.Cells[2,1]:='<=';.Cells[2,2]:='<=';.Cells[2,3]:='<=';.Cells[3,1]:='2';.Cells[3,2]:='6';.Cells[3,3]:='4';

end;.

МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РОССИЙСКОЙ ФЕДЕРАЦИИ "САХАЛИНСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ" САХАЛИНСКИЙ КОЛЛЕДЖ БИЗНЕСА И ИНФОРМАТИКИ

Больше работ по теме: