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

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

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

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

 

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

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

 

 

 

 

 

 

 

 

 

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

 

 

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

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

 

 

 

 

 

Выполнил:

студент группы 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 неизвестных, которые выразим через остальные неизвестные. Для определенности предположим, что выбраны первые, идущие подряд, неизвестные X1, X2, ..., Xr. Тогда наша система уравнений может быть записана как

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

Придавая определенные значения свободным переменным и вычисляя значения базисных (выраженных через  свободные), мы будем получать различные решения нашей системы ограничений. Таким образом, можно получить любое ее решение. Нас будут интересовать особые решения, получаемые в случае, когда свободные переменные равны нулю. Такие решения называются базисными, их столько же, сколько различных базисных видов у данной системы ограничений. Базисное решение называется допустимым базисным решением или опорным решением, если в нем значения переменных неотрицательны. Если в качестве базисных взяты переменные X1, X2, ..., Xr, то решение {b1, b2,..., br, 0, ..., 0} будет опорным при условии, что b1, b2,..., br ≥ 0.

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

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

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

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

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

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

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

2)  Графический метод-основан на геометрической интерпретации задачи линейного программирования и применяется в основном при решении задач двумерного пространства и только некоторых задач трёхмерного пространства, так как довольно трудно построить многогранник решений, который образуется в результате пересечения полупространств. Задачу пространства размерности больше трёх изобразить графически вообще невозможно.

3) Метод Гомори- при решении многих задач (планирование мелкосерийного производства, распределение кораблей по путям сообщения, выработка суждений типа "да-нет" и т.п.) нецелочисленное решение не имеет смысла. Попытка тривиального округления до целых значений приводит либо к нарушению ограничений задачи, либо к недоиспользованию ресурсов. Как мы имели возможность убедиться, для произвольной линейной программы (за исключением программ типа классической транспортной задачи, где коэффициенты матрицы ограничений равны 1 или 0) гарантировать целочисленность решения невозможно. 
 
В случае двухмерной задачи проблема решается относительно просто путем выявления всех целочисленных точек, близких к границе множества планов, построения выпуклого множества планов, содержащего все целочисленные планы и решения задачи над этим множеством. 
 
B общем случае выдвигается идея последовательного отсечения нецелочисленных оптимальных планов: обычным симплексным методом отыскивается оптимальный план и, если он нецелочисленный, строится дополнительное ограничение, отсекающее найденный оптимальный план, но не отсекающее ни одного целочисленного плана. 
 
Эта идея, принадлежащая Д. Данцигу и Р. Гомори, впервые была представлена в форме дополнительного ограничения: 
 (3.1) 
(сумма небазисных компонент оптимального плана должна быть отлична от нуля; хотя бы одна из небазисных компонент должна быть ненулевой). В самом деле, оптимальный план с нулевыми значениями небазисных компонент этому условию не удовлетворяет, что подтверждает отсечение этого плана от исходного множества.

 

 

 

 

 

 

 

 

                                  3  Описание выбранного алгоритма

 

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

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

Метод Гомори получил  своё название по имени математика, первым разработавшим в 1957-1958 годах  алгоритм, до сих пор широко используемый для решения целочисленных задач линейного программирования. Каноническая форма задачи целочисленного программирования позволяет доступно и в полном объёме раскрыть преимущества этого метода.

Метод Гомори применительно к линейному  программированию существенно усложняет задачу нахождения оптимальных значений. Ведь целочисленность является основным условием, дополнительно ко всем параметрам задачи. Нередки случаи, когда задача, имея допустимые (целочисленные) планы, при наличии у целевой функций ограничений на допустимом множестве, в решении не приходит к достижению максимума. Это происходит по причине отсутствия именно целочисленных решений. Без этого же условия, как правило, в виде решения находится подходящий вектор.

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

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

Метод Гомори, по сути, предполагает построение ограничений, которые отсекают решения, не являющиеся нецелочисленными. При  этом не происходит отсечения ни одного решения целочисленного плана.

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

 

                                           4 Средства решения задачи

 

  Borland Delphi представляет собой средство разработки приложений для Microsoft Windows. Delphi является мощным и простым в использовании инструментом для создания автономных программ, обладающих графическим интерфейсом (GUI), или 32-битных консольных приложений (программ, которые не имеют графического интерфейса). 
   В сочетании с Borland Kylix, программисты Delphi могут создавать из одного исходного текста приложения и для Windows и для Linux, и это открывает новые возможности и увеличивает потенциальную отдачу от усилий, вложенных в изучение Delphi. В Delphi используется кросс-платформенная библиотека компонентов CLX и визуальные дизайнеры для создания высокопроизводительных приложений для Windows, которые повторной компиляцей можно легко превратить в приложения для Linux. 
   Delphi является первым языком программирования, обладающим простой в использовании средой для быстрой разработки приложений, разрушающей барьеры между языками высокого уровня, и языками, на низком уровне разговаривающими с системой на языке битов и байтов. 
   При создании графического интерфейса приложений Delphi, у вас все возможности языка программирования Object Pascal, "завернутого" в среду RAD. Такие компоненты окна графического пользовательского интерфейса, как формы, кнопки и списки объектов, включены в состав Delphi. Это означает, что вам не нужно писать никакого кода при добавлении их в ваше приложение. Вы просто "кладёте" их на вашу Форму, как в графическом редакторе. Вы можете также добавить на Форму элементы управления ActiveX, для создания в считанные минуты специализированных программ таких, например, как веб-браузеры. Delphi позволяет разработчикам дизайна внедрять в интерфейс новые элементы и кодировать их события одним щелчком мыши. 
   Delphi поставляется в различных конфигурациях, настроенных на потребности различных предприятий. В Delphi вы можете писать программы для Windows быстрее и легче, чем это было возможно раньше.

Паскаль

 

   Лучшим  способом представить что такое Delphi является Object Pascal на основе визуальной среды разработки. Delphi основан на Object Pascal, языке, аналогичном объектно-ориентированному C++, а в некоторых случаях даже лучше. Для разработчиков не имеющих опыта работы в Паскале, Delphi имеет шаблоны своих структур на Паскале, что ускоряет процесс изучения языка. 
   Компилятор Delphi упаковывает приложения в компактные исполняемые файлы, причем нет необходимости в громоздких библиотеках DLL - большое удобство, я должен сказать. 
   Библиотека Visual Component Library (автономные бинарные части программного обеспечения, которые выполняют некоторые конкретные предопределенные функции), или VCL, Delphi является объектно-ориентированной базой. В этой богатой библиотеке вы найдете классы для таких визуальных объектов Windows как окна, кнопки и т.д., а также классы для пользовательских элементов управления таких как таймер и мультимедийный плеер, наряду с невизуальными объектами, такими как список строк, таблицы базы данных, потоки и т.д.

Базы  данных

 

   Delphi может получать доступ ко многим типам баз данных. Используя BDE (Borland Database Engine - механизм доступа к базам данных), формы и отчеты, которые вы создаете, получают доступ к локальным базам данных, таким как Paradox и DBase, сетевых баз данных SQL Server, InterBase, также как и SysBase, и любые источники данных, доступные даже через ODBC (открытая связь с базами данных).

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

                              4.1  Технические средства решения задачи

 

Процессор: AMD Athlon™ II X4 645 Processor 3.10 GHz

Оперативная память: 4 Gb

Видеоадаптер: NVIDIA GeForce 440 GTX

Жёсткий диск: HDD 1000 Gb Samsung

Клавиатура: A4TECH X7

Мышь: A4TECH X7

Монитор: Envision P971wL

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

                             4.2 Инструментальные средства разработки

  Система программирования Delphi версии 7 фирмы Enterprise (Borland) предоставляет наиболее широкие возможности для программирования приложений ОС Windows.

Delphi – это продукт  Borland International для быстрого создания приложений. Процесс создания интерфейса будущей программы напоминает забаву с игровым компьютерным конструктором. Поэтому RAD-среды еще называют визуальными средами разработки: какими мы видим рабочие и диалоговые окна программы при проектировании, такими они и будут, когда программа заработает.

  Высокопроизводительный инструмент визуального построения приложений включает в себя настоящий компилятор кода и предоставляет средства визуального программирования, несколько похожие на те, что можно обнаружить в Microsoft Visual Basic (она не является RAD-системой) или в других инструментах визуального проектирования. В основе Delphi лежит язык Object Pascal, который является расширением объектно-ориентированного языка Pascal. В Delphi также входят локальный SQL-сервер, генераторы отчетов, библиотеки визуальных компонентов, и прочее, необходимое для того, чтобы чувствовать себя совершенно уверенным при профессиональной разработке информационных систем или просто программ для Windows-среды.

    Прежде всего Delphi предназначен для профессиональных разработчиков, желающих очень быстро разрабатывать приложения в архитектуре клиент-сервер. Delphi производит небольшие по размерам высокоэффективные исполняемые модули (.exe и .dll), поэтому в Delphi должны быть, прежде всего, заинтересованы те, кто разрабатывает продукты на продажу. С другой стороны небольшие по размерам и быстро исполняемые модули означают, что требования к клиентским рабочим местам существенно снижаются – это имеет немаловажное значение и для конечных пользователей.

Преимущества Delphi по сравнению  с аналогичными программными продуктами.       

– быстрота разработки приложения (RAD);       

– высокая производительность разработанного приложения;      

– низкие требования разработанного приложения к ресурсам компьютера;      

– наращиваемость за счет встраивания  новых компонент и инструментов в среду Delphi;      

– возможность разработки новых  компонентов и инструментов собственными средствами Delphi (существующие компоненты и инструменты доступны в исходных кодах);      

– удачная проработка иерархии объектов.

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

   Основным конкурентом Borland Delphi 7 является её родной брат – RAD-среда Borland C++ Builder, технология работы с которой полностью совпадает с технологией, принятой в Delphi 7. Только в Delphi программный код пишется на языке программирования Паскаль, точнее на его объектно-ориентированной версии ObjectPascal, а не на языке C++.

Для того чтобы обосновать, почему наш выбор остановился на Borland Delphi 7, достаточно просто перечислить некоторые недостатки языка С++ по сравнению с ObjectPascal:

1. Надо делать много  инициализации (регистрировать класс  окна, организовывать цикл обработки  сообщений, создавать оконную функцию, пиктограмму и прочее…) и частично быть системным программистом. На Delphi-же системное программирование уже встроено и инициализация работает по умолчанию, поэтому программист главный упор делает на своих алгоритмах, а не на организации вспомогательных работ.

2. Значительно большая,  по сравнению с Object Pascal, сложность  языка, даже, несмотря на компактность  кода, возникают сложности в его  восприятии.

3. Одна особенность,  на мой взгляд, языка С++ очень  портит этот язык - он чувствителен  к регистру символов, т.е. переменная A и переменная a - это разные переменные.

4. В Delphi классы (объекты) могут располагаться только в динамической памяти, а в  C++ в любой памяти (статическая, стек, динамическая). Это добавляет безопасности программирования в Delphi.

Также существует среда  программирования Lazarus, относительно молодая, внешне похожая на Delphi. Данный продукт - IDE для компилятора FreePascal Compiler. Распространяется бесплатно по GNU General Public License (или просто GPL), но Lazarus ещё не является средой программирования профессионального уровня, для него разработано мало компонентов, при стандартных настройках. Также размеры разрабатываемых приложений тоже оставляют желать лучшего. В первую очередь это связано с особенностью компилятора FreePascal, который не дружит с динамическими библиотеками. А потому должен включать в себя все используемые пакеты. Тоже самое касается и собственно среды разработки, которую вы должны пересобрать каждый раз при добавлении нового пакета.