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

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

       5  Информационное обеспечение задачи

 

                                         5.1 Входная информация

 

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

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

 

 

 

 

 

 

 

 

 

                               5.2 Выходная информация

 

Для проверки правильности работы разрабатываемого продукта, проведем тестирование по ранее решенным задачам  в главе 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)

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

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

                      6  Программное обеспечение задачи

 

Borland Delphi (по-русски обычно произносят [бо́рланд дэ́льфи] или [бо́рланд дэ́лфи]) — это интегрированная среда разработки ПО фирмы Borland. Delphi является средой RAD (от англ. rapid application development — быстрая разработка приложений).

Говоря о том или  ином средстве разработки приложений всегда хочется понять какие тенденции приводят к его появлению. Borland Delphi не является исключением из правил. Итак, что же мы имели к середине 90-х? 
Одно направление - объектно-ориентированный подход, хорошо структурирующий задачу, как таковую, так и ее решение в виде прикладной системы.  
Другое направление, возникшее во многом благодаря объектной ориентации, - визуальные средства быстрой разработки приложений (RAD - Rapid Application Development), основанные на компонентной архитектуре. 
Третья тенденция - использование компиляции, а не интерпретации. Это объясняется тем, что скоростные характеристики компилируемых приложений в десятки раз лучше, чем у систем, использующих интерпретатор. При этом повышается легкость отчуждаемости готовых систем, так как отпадает необходимость "таскать за собой" сам интерпретатор (run-time), выполненный обычно в виде динамической библиотеки и занимающий в лучшем случае несколько сотен килобайт (а большинстве случаев - два-три мегабайта). Отсюда и меньшая ресурсоемкость у скомпилированных систем. 
Четвертая тенденция - возможность работы с базами данных универсальными (единообразными) методами. Если мы попытаемся оценить процент систем, которые так или иначе требуют обработки структурированной информации (как для внутрикорпоративного использования, так и для коммерческого или иного распространения), то окажется, что цифра 60- 70% может представлять лишь нижнюю границу. Важным свойством средств обеспечения доступа к базам данных является их масштабируемость, как возможность не только количественного, но и качественного роста системы. Например, обеспечение перехода от локальных ,в том числе, файл-серверных данных к архитектуре клиент-сервер или тем более к многоуровневой N-tier схеме.

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

    1)Delphi использует язык 3-го поколения Object Pascal, обладающий полной реализаций основных признаков объектной ориентации (инкапсуляция, наследование, полиморфизм), поддержкой RTTI-RunTime Type Information и встроенной обработкой исключительных ситуаций (Exception handling). Компонентная архитектура Delphi является прямым развитием поддерживаемой объектной модели. Все компоненты являются объектными типами (классами), с возможностью неограниченного наследования. Компоненты Delphi поддерживают PME-модель (Property, Method, Events), позволяющую изменять поведение компонентов без необходимости создания новых классов.

     2) Delphi 2 Client/Server Suite включает систему контроля версий Intersolv       PVCS, поддерживает работу со словарем данных (Data Dictionary) и Репозитарием объектов (Object Repository). Среда визуальной разработки Delphi позволяет единообразно работать как с предопределенными, так и с пользовательскими компонентами, которые разрабатываются на том же языке (Object Pascal), на котором создаются и конечные приложения.

Borland Database Engine (BDE) обеспечивает  единообразную работу с локальными  данными (Paradox, dBase) и серверами  БД (Oracle, Sybase, MS SQL Server, InterBase и т.д.), за счет применения навигационных методов доступа к серверным СУБД (двунаправленные курсоры, закладки и т.п.) и SQL - к локальным форматам (подмножество Local SQL).

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

                        6.1    Описание программного продукта

 

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

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

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

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

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

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

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

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

 

 

 

 

 

 

 

 

 

 

 

 

 

 

                                      6.2   Руководство пользователю.

     

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

 

 

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

 

 

 

 

 

 

 

 

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

 

 

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

 

 

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

 

 

 

 

 

 

 

 

                                                 Заключение

 

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

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

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

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

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

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

                                                    Литература

1. Акулич И.Л. Математическое программирование в примерах и задачах: учеб.пособие для ВУЗов / И. Л. Акулич. – М.: Высшая школа, 1986.
2. Алгоритм Гомори//Википедия. [Электронный ресурс]. URL:http://ru.wikipedia.org/wiki/Алгоритм_Гомори
3. О.Л Голицына, Попов И.И. Основы алгоритмизации и программирования. М.: ФОРУМ - ИНФРА-М, 2006.
4. Лященко И.Н. Линейное и нелинейное программирование, М.: Наука, 1985.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

                                       Приложение

 

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]:='Áï';

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);