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

Министерство образования  и науки Российской Федерации

Федеральное государственное  бюджетное образовательное учреждение высшего профессионального образования 

«Южно-Российский государственный  университет экономики и сервиса»

 

Ростовский  технологический институт сервиса и туризма

Электротехнический  колледж

 

 

 

 

 

 

 

 

 

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

 

 

по дисциплине «МАТЕМАТИЧЕСКИЕ МЕТОДЫ»

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

 

 

 

 

 

Выполнил:

студент группы 3-51 ПВМ

Оленбергер В.И.

 

 

Руководитель:

к.т.н, доцент, зав. кафедрой «Математика и информатика» РТИСТ

Акишин Б.А.

 

 

 

Ростов-на-Дону, 2013

Министерство образования  и науки Российской Федерации

Федеральное государственное  бюджетное образовательное учреждение высшего профессионального образования

«Южно-Российский государственный  университет экономики и сервиса»

 

Ростовский  технологический институт сервиса  и туризма

Электротехнический  колледж

 

 

 

 

ЗАДАНИЕ НА КУРСОВУЮ РАБОТУ

 

 

по дисциплине «МАТЕМАТИЧЕСКИЕ МЕТОДЫ»

для студента 3 курса группы 3-51 ПВМ

Оленбергера Владислава Игоревича

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

             

                    

 

(утверждена цикловой  комиссией Математических и естественнонаучных  дисциплин,

  протокол №   5  от «  10  »  января 2013г.)

 

 

1. Исходные данные: вариант № 7 утвержденных тем курсовых работ по дисциплине «Математические методы» на 2012-13 уч.г.
2. Объем курсовой работы: пояснительная записка 20-25 стр. и результаты компьютерных расчетов
3. Срок представления курсовой работы: 10.06.2013

 

 

Задание выдал: председатель цикловой комиссии ________ Т.Ф. Кружилина

 

 Задание получил:  студент  ____________________________В.И.Оленбергер

 

     « 20 »     января  2013 г.

 

Цель курсовой работы:

 

1. Изучить предлагаемый метод  математического моделирования и его модификации.
2. Определить круг задач, решаемых с помощью это метода.
3. Изучить математическое описание метода и алгоритмов его реализации.
4. Составить содержательный пример задачи, эффективно решаемой данным методом.
5. Изучить доступные программные реализации метода.
6. Разработать программный продукт рассматриваемой задачи, содержащий процедуры ввода исходной информации, расчетную часть (собственную или известную) и процедуры вывода результатов. Пользовательский интерфейс должен быть простым, наглядным и удобным в использовании. Расчетная часть должна  функционировать при любых допустимых значениях исходных данных.
7. Сделать анализ полученных результатов и выводы по теме.

Пояснительная записка  должна содержать следующие разделы:

Введение

1. Постановка задачи.
2. Обзор и анализ существующих методов или моделей решения задачи.
3. Описание выбранного алгоритма.
4. Средства решения задачи.
1. Технические средства решения задачи.
2. Инструментальные средства разработки.
5. Информационное обеспечение задачи
1. Входная информация;
2. Выходная информация.
6. Программное обеспечение задачи.
1. Описание программного продукта;
2. Руководство пользователю.

Заключение

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

Приложения

 

Дата выдачи задания    20.01.2013

Срок окончания             10.06.2013

Преподаватель        ___________________ Акишин Б.А.

 

                                                    Введение

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

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

Рассмотрим алгоритм решения задачи линейного целочисленного программирования этим методом.

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

- оно должно быть  линейным;

- должно отсекать найденный  оптимальный нецелочисленный план;

- не должно отсекать  ни одного целочисленного плана.

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

 

 

 

 

 

 

 

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

 

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

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

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

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

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

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

• Изучить предметную область ЗЦП
• Определить входные, выходные данные задач линейного программирования
• Определить метод решения целочисленного программирования
• Выполнить структурное программирование задачи
• Спроектировать интерфейсные формы "Gomori"
• Разработать программный продукт "Gomori"
• Произвести анализ надежности и качества ПП "Gomori"

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

     2 Обзор и анализ существующих методов или моделей решения задачи

 

Существует несколько методов решения задач целочисленного программирования:

1)Симплекс метод- является основным в линейном программировании. Решение задачи начинается с рассмотрений одной из вершин многогранника условий. Если исследуемая вершина не соответствует максимуму (минимуму), то переходят к соседней, увеличивая значение функции цели при решении задачи на максимум и уменьшая при решении задачи на минимум. Таким образом, переход от одной вершины к другой улучшает значение функции цели. Так как число вершин многогранника ограничено, то за конечное число шагов гарантируется нахождение оптимального значения или установление того факта, что задача неразрешима.

Этот метод  является универсальным, применимым к  любой задаче линейного программирования в канонической форме. Система ограничений здесь - система линейных уравнений, в которой количество неизвестных больше количества уравнений. Если ранг системы равен r, то мы можем выбрать r неизвестных, которые выразим через остальные неизвестные. Для определенности предположим, что выбраны первые, идущие подряд, неизвестные X₁, X₂, ..., X_r. Тогда наша система уравнений может быть записана как

К такому виду можно  привести любую совместную систему, например, методом Гаусса. Правда, не всегда можно выражать через остальные первые r неизвестных (мы это сделали для определенности записи). Однако такие r неизвестных обязательно найдутся. Эти неизвестные (переменные) называются базисными, остальные свободными.

Придавая определенные значения свободным переменным и вычисляя значения базисных (выраженных через  свободные), мы будем получать различные решения нашей системы ограничений. Таким образом, можно получить любое ее решение. Нас будут интересовать особые решения, получаемые в случае, когда свободные переменные равны нулю. Такие решения называются базисными, их столько же, сколько различных базисных видов у данной системы ограничений. Базисное решение называется допустимым базисным решением или опорным решением, если в нем значения переменных неотрицательны. Если в качестве базисных взяты переменные X₁, X₂, ..., X_r, то решение {b₁, b₂,..., b_r, 0, ..., 0} будет опорным при условии, что b₁, b₂,..., b_r ≥ 0.

Симплекс-метод  основан на теореме, которая называется фундаментальной теоремой симплекс-метода. Среди оптимальных планов задачи линейного программирования в канонической форме обязательно есть опорное решение ее системы ограничений. Если оптимальный план задачи единственен, то он совпадает с некоторым опорным решением. Различных опорных решений системы ограничений конечное число. Поэтому решение задачи в канонической форме можно было бы искать перебором опорных решений и выбором среди них того, для которого значение F самое большое. Но, во-первых, все опорные решения неизвестны и их нужно находить, a, во-вторых, в реальных задачах этих решений очень много и прямой перебор вряд ли возможен. Симплекс-метод представляет собой некоторую процедуру направленного перебора опорных решений. Исходя из некоторого, найденного заранее опорного решения по определенному алгоритму симплекс-метода мы подсчитываем новое опорное решение, на котором значение целевой функции F не меньше, чем на старом. После ряда шагов мы приходим к опорному решению, которое является оптимальным планом.

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

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

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

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