Реализация целочисленного программирования (метод Гомори). Читать текст оnline - МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РОССИЙСКОЙ ФЕДЕРАЦИИ. Метод Гомори. 1. 1 Экономическая сущность задачи. Постановка задачи.
Метод решения задач. Функциональные тесты. Глава 2. Моделирование, алгоритмизация и программирование метода. Математическая модель задачи.
По теме: «Целочисленное программирование». Целочисленное программирование возникло в 50-60-е годы нашего века из нужд практики - главным образом в работах американских математиков Дж.Данцига и Р.Гомори.
Входные - выходные данные задачи. Блок - схема решения задачи. Тестирование. Глава 3. Руководство пользователя. Заключение. Список литературы. Приложение. Введение. При рассмотрении целого ряда задач финансового менеджмента и бизнеса необходимо учитывать требование целочисленности используемых переменных.
Такие задачи называются задачами целочисленного программирования. Под задачей целочисленного программирования (ЦП) понимается задача, в которой все или некоторые переменные должны принимать целые значения.
В том случае, когда ограничения и целевая функция задачи представляют собой линейные зависимости, задачу называют целочисленной задачей линейного программирования. В противном случае, когда хотя бы одна зависимость будет нелинейной, это будет целочисленной задачей нелинейного программирования. Особый интерес к задачам ЦП вызван тем, что во многих практических задачах необходимо находить целочисленное решение ввиду дискретности ряда значений искомых переменных. Среди практически важных задач отыскания условного экстремума линейной функции важное место занимают задачи с требованием целочисленности всех (части) переменных. Они получили название задач целочисленного (частично целочисленного) программирования.
Российский Государственный Торгово-Экономический Университет. По теме: «Целочисленное программирование». Выполнила: студентка 2 курса УФФ. 2.1 Решение задач целочисленного программирования графическим. Описание: Курсовая работа по дисциплине МАТЕМАТИЧЕСКИЕ МЕТОДЫ ИССЛЕДОВАНИЯ ОПЕРАЦИЙ на тему Решение задачи целочисленного ЛП с помощью динамического программирования АННОТАЦИЯ Курсовая работа содержит 40 страниц 8 формул 17 таблиц. Курсовая работа: Применение линейного программирования для. Читать курсовую работу online по теме 'Реализация целочисленного программирования (метод Гомори)'. Раздел: Информационное обеспечение. На бирже курсовых и дипломных проектов можно найти готовые бесплатные и платные работы или заказать написание уникальных курсовых работ, дипломов, лабораторных. Наименование: реферат Целочисленная модель математического программирования. Целочисленное программирование. Задача о назначениях" (курсовая работа) .
Целочисленным (иногда его называют также дискретным) программированием называется раздел математического программирования, изучающий экстремальные задачи, в которых на искомые переменные накладывается условие целочисленности, а область допустимых решений конечна. Огромное количество экономических задач носит дискретный, чаще всего целочисленный характер, что связано, как правило с физической неделимостью многих элементов расчета: например, нельзя построить два с половиной завода, купить полтора автомобиля и т. В ряде случаев такие задачи решаются обычными методами, например, симплексным методом, с последующим округлением до целых чисел.
Однако такой подход оправдан, когда отдельная единица составляет очень малую часть всего объема (например, товарных запасов); в противном случае он может внести значительные искажения в действительно оптимальное решение. Целочисленное программирование возникло в 5. Первоначально целочисленное программирование развивалось независимо от геометрии чисел на основе теории и методов математической оптимизации, прежде всего линейного программирования. Однако в последние время исследования в этом направлении все чаще проводятся средствами математики целых чисел. Задачи такого типа весьма актуальны, так как к их решению сводится анализ разнообразных ситуаций, возникающих в экономике, технике, военном деле и других областях.
С появлением эвм, ростом их производительности повысился интерес к задачам такого типа и к математике в целом. Цель курсового проекта: реализовать в среде разработки borland delphi 7 решение задач целочисленного программирования методом гомори.
Задачи курсовой работы. Метод Гомори. 1 Экономическая сущность задачи. Огромное количество экономических задач носит дискретный, чаще всего целочисленный характер, что связано, как правило с физической неделимостью многих элементов расчета: например, нельзя построить два с половиной завода, купить полтора автомобиля и т.
В ряде случаев такие задачи решаются обычными методами, например, симплексным методом, с последующим округлением до целых чисел. Однако такой подход оправдан, когда отдельная единица составляет очень малую часть всего объема (например, товарных запасов); в противном случае он может внести значительные искажения в действительно оптимальное решение. Поэтому разработан метод Гомори для решения целочисленных задач для получения целочисленного результата. Постановка задачи.
Постановка задачи на максимум выглядит следующим образом: При производстве n видов продукции используется m видов ресурсов. Составить план выпуска продукции, обеспечивающий максимальную прибыль. Ответ должен иметь целочисленные значения. Постановка задачи на минимум выглядит следующим образом: Животные должны получать ежедневно m питательных веществ в количестве не менее b. В рацион животных входят корма n видов. Известно: aij (i=1, 2, . Составить суточный рацион кормления животных, обеспечивающий минимальные затраты.
Ответ должен иметь целочисленные значения. Метод решения задач. Согласно методу Гомори задача линейного программирования сначала решается симплексным методом без учета целочисленности переменных. Поставленную описательную задачу переводят в математическую форму (целевая функция и ограничения). Полученное математическое описание приводят к канонической форме.)Каноническую форму приводят к матричному виду.)Ищут первое допустимое решение. Для этого матрица должна быть правильной. Матрица в ЗЛП называется правильной, если она содержит минимум m правильных (базисных) столбцов, где m - число строк в матрице.
Столбец в канонической ЗЛП называется правильным (базисным), если все его элементы равны нулю, кроме единственного равного единице.)Если матрица не является правильной, то ее нужно сделать таковой с помощью искусственного базиса. Для этого в матрицу нужно дописать столько базисных столбцов, чтобы их общее количество вместе с уже имеющимися базисными столбцами составляло m.
После этого переходят к пункту 6. Если искусственный столбец выходит из базиса, то его удаляют из матрицы. Если удалены все искусственные столбцы, то получено первое допустимое решение. Если искусственные элементы не удается вывести из базиса, то система не имеет решений.)Строят последовательность матриц. Нужно определить ведущий столбец, ведущую строку и ведущий элемент.
Элемент, соответствующий ведущей строке, удаляется из базиса, а на его место ставят элемент, соответствующий ведущему столбцу. Составляют уравнение пересчета матрицы, выполняют пересчет, а затем проверяют его результаты на оптимальность. Если решение не оптимально, то заново ограничивают ведущий элемент, ведущую строку и ведущий столбец)Составление дополнительного ограничения (сечения) и решение расширенной задачи обычным симплекс- методом.
Дополнительное ограничение (сечение) отсекает нецелочисленные решения. Функциональные тесты.
Задача 1. Решим прямую задачу линейного программирования симплексным методом, с использованием симплексной таблицы. Определим максимальное значение целевой функции F(X) = 1. Для построения первого опорного плана систему неравенств приведем к системе уравнений путем введения дополнительных переменных . В 1- м неравенстве смысла (?) вводим базисную переменную x. В 2- м неравенстве смысла (?) вводим базисную переменную x. Матрица коэффициентов A = a(ij) этой системы уравнений имеет вид: Базис.
Bx. 1x. 2x. 3x. 4x. F(X0)0- 1. 6- 9. 00. Базис. Bx. 1x. 2x. F(X1)0- 1. 6- 9. 00. Базис. Bx. 1x. 2x.
F(X2)6. 40- 2. 3/5. Базис. Bx. 1x. 2x. F(X3)7. 22/3. 00. Оптимальный план можно записать так: x. X) = 1. 62. 2/3 + 9. В Оптимальном векторе есть нецелые числа, следует применить метод Гомори.
Базис. Bx. 1x. 2x. F(X0)- 7. 22/3. 00- 2. Базис. Bx. 1x. 2x. F(X)- 7. 22/3. 00- 2. Базис. Bx. 1x. 2x.
F(X0)- 6. 80. 00- 2- 7. Базис. Bx. 1x. 2x. F(X0)- 6. 80. 00- 2- 7. Решение получилось целочисленным. Оптимальный целочисленный план можно записать так: Fопт(X) = 6. Хопт(2; 4)Задача 2.
Решим прямую задачу линейного программирования симплексным методом, с использованием симплексной таблицы. Определим максимальное значение целевой функции F(X) = 7x. Для построения первого опорного плана систему неравенств приведем к системе уравнений путем введения дополнительных переменных (переход к канонической форме). В 1- м неравенстве смысла (?) вводим базисную переменную x. В 2- м неравенстве смысла (?) вводим базисную переменную x. Матрица коэффициентов A = a(ij) этой системы уравнений имеет вид: Базис.
Bx. 1x. 2x. 3x. 4x. F(X0)0- 7- 9. 00. Базис. Bx. 1x. 2x. F(X1)0- 7- 9. 00. Базис. Bx. 1x. 2x. F(X2)1. 8- 1. 00.
Базис. Bx. 1x. 2x. F(X3)6. 30. 02. 6/1. Оптимальный план можно записать так: x. X) = 9. 31/2 + 7. В Оптимальном векторе есть нецелые числа, следует применить метод Гомори. Базис. Bx. 1x. 2x.
F(X0)- 6. 30. 0- 2. Базис. Bx. 1x. 2x. F(X)- 6. 30. 0- 2. Базис. Bx. 1x. 2x. F(X0)- 5. 90. 00- 1- 8. Базис. Bx. 1x. 2x. F(X0)- 5. 50. 00.
Решение получилось целочисленным. Оптимальный целочисленный план можно записать так: Fопт(X) = 5. Хопт(4; 3)Задача 3. Решим прямую задачу линейного программирования симплексным методом, с использованием симплексной таблицы.
Определим максимальное значение целевой функции F(X) = 7x. Для построения первого опорного плана систему неравенств приведем к системе уравнений путем введения дополнительных переменных (переход к канонической форме). В 1- м неравенстве смысла (?) вводим базисную переменную x. В 2- м неравенстве смысла (?) вводим базисную переменную x. Матрица коэффициентов A = a(ij) этой системы уравнений имеет вид: Базис. Bx. 1x. 2x. 3x. 4x. F(X0)0- 7- 3. 00.
Базис. Bx. 1x. 2x. F(X1)0- 7- 3. 00. Базис. Bx. 1x. 2x. F(X2)2. 80- 1/5. 12/5. Базис. Bx. 1x. 2x. F(X3)2. 91/2. 00.
Оптимальный план можно записать так: x. X) = 7. 1 + 3. 71/2 = 2. В Оптимальном векторе есть нецелые числа, следует применить метод Гомори.
Базис. Bx. 1x. 2x. F(X0)- 2. 91/2. 00- 1- 1/4. Базис. Bx. 1x. 2x.
F(X)- 2. 91/2. 00- 1- 1/4. Базис. Bx. 1x. 2x.
F(X0)- 2. 90. 0- 1. Решение получилось целочисленным.
Оптимальный целочисленный план можно записать так: Fопт(X) = 2. Хопт(2; 5)Глава 2. Моделирование, алгоритмизация и программирование метода. Математическая модель задачи.
Необходимо найти максимум или минимум функциипри условияхгде Z - множество целых чисел. Для решения задачи ЦЛП может быть применен метод Гомори. Метод Гомори содержит два этапа. Этап 1. Решение исходной задачи обычным симплекс- методом и проверка решения на целочисленноесть. Если решение содержит хотя бы одно дробное значение, то переходят к этапу 2, в противном случае расчет заканчивается.
Целочисленное программирование. Решение задач. Раздел математического программирования, в котором на экстремальные задачи налагается условие дискретности переменных при конечной области допустимых решений, называется дискретным программированием. При наличии условия целочисленности имеется в виду подраздел дискретного программирования – целочисленное программирование. Известна полезность cij, связанная с выполнением i- м исполнителем j- ой работы j=1. Необходимо назначить исполнителей на работы так, чтобы добиться максимальной полезности, при условии, что каждый исполнитель может быть назначен только на одну работу и за каждой работой должен быть закреплен только один исполнитель. Его маршрут должен минимизировать суммарное пройденное расстояние. Иначе, маршрут должен представлять собой замкнутую ломаную, без пересечений в городах- точках.
Координаты такой вершины являются целочисленным решением. Целочисленному минимуму целевой функции будет соответствовать координаты вершины целочисленной решетки, лежащей в области допустимых решений, наиболее близкой к началу координат в направлении вектора С. Целочисленное программирование.
Если среди компонент этого плана нет дробных чисел, то тем самым найдено искомое решение данной задачи. Тогда в оптимальном план ее значение будет , по крайней мере. Ki*. либо больше или равно ближайшему большему целому числу Ki*. Определяя эти числа симплексным методом решения двух задач линейного программирования. F=. Тогда этот план и значение целевой функции и дают решение исходной задачи. Тогда рассматривается вторая задача и в ее оптимальном плане выбирается одна из компонент, значение которой равно дробному числу и строятся две новые задача, аналогично предыдущим. Одна из задач имеет оптимальный целочисленный план, а в оптимальном плане другой задачи есть дробные числа.
Тогда вычисляем значение целевой функции от планов и сравниваем их между собой. Если на целочисленном оптимальном план значение целевой функции больше или равно ее значению в плане, среди компонент которого есть дробные числа, то данный целочисленный план является оптимальным для исходной задачи и дает искомое решение. Тогда рассматриваем ту из задач, для которой значение целевой функции является наибольшим. Строятся новые две задачи. Определяется оптимальный целочисленный план, либо устанавливается неразрешимость задачи. Для решения задачи целочисленного программирования методом ветвей и границ используется сервис Метод ветвей и границ.