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

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

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

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, который не дружит с динамическими библиотеками. А потому должен включать в себя все используемые пакеты. Тоже самое касается и собственно среды разработки, которую вы должны пересобрать каждый раз при добавлении нового пакета.