Размещено на http://www.allbest.ru/

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

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

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

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

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

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

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

Студента:

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

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

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

Сливчак С.И.

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

2013



Содержание

Оглавление

• Введение
• Глава 1. Метод Гомори
• 1.1 Экономическая сущность задачи
• 1.2 Постановка задачи
• 1.3 Метод решения задач
• 1.4 Функциональные тесты
• Глава 2. Моделирование, алгоритмизация и программирование метода
• 2.1 Математическая модель задачи
• 2.2 Входные - выходные данные задачи
• 2.3 Блок - схема решения задачи
• 2.4 Тестирование
• Глава 3. Руководство пользователя
• Заключение
• Список литературы
• Приложение

Введение

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

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

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

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

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

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

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

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

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

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

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

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

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



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

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

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

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

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

При производстве n видов продукции используется m видов ресурсов. Известно: b_1, b_{2, …,} b_m - запасы ресурсов; a_ij (i=1, 2, …, m; j=1, 2, …, n)- расход каждого i-го вида ресурса на изготовление единицы j-й продукции; c_j (j=1, 2, …, n)- прибыль, получаемая при реализации единицы j-й продукции. Составить план выпуска продукции, обеспечивающий максимальную прибыль. Ответ должен иметь целочисленные значения.

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

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

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

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

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

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

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

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

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

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

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

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

Задача 1

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

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

5x₁ + 2x₂?20

x₁ + x₂?6

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

5x₁ + 2x₂ + 1x₃ + 0x₄ = 20

1x₁ + 1x₂ + 0x₃ + 1x₄ = 6

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



Базис	B	x1	x2	x3	x4
x3	20	5	2	1	0
x4	6	1	1	0	1
F(X0)	0	-16	-9	0	0
Базис	B	x1	x2	x3	x4
x3	20	5	2	1	0	4
x4	6	1	1	0	1	6
F(X1)	0	-16	-9	0	0	0
Базис	B	x1	x2	x3	x4	min
x1	4	1	2/5	1/5	0	10
x4	2	0	3/5	-1/5	1	31/3
F(X2)	64	0	-23/5	31/5	0	0
Базис	B	x1	x2	x3	x4
x1	22/3	1	0	1/3	-2/3
x2	31/3	0	1	-1/3	12/3
F(X3)	722/3	0	0	21/3	41/3

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

x₁ = 2²/₃

x₂ = 3¹/₃

F(X) = 16*2²/₃ + 9*3¹/₃ = 72²/₃

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

Базис	B	x1	x2	x3	x4	x5
x1	22/3	1	0	1/3	-2/3	0
x2	31/3	0	1	-1/3	12/3	0
x5	-2/3	0	0	-1/3	-1/3	1
F(X0)	-722/3	0	0	-21/3	-41/3	0
Базис	B	x1	x2	x3	x4	x5
x1	22/3	1	0	1/3	-2/3	0
x2	31/3	0	1	-1/3	12/3	0
x5	-2/3	0	0	-1/3	-1/3	1
F(X)	-722/3	0	0	-21/3	41/3	0
и	0	-	-	-21/3 : (-1/3) = 7	-41/3 : (-1/3) = 13	-
Базис	B	x1	x2	x3	x4	x5
x1	2	1	0	0	-1	1
x2	4	0	1	0	2	-1
x3	2	0	0	1	1	-3
F(X0)	-68	0	0	0	-2	-7
Базис	B	x1	x2	x3	x4	x5
x1	2	1	0	0	-1	1
x2	4	0	1	0	2	-1
x3	2	0	0	1	1	-3
F(X0)	-68	0	0	0	-2	-7

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

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

Задача 2

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

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

- x₁ + 3x₂?6

7x₁ + x₂?35

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



-1x₁ + 3x₂ + 1x₃ + 0x₄ = 6

7x₁ + 1x₂ + 0x₃ + 1x₄ = 35

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

Базис	B	x1	x2	x3	x4
x3	6	-1	3	1	0
x4	35	7	1	0	1
F(X0)	0	-7	-9	0	0
Базис	B	x1	x2	x3	x4
x3	6	-1	3	1	0	2
x4	35	7	1	0	1	35
F(X1)	0	-7	-9	0	0	0
Базис	B	x1	x2	x3	x4	min
x2	2	-1/3	1	1/3	0	-
x4	33	71/3	0	-1/3	1	41/2
F(X2)	18	-10	0	3	0	0
Базис	B	x1	x2	x3	x4
x2	31/2	0	1	7/22	1/22
x1	41/2	1	0	-1/22	3/22
F(X3)	63	0	0	26/11	14/11

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

x₂ = 3¹/₂

x₁ = 4¹/₂

F(X) = 9*3¹/₂ + 7*4¹/₂ = 63

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



Базис	B	x1	x2	x3	x4	x5
x2	31/2	0	1	7/22	1/22	0
x1	41/2	1	0	-1/22	3/22	0
x5	-1/2	0	0	-7/22	-1/22	1
F(X0)	-63	0	0	-26/11	-14/11	0
Базис	B	x1	x2	x3	x4	x5
x2	31/2	0	1	7/22	1/22	0
x1	41/2	1	0	-1/22	3/22	0
x5	-1/2	0	0	-7/22	-1/22	1
F(X)	-63	0	0	-26/11	-14/11	0
и	0	-	-	-26/11 : (-7/22) = 8	-14/11 : (-1/22) = 30	-
Базис	B	x1	x2	x3	x4	x5
x2	3	0	1	0	0	1
x1	44/7	1	0	0	1/7	-1/7
x3	14/7	0	0	1	1/7	-31/7
F(X0)	-59	0	0	0	-1	-8
Базис	B	x1	x2	x3	x4	x5
x2	3	0	1	0	0	1
x1	4	1	0	0	0	-1
x3	1	0	0	1	0	-4
x4	4	0	0	0	1	6
F(X0)	-55	0	0	0	0	-2

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

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

Задача 3

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

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



5x₁ + 2x₂?20

8x₁ + 4x₂?38

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

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

5x₁ + 2x₂ + 1x₃ + 0x₄ = 20

8x₁ + 4x₂ + 0x₃ + 1x₄ = 38

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

Базис	B	x1	x2	x3	x4
x3	20	5	2	1	0
x4	38	8	4	0	1
F(X0)	0	-7	-3	0	0
Базис	B	x1	x2	x3	x4	min
x3	20	5	2	1	0	4
x4	38	8	4	0	1	43/4
F(X1)	0	-7	-3	0	0	0
Базис	B	x1	x2	x3	x4	min
x1	4	1	2/5	1/5	0	10
x4	6	0	4/5	-13/5	1	71/2
F(X2)	28	0	-1/5	12/5	0	0
Базис	B	x1	x2	x3	x4
x1	1	1	0	1	-1/2
x2	71/2	0	1	-2	11/4
F(X3)	291/2	0	0	1	1/4

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



x₁ = 1

x₂ = 7¹/₂

F(X) = 7*1 + 3*7¹/₂ = 29¹/₂

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

Базис	B	x1	x2	x3	x4	x5
x1	1	1	0	1	-1/2	0
x2	71/2	0	1	-2	11/4	0
x5	-1/2	0	0	0	-1/4	1
F(X0)	-291/2	0	0	-1	-1/4	0
Базис	B	x1	x2	x3	x4	x5
x1	1	1	0	1	-1/2	0
x2	71/2	0	1	-2	11/4	0
x5	-1/2	0	0	0	-1/4	1
F(X)	-291/2	0	0	-1	-1/4	0
и	0	-	-	-	-1/4 : (-1/4) = 1	-
Базис	B	x1	x2	x3	x4	x5
x1	2	1	0	1	0	-2
x2	5	0	1	-2	0	5
x4	2	0	0	0	1	-4
F(X0)	-29	0	0	-1	0	-1

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

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



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

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

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

при условиях

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

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

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

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

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

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

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

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

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

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

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

b_i = x_i +a_im+lx_m+1 +a_im+2x_m+2+…+a_inx_n .

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

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

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

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

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

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



Обозначим

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

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

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

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

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

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

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

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

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

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

Задача 1

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

5x₁ + 2x₂?20

x₁ + x₂?6

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

Задача 2

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

- x₁ + 3x₂?6

7x₁ + x₂?35



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

Задача 3

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

5x₁ + 2x₂?20

8x₁ + 4x₂?38

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

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



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

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

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



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

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

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



Заключение

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

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

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

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

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



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

1. Алгоритм Гомори//Википедия. [Электронный ресурс]. URL:http://ru.wikipedia.org/wiki/Алгоритм_Гомори

2. Конюховский П.В. Математические методы исследования операций в экономике, СПб.: Питер, 2008.

3. Корбут А.А., Финкельштейн Ю.Ю. Дискретное программирование, М.: Наука, 1969.

4. Лященко И.Н. Линейное и нелинейное программирование, М.: Наука, 1985.

5. Метод Гомори //Высшая математика. [Электронный ресурс].URL http://www.mathelp.spb.ru/book1/lprog8.htm

6. О.Л Голицына, Попов И.И. Основы алгоритмизации и программирования. М.: ФОРУМ - ИНФРА-М, 2006.

7. Партыка Т.Л., Попов И.И. Математические методы: Учебник. М.: Форум: ИНФА-М, 2005. 464с.

8. Просветов Г. И. Математические методы и модели в экономике. Задачи и решения, М.: Альфа-Пресс, 2008. 344с.

9. Сборник задач по высшей математике для экономистов: Учебное пособие / Под ред. В.И. Ермакова. М.: ИНФРА-М, 2001. 575с.

10. Тынкевич М.А. Экономико-математические методы (исследование операций), издание 2-е, исправленное и дополненное, Кемерово, 2007.



Приложение

unit Unit1;

interface

uses

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

Dialogs, StdCtrls, ComCtrls, Grids, Spin, ExtCtrls, jpeg, XPMan;

type

TForm1 = class(TForm)

Chelevaya: TStringGrid;

SpinEdit1: TSpinEdit;

Label1: TLabel;

StringGrid1: TStringGrid;

SpinEdit2: TSpinEdit;

Label2: TLabel;

Button1: TButton;

REshenie: TStringGrid;

Button2: TButton;

RadioGroup1: TRadioGroup;

Label3: TLabel;

Button3: TButton;

SpinEdit3: TSpinEdit;

Label4: TLabel;

Label5: TLabel;

Label6: TLabel;

Label7: TLabel;

Label8: TLabel;

GroupBox1: TGroupBox;

Label9: TLabel;

Label10: TLabel;

Q_str: TStringGrid;

Button4: TButton;

XPManifest1: TXPManifest;

Label11: TLabel;

procedure SpinEdit1Change(Sender: TObject);

procedure SpinEdit2Change(Sender: TObject);

procedure FormCreate(Sender: TObject);

procedure Button2Click(Sender: TObject);

procedure Button1Click(Sender: TObject);

procedure Button3Click(Sender: TObject);

procedure ChelevayaKeyPress(Sender: TObject; var Key: Char);

procedure Button4Click(Sender: TObject);

private

{ Private declarations }

public

{ Public declarations }

end;

var

Form1: TForm1;

i,j,str_um,stolb_um,minmax_zn:Integer;

minmax_za:real;

implementation

uses Math;

{$R *.dfm}

procedure TForm1.SpinEdit1Change(Sender: TObject);

begin

with REshenie do

for i:=0 to colcount-1 do

for j:=0 to rowcount-1 do

Cells[i,j]:='';

with StringGrid1 do

for i:=0 to colcount-1 do

for j:=1 to rowcount-1 do

Cells[i,j]:='';

with Chelevaya do

for i:=0 to colcount-1 do

for j:=1 to rowcount-1 do

Cells[i,j]:='';

REshenie.Cells[0,1]:='Ci';

REshenie.Cells[1,1]:='Ai';

Chelevaya.ColCount:=SpinEdit1.Value;

REshenie.ColCount:=SpinEdit1.Value+SpinEdit2.Value+3;

StringGrid1.ColCount:=SpinEdit1.Value+2;

StringGrid1.Cells[SpinEdit1.Value-1,0]:='X'+IntToStr(SpinEdit1.Value);

Chelevaya.Cells[SpinEdit1.Value-1,0]:='X'+IntToStr(SpinEdit1.Value);

StringGrid1.Cells[SpinEdit1.Value,0]:='Ciae';

StringGrid1.Cells[SpinEdit1.Value+1,0]:='#';

str_um:=REshenie.RowCount;

stolb_um:=REshenie.ColCount;

end;

procedure TForm1.SpinEdit2Change(Sender: TObject);

begin

with REshenie do

for i:=0 to colcount-1 do

for j:=0 to rowcount-1 do

Cells[i,j]:='';

REshenie.Cells[0,1]:='Ci';

REshenie.Cells[1,1]:='Ai';

StringGrid1.RowCount:=SpinEdit2.Value+1;

REshenie.ColCount:=SpinEdit1.Value+SpinEdit2.Value+3;

REshenie.RowCount:=SpinEdit2.Value+3;

str_um:=REshenie.RowCount;

stolb_um:=REshenie.ColCount;

end;

procedure TForm1.FormCreate(Sender: TObject);

begin

str_um:=REshenie.RowCount;

stolb_um:=REshenie.ColCount;

StringGrid1.Cells[0,0]:='X1';

StringGrid1.Cells [1,0]:='X2';

Chelevaya.Cells[0,0]:='X1';

Chelevaya.Cells[1,0]:='X2';

StringGrid1.Cells[2,0]:='Ciae';

StringGrid1.Cells [3,0]:='#';

REshenie.Cells[0,1]:='Ci';

REshenie.Cells[1,1]:='Ai';

end;

procedure TForm1.Button2Click(Sender: TObject);

var stolb,strok:Integer;

s,d:real;

begin

Button1.Visible:=true;

REshenie.RowCount:=str_um;

REshenie.ColCount:=stolb_um;

with REshenie do

for i:=0 to colcount-1 do

for j:=0 to rowcount-1 do

Cells[i,j]:='';

for i:=2 to REshenie.ColCount-1 do

for j:=0 to REshenie.RowCount-1 do

REshenie.Cells[i,j]:='0';

REshenie.Cells[0,1]:='Ci';

REshenie.Cells[1,1]:='Ai';

for i:=2 to REshenie.RowCount-2 do

REshenie.Cells[0,i]:='0';

for strok:=1 to SpinEdit2.Value+2 do

for stolb:=2 to SpinEdit1.Value+1 do

begin

REshenie.Cells[stolb,strok]:=StringGrid1.Cells[stolb-2,strok-1];

end;

for stolb:=2 to SpinEdit1.Value+1 do

begin

REshenie.Cells[stolb,0]:=Chelevaya.Cells[stolb-2,1];

end;

for strok:=1 to SpinEdit2.Value do

REshenie.Cells[REshenie.ColCount-1,strok+1]:=StringGrid1.Cells[StringGrid1.colcount-1,strok];

for strok:=1 to SpinEdit2.Value do

begin

REshenie.Cells[1,strok+1]:='X'+inttostr(SpinEdit1.Value+strok);

REshenie.Cells[strok+SpinEdit1.Value+1,1]:='X'+inttostr(SpinEdit1.Value+strok);

end;

for strok:=2 to SpinEdit2.Value+1 do

begin

if StringGrid1.Cells[SpinEdit1.Value,strok-1]='<=' then

REshenie.Cells[strok+SpinEdit1.Value,strok]:='+1';

if StringGrid1.Cells[SpinEdit1.Value,strok-1]='>=' then

REshenie.Cells[strok+SpinEdit1.Value,strok]:='-1';

end;

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

for stolb:=2 to REshenie.ColCount-1 do

begin

for j:=2 to REshenie.RowCount-2 do

begin

d:=StrTofloat( REshenie.cells[stolb,j])*StrTofloat(REshenie.Cells[0,j]);

s:=s+d;

end;

REshenie.Cells[stolb,REshenie.RowCount-1]:=FloatToStr(s-StrTofloat(REshenie.Cells[stolb,0]));

end

end;

procedure TForm1.Button1Click(Sender: TObject);

var itera,kluch_stolb,kluch_strok:integer;

min1,min2,d,z,f1,f2,f3,f4,s:real;

chet: integer;

mas_of_min:array[1..10]of real;

mas_of_zna:array[1..10,1..10]of real;

begin

chet:=0;

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

for itera:=1 to SpinEdit3.Value do

begin

if RadioGroup1.ItemIndex=1 then

begin

min1:=99;

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

for i:=1 to REshenie.ColCount-3 do

begin

if StrToFloat(REshenie.Cells[i+1,REshenie.rowcount-1])<min1 then

begin

min1:=StrToFloat(REshenie.Cells[i+1,REshenie.rowcount-1]);

kluch_stolb:=i+1;

end;

end;

for i:=1 to REshenie.RowCount-3 do

begin

if REshenie.Cells[kluch_stolb,i+1]<>'0' then

mas_of_min[i]:=strtofloat(REshenie.Cells[REshenie.Colcount-1,i+1]) /strtofloat(REshenie.Cells[kluch_stolb,i+1])

else

mas_of_min[i]:=0;

end;

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

min2:=9999;

for i:=1 to REshenie.RowCount-3 do

if (mas_of_min[i]<min2) and (mas_of_min[i]>0) then

begin

min2:=mas_of_min[i];

kluch_strok:=i+1;

end;

f4:=StrToFloat(REshenie.Cells[kluch_stolb,kluch_strok]);

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

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

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

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

for i:=2 to REshenie.RowCount-2 do

begin

for j:=2 to REshenie.ColCount-1 do

begin

if i<>kluch_strok then

if j<>kluch_stolb then

begin

f1:=StrToFloat(REshenie.Cells[j,i]);

f2:=StrToFloat(REshenie.Cells[j,kluch_strok]);

f3:=StrToFloat(REshenie.Cells[kluch_stolb,i]);

mas_of_zna[j,i]:=((f1*f4)-(f2*f3))/f4;

end;

end;

end;

//Нули в столбце

for i:=2 to REshenie.RowCount-1 do

begin

REshenie.Cells[kluch_stolb,i]:='0';

end;

REshenie.Cells[kluch_stolb,kluch_strok]:=floattostr(f4);

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

for i:=2 to REshenie.ColCount-1 do

begin

REshenie.Cells[i,kluch_strok]:=floattostr(strtofloat(REshenie.Cells[i,kluch_strok])/f4);

end;

z:=StrToFloat(REshenie.Cells[kluch_stolb,kluch_strok]);

for i:=2 to REshenie.RowCount-2 do

begin

for j:=2 to REshenie.ColCount-1 do

begin

if i<>kluch_strok then

if j<>kluch_stolb then

begin

REshenie.Cells[j,i]:=FloatToStr(mas_of_zna[j,i]);

end;

end;

end;

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

for i:=2 to REshenie.ColCount-1 do

begin

for j:=2 to REshenie.RowCount-2 do

begin

d:=StrTofloat( REshenie.cells[i,j])*StrTofloat(REshenie.Cells[0,j]);

s:=s+d;

end;

REshenie.Cells[i,REshenie.RowCount-1]:=FloatToStr(s-StrToInt(REshenie.Cells[i,0]));

s:=0;

end;

for i:=2 to REshenie.ColCount-2 do

begin

if StrToFloat( REshenie.Cells[i,REshenie.RowCount-1])>= 0 then

chet:=chet+1

else

end;

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

if chet=REshenie.ColCount-3 then

begin

MessageDlg('Решение Найдено',mtWarning,[mbOK],1);

Button3.Visible:=true;

Button1.Visible:=false;

break;

end else

if itera=SpinEdit3.Value then

begin

MessageDlg(Решение не найдено, увеличьте количество итераций или отсутствует '+RadioGroup1.items[RadioGroup1.itemindex]+' функции',mtWarning,[mbOK],1);

Button1.Visible:=false;

Button3.Visible:=false;

end;

chet:=0;

end

else

begin

min1:=-99;

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

for i:=1 to REshenie.ColCount-3 do

begin

if StrToFloat(REshenie.Cells[i+1,REshenie.rowcount-1])>min1 then

begin

min1:=StrToFloat(REshenie.Cells[i+1,REshenie.rowcount-1]);

kluch_stolb:=i+1;

end;

end;

for i:=1 to REshenie.RowCount-3 do

begin

if REshenie.Cells[kluch_stolb,i+1]<>'0' then

mas_of_min[i]:=strtofloat(REshenie.Cells[REshenie.Colcount-1,i+1]) /strtofloat(REshenie.Cells[kluch_stolb,i+1])

else

mas_of_min[i]:=0;

end;

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

min2:=9999;

for i:=1 to REshenie.RowCount-3 do

if (mas_of_min[i]<min2) and (mas_of_min[i]>0) then

begin

min2:=mas_of_min[i];

kluch_strok:=i+1;

end;

f4:=StrToFloat(REshenie.Cells[kluch_stolb,kluch_strok]);

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

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

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

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

for i:=2 to REshenie.RowCount-2 do

begin

for j:=2 to REshenie.ColCount-1 do

begin

if i<>kluch_strok then

if j<>kluch_stolb then

begin

f1:=StrToFloat(REshenie.Cells[j,i]);

f2:=StrToFloat(REshenie.Cells[j,kluch_strok]);

f3:=StrToFloat(REshenie.Cells[kluch_stolb,i]);

mas_of_zna[j,i]:=((f1*f4)-(f2*f3))/f4;

end;

end;

end;

//Нули в столбце

for i:=2 to REshenie.RowCount-1 do

begin

REshenie.Cells[kluch_stolb,i]:='0';

end;

REshenie.Cells[kluch_stolb,kluch_strok]:=floattostr(f4);

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

for i:=2 to REshenie.ColCount-1 do

begin

REshenie.Cells[i,kluch_strok]:=floattostr(strtofloat(REshenie.Cells[i,kluch_strok])/f4);

end;

z:=StrToFloat(REshenie.Cells[kluch_stolb,kluch_strok]);

for i:=2 to REshenie.RowCount-2 do

begin

for j:=2 to REshenie.ColCount-1 do

begin

if i<>kluch_strok then

if j<>kluch_stolb then

begin

REshenie.Cells[j,i]:=FloatToStr(mas_of_zna[j,i]);

end;

end;

end;

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

for i:=2 to REshenie.ColCount-1 do

begin

for j:=2 to REshenie.RowCount-2 do

begin

d:=StrTofloat( REshenie.cells[i,j])*StrTofloat(REshenie.Cells[0,j]);

s:=s+d;

end;

REshenie.Cells[i,REshenie.RowCount-1]:=FloatToStr(s-StrToInt(REshenie.Cells[i,0]));

s:=0;

end;

for i:=2 to REshenie.ColCount-2 do

begin

if StrToFloat( REshenie.Cells[i,REshenie.RowCount-1])<= 0 then

chet:=chet+1

else

end;

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

if chet=REshenie.ColCount-3 then

begin

MessageDlg('Решение найдено',mtWarning,[mbOK],1);

Button3.Visible:=true;

Button1.Visible:=false;

break;

end else

if itera=SpinEdit3.Value then

begin

MessageDlg(Решение не найдено, увеличьте количество итераций или отсутствует '+RadioGroup1.items[RadioGroup1.itemindex]+' функции',mtWarning,[mbOK],1);

Button1.Visible:=false;

Button3.Visible:=false;

end;

chet:=0;

end;

end;

Label5.Caption:=IntToStr(kluch_stolb);

Label6.Caption:=IntToStr(kluch_strok);

end;

procedure TForm1.Button3Click(Sender: TObject);

label

fin,finals;

var

z,f1,f2,f3,f4,s,d:real;

mas_of_zna:array[1..10,1..10]of real;

mas_of_min:array[1..10]of real;

max_drob_n,kluch_stolb,kluch_strok:Integer;

mas_of_q:array[1..10]of real;

q,max,max_drob_z,x,min2,m,min1:real;

begin

max:=-9999;

//

for i:=2 to REshenie.rowCount-2 do

If (frac(StrToFloat(REshenie.Cells[REshenie.colcount-1,i]))<>0) and (frac(StrToFloat( REshenie.Cells[REshenie.ColCount-1,i]))>max) then

begin

max:=frac(StrToFloat(REshenie.Cells[REshenie.colcount-1,i]));

max_drob_n:=i;

max_drob_z:=StrToFloat(REshenie.Cells[REshenie.colcount-1,i]);

end;

finals:

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

if (max_drob_z<>0) or (frac(StrToFloat(REshenie.Cells[REshenie.ColCount-1,REshenie.RowCount-1]))<>0)then

begin

Label9.Caption:=FloatToStr(max_drob_z);

Label5.Caption:=IntToStr(REshenie.ColCount-1);

Label6.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]));

mas_of_q[REshenie.ColCount-1]:=1;

for i:=2 to REshenie.ColCount-2 do

begin

if (StrToFloat(REshenie.Cells[i,max_drob_n])<0) and (frac(StrToFloat(REshenie.Cells[i,max_drob_n]))<>0) then

mas_of_q[i]:=StrToFloat(REshenie.Cells[i,max_drob_n])-Trunc(StrToFloat(REshenie.Cells[i,max_drob_n])-1)

else

mas_of_q[i]:=StrToFloat(REshenie.Cells[i,max_drob_n])-Trunc(StrToFloat(REshenie.Cells[i,max_drob_n]));

end;

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

for i:=2 to REshenie.ColCount do

begin

Q_str.Cells[i-2,0]:=floattostr( mas_of_q[i]);

end;

Label10.Caption:=FloatToStr(mas_of_q[1]);

//Добавление новой строки

REshenie.RowCount:=REshenie.RowCount+1;

//перенос оценок на последнюю строку

for i:=2 to REshenie.ColCount do

begin

REshenie.Cells[i,REshenie.RowCount-1]:=REshenie.Cells[i,REshenie.RowCount-2];

REshenie.Cells[i,REshenie.RowCount-2]:='';

end;

REshenie.Cells[1,REshenie.RowCount-2]:='X'+IntToStr(strtoint(REshenie.Cells[REshenie.colcount-2,1][2])+1);

REshenie.Cells[0,REshenie.RowCount-2]:='0';

//добавление нового столбца

REshenie.ColCount:=REshenie.COlCount+1;

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

for i:=2 to REshenie.rowCount do

begin

REshenie.Cells[REshenie.COlCount-1,i]:=REshenie.Cells[REshenie.colcount-2,i];

REshenie.Cells[REshenie.COlCount-2,i]:='';

end;

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

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

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

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

for i:=2 to REshenie.RowCount-1 do

begin

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

end;

//Заполнение строки q1

for i:=2 to REshenie.ColCount-1 do

begin

if (mas_of_q[i]<>0) and (mas_of_q[i]<>1) then

REshenie.Cells[i,REshenie.RowCount-2]:='-'+FloatToStr(mas_of_q[i])

else

REshenie.Cells[i,REshenie.RowCount-2]:=FloatToStr(mas_of_q[i]);

end;

//Знак - или +

for i:=2 to REshenie.ColCount-3 do

begin

if (RadioGroup1.ItemIndex=1) and (REshenie.Cells[i,reshenie.rowcount-1][1]<>'-') and (StrToFloat(REshenie.Cells[i,reshenie.rowcount-1])>0) then

REshenie.Cells[i,reshenie.rowcount-1]:='-'+REshenie.Cells[i,reshenie.rowcount-1];

end;

min1:=99;

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

for i:=1 to REshenie.ColCount-3 do

begin

if (StrToFloat(REshenie.Cells[i+1,REshenie.rowcount-2]) <>0) then

if StrToFloat(REshenie.Cells[i+1,REshenie.rowcount-1])<>0 then

if (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

begin

min1:=StrToFloat(REshenie.Cells[i+1,REshenie.rowcount-1])/StrToFloat(REshenie.Cells[i+1,REshenie.rowcount-1]);

kluch_stolb:=i+1;

end;

end;

for i:=1 to REshenie.RowCount-3 do

begin

if REshenie.Cells[kluch_stolb,i+1]<>'0' then

mas_of_min[i]:=strtofloat(REshenie.Cells[REshenie.Colcount-1,i+1]) /strtofloat(REshenie.Cells[kluch_stolb,i+1])

else

mas_of_min[i]:=0;

end;

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

min2:=9999;

for i:=1 to REshenie.RowCount-3 do

if (mas_of_min[i]<min2) and (mas_of_min[i]>0) then

begin

min2:=mas_of_min[i];

kluch_strok:=i+1;

end;

f4:=StrToFloat(REshenie.Cells[kluch_stolb,kluch_strok]);

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

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

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

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

for i:=2 to REshenie.RowCount-2 do

begin

for j:=2 to REshenie.ColCount-1 do

begin

if i<>kluch_strok then

if j<>kluch_stolb then

begin

f1:=StrToFloat(REshenie.Cells[j,i]);

f2:=StrToFloat(REshenie.Cells[j,kluch_strok]);

f3:=StrToFloat(REshenie.Cells[kluch_stolb,i]);

mas_of_zna[j,i]:=((f1*f4)-(f2*f3))/f4;

end;

end;

end;

//Нули в столбце

for i:=2 to REshenie.RowCount-1 do

begin

REshenie.Cells[kluch_stolb,i]:='0';

end;

REshenie.Cells[kluch_stolb,kluch_strok]:=floattostr(f4);

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

for i:=2 to REshenie.ColCount-1 do

begin

REshenie.Cells[i,kluch_strok]:=floattostr(strtofloat(REshenie.Cells[i,kluch_strok])/f4);

end;

z:=StrToFloat(REshenie.Cells[kluch_stolb,kluch_strok]);

for i:=2 to REshenie.RowCount-2 do

begin

for j:=2 to REshenie.ColCount-1 do

begin

if i<>kluch_strok then

if j<>kluch_stolb then

begin

REshenie.Cells[j,i]:=FloatToStr(mas_of_zna[j,i]);

end;

end;

end;

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

for i:=2 to REshenie.ColCount-1 do

begin

for j:=2 to REshenie.RowCount-2 do

begin

m:=StrTofloat( REshenie.cells[i,j])*StrTofloat(REshenie.Cells[0,j]);

x:=x+m;

end;

if i=REshenie.ColCount-1 then

REshenie.Cells[i,REshenie.RowCount-1]:=FloatToStr(x)

else

REshenie.Cells[i,REshenie.RowCount-1]:=FloatToStr(x-StrTofloat(REshenie.Cells[i,0]));

x:=0;

end;

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

for j:=2 to REshenie.RowCount-1 do

begin

if ((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'))

or ((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'))

or ((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'))

or ((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'))

then

REshenie.Cells[REshenie.Colcount-1,j]:=inttostr(round(StrToFloat(REshenie.Cells[REshenie.Colcount-1,j])));

end;

Label5.Caption:=FloatToStr(kluch_stolb);

Label6.Caption:=FloatToStr(kluch_strok);

end

else

begin

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

Button3.Visible:=false;

for i:=1 to Q_str.ColCount-1 do

Q_str.Cells[i,0]:='';

For i:=1 to SpinEdit1.Value do

begin

Q_str.Cells[i-1,0]:='X'+IntToStr(i);

end;

for i:=2 to REshenie.RowCount-2 do

for j:=1 to SpinEdit1.Value do

if REshenie.Cells[1,i]='X'+IntToStr(j) then

Q_str.Cells[j-1,1]:=REshenie.Cells[REshenie.colcount-1,i];

end;

end

procedure TForm1.ChelevayaKeyPress(Sender: TObject; var Key: Char);

begin

if not (key in ['0'..'9',#8,'-','<','=','>','.',#13]) then key:=#0;

end;

procedure TForm1.Button4Click(Sender: TObject);

begin

Chelevaya.Cells[0,1]:='2';

Chelevaya.Cells[1,1]:='-1';

StringGrid1.Cells[0,1]:='-1';

StringGrid1.Cells[0,2]:='1';

StringGrid1.Cells[0,3]:='1';

StringGrid1.Cells[1,1]:='2';

StringGrid1.Cells[1,2]:='2';

StringGrid1.Cells[1,3]:='-2';

StringGrid1.Cells[2,1]:='<=';

StringGrid1.Cells[2,2]:='<=';

StringGrid1.Cells[2,3]:='<=';

StringGrid1.Cells[3,1]:='2';

StringGrid1.Cells[3,2]:='6';

StringGrid1.Cells[3,3]:='4';

end;

end.

Размещено на Allbest.ru