Методика решения задач линейного программирования в программной среде Delphi

Размещено на http://www.allbest.ru

Размещено на http://www.allbest.ru

Введение

Методология моделирования долгое время развивалась независимо отдельными науками. Отсутствовала единая система понятий, единая терминология. Лишь постепенно стала осознаваться роль моделирования как универсального метода научного познания. Термин "модель" широко используется в различных сферах человеческой деятельности и имеет множество смысловых значений. Модель - это такой материальный или мысленно представляемый объект, который в процессе исследования замещает объект-оригинал так, что его непосредственное изучение дает новые знания об объекте-оригинале.

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

Процесс моделирования включает три элемента:

· субъект (исследователь),

· 2) объект исследования,

· 3) модель, опосредствующую отношения познающего субъекта и познаваемого объекта.

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

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

Тогда наша система уравнений может быть записана как:

Базисное решение называется допустимым базисным решением или опорным решением, если в нем значения переменных неотрицательны. Если в качестве базисных взяты переменные X1, X2, ..., Xr, то решение {b1, b2,..., br, 0, ..., 0} будет опорным при условии, что b1, b2,..., br ? 0.

Математическая модель данной задачи имеет вид:

Z(X) = c1 x1 + c2x2 + ... + сnхn > max

Xj>0, j = 1, 2, ..., n.

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

1. Общая часть

1.1 Описание предметной области

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

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

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

Составление двойственной задачи включает в себя следующие пункты:

1. Тип оптимума меняется на противоположный, т.е. максимум на минимум, и наоборот.

2. Вектор коэффициентов целевой функции с и столбец ограничений b меняются местами.

3. Матрица ограничений задачи A транспонируется.

4. Множество индексов переменных, на которые наложено условие неотрицательности в прямой задаче (например, хj ? 0 или uj ? 0), определяют номера ограничений, имеющих форму неравенств в двойственной задаче (aju ? сj или aix ? bj).

5. Множество номеров ограничений, имеющих форму неравенств в прямой задаче (например, aix ? bj или aju ? сj), определяют множество индексов переменных, на которые накладывается условие неотрицательности, в двойственной задаче (ui ? 0 или xi ? 0).

Общей задачей линейного программирования называется задача, которая состоит в определении максимального (минимального) значения функции:

При условиях:

где - заданные постоянные величины и .

Функция называется целевой функцией (или линейной формой) задачи, а условия - ограничениями данной задачи.

Канонической или основной задачей линейного программирования называется задача, которая состоит в определении максимального значения функции:

.

При выполнении условий:

Где: .

Если в опорном плане существует хотя бы одна отрицательная координата xi0 и при этом не существует ни одного отрицательного коэффициентах xij разложений векторов-условий Aj, j=1,2, …, n, то задача не имеет решения ввиду несовместности системы ограничений.

Пусть в результате эквивалентных преобразований системы уравнений-ограничений задачи некоторое уравнение приняло вид:

xi0 = xl1x1 + xl2x2 + … + xinxn, где xi0 < 0, a xij ? 0 Vj.

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

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

1. Привести задачу к каноническому виду.

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

3. Если ПДОР не имеет отрицательных координат, то оно является допустимым и оптимальным (по теореме 1.3). Решение задачи заканчивается.

4. Если ПДОР имеет отрицательную координату хi0 < 0, для которой соответствующие коэффициенты разложений всех векторов-условий неотрицательны (хij > 0 Vy), то задача не имеет решения ввиду несовместности системы ограничений. Решение задачи прекращается.

5. Если хотя бы одна координата ПДОР отрицательна, т.е. хi0 < 0, и при этом найдется хотя бы один отрицательный коэффициент хij разложений векторов-условий Аj по базису решения, то переходят к новому решению, на котором значение целевой функции будет ближе к оптимальному. Номер вектора Аk, вводимого в базис, определяется с использованием параметра

?0i = min{|Дj/xij|} = |Дk/xik|,

xij < 0

Номер вектора Аi, выводимого из базиса, находится из условия min{xi0 ?0i} в задаче на максимум или из условия max{-хi0 ?0i} в задаче на минимум.

Далее возвращаются к пункту 3 данного алгоритма.

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

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

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

1.2 Обоснование выбора языка программирования

Мечта программистов о среде программирования, в которой бы простота и удобство сочетались с мощью и гибкостью, стала реальностью с появлением среды Delphi. Она обеспечивала визуальное проектирование пользовательского интерфейса, имела развитый объектно-ориентированный язык Object Pascal (позже переименованный в Delphi) и уникальные по своей простоте и мощи средства доступа к базам данных. Язык Delphi по возможностям значительно превзошел язык Basic и даже в чем-то язык C++, но при этом он оказался весьма надежным и легким в изучении (особенно в сравнении с языком C++). В результате, среда Delphi позволила программистам легко создавать собственные компоненты и строить из них профессиональные программы. Среда оказалась настолько удачной, что по запросам любителей C++ была позже создана среда C++Builder -- клон среды Delphi на основе языка C++ (с расширенным синтаксисом).

Среда Delphi стала, по сути, лучшим средством программирования для операционной системы Windows, но программистов ждало разочарование, если возникало желание перенести программу в другую операционную систему, в частности, в операционную систему Unix.

Алфавит языка Delphi. Язык - совокупность символов, соглашений и правил, используемых для общения. При записи алгоритма решения задачи на языке программирования необходимо четко знать правила написания и использования языковых единиц. Основой любого языка является алфавит (набор знаков, состоящий из букв, десятичных и шестнадцатеричных цифр, специальных символов).

Алфавит Delphi составляют:

ѕ Прописные и строчные буквы латинского алфавита.

ѕ Десятичные цифры.

ѕ Специальные символы: + - * / > < = ; # ` , . : {} [] ( ).

ѕ Комбинации специальных символов, которые нельзя разделять пробелами, если они используются как знаки операций: «:=», «..», «<>», «<=», «>=», «{}».

ѕ Неделимые последовательности знаков алфавита образуют слова, отделенные друг от друга разделителями. Ими могут быть пробел, комментарий или символ конца строки.

Словарь Delphi можно разделить на три группы слов:

ѕ зарезервированные,

ѕ слова, стандартные идентификаторы,

ѕ идентификаторы пользователя.

Зарезервированные слова имеют фиксированное написание и навсегда определенный смысл. Они не могут изменяться программистом и их нельзя использовать в качестве имен для обозначения величин.

Идентификатор - имя (установление соответствия объекта некоторому набору символов). Для обозначения определенных разработчиками языка функций, констант и т.д. служат стандартные идентификаторы. Идентификаторы пользователя - это те имена, которые дает сам программист.

2. Специальная часть

2.1 Экономическая и математическая постановка задачи

Компания производит полки для ванных комнат двух размеров - А и В. Агенты по продаже считают, что в неделю на рынке может быть реализовано до 550 полок. Для каждой полки типа А требуется 2 м2 материала, а для полки типа В - 3 м2 материала. Компания может получить до 1200 м материала в неделю. Для изготовления одной полки типа А требуется 12 мин машинного времени, а для изготовления одной полки типа В - 30 мин; машину можно использовать 160 час в неделю. Если прибыль от продажи полок типа А составляет 3 денежных единицы, а от полок типа В - 4 ден. ед., то сколько полок каждого типа следует выпускать в неделю?

Исходные данные представлены в таблице 1.

Таблица 1 - Исходные данные

Базис	План	x1	x2	x3	x4	x5
х3	550	1	1	1	0	0
х4	1200	2	3	0	1	0
х5	9600	12	30	0	0	1
f	0	-3	-4	0	0	0

Нахождение элементов симплекс-таблицы производится методом прямоугольника.

Математическая формулировка задачи включает:

Переменные, подлежащие оптимизации:

xa - виды выпускаемой продукции (полок),

xb - виды затрат на производство продукции (Время, сырье, работа),

Целевую функцию:

f = 3х1 + 4х2 max, х1 + х2 < 550,

2х1+ 3х2 < 1200,

12х1+ 30х2 < 9600, х1> 0, х2>0.

Ограничения:

х1 + х2 < 550 - в неделю на рынке может быть реализовано до 550 полок.

2х1 + 3х2 < 1200 - Затраты материала.

12х1 + 30х2 < 9600 - Затраты машинного времени.

2.2 Реализация модели математическим методом

Для построения общего метода решения задачи ЛП все модели должны быть представлены в канонической (стандартной) форме, которая удовлетворяет следующим условиям:

1) все ограничения и целевая функция должны быть записаны в виде равенств с неотрицательной правой частью;

2) значения всех переменных модели должны быть неотрицательны;

3) целевая функция подлежит максимизации или минимизации, где xj - вспомогательные переменные, включаемые в уравнения ограничений (остаточные для неравенства типа ? и избыточные для неравенства типа ?) для приведения неравенств к виду равенств.

Соответствующая линейная модель, приведенная к стандартной (канонической) форме имеет следующий вид:

3х1 + 4х2 -> max.

х1 + х2 < 550

2х1 + 3х2 < 1200

12х1 + 30х2 < 9600.

х3, х4, х5 - дополнительные переменные.

Таким образом, приходим к задаче линейного программирования.

f = 3х1 + 4х2 max, х1 + х2 < 550,

2х1+ 3х2 < 1200,

12х1+ 30х2 < 9600, х1> 0, х2>0 , х3>0, х4>0, х5>0.

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

Решение:

F=3x1+4x2->max

x1+x2<=550

2x1+3x2<=1200

12x1+30x2<=9600

F=3x1+4x2+0x3+0x4+0x5->max

550/1=550

1200/3=400

9600/30=320

В качестве опорного плана выберем X0=(0, 0, 550, 1200, 9600). Произведем вычисления:



Составим симплекс-таблицу (Таблица 2).

Таблица 2 - Таблица результатов

Базис	План	x1	x2	x3	x4	x5
х3	230	3/5	0	1	0	-1/30
х4	240	4/5	0	0	1	-1/10
х2	320	2/5	1	0	0	1/30
f	1280	-7/5	0	0	0	2/15

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

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



Составим симплекс-таблицу (Таблица 3).

Таблица 3 - Таблица результатов

Базис	План	x1	x2	x3	x4	x5
x3	50	0	0	1	-3/4	1/24
x1	300	1	0	0	5/4	-1/8
x2	200	0	1	0	-1/2	1/12
f	1700	0	0	0	7/4	-1/24

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



Составим симплекс-таблицу (Таблица 4).

Таблица 4 - Таблица результатов

Базис	План	x1	x2	x3	x4	x5
x5	1200	0	0	24	-18	1
x1	450	1	0	3	-1	0
x2	100	0	1	-2	1	0
f	1750	0	0	1	1	0

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

Решение двойственной задачи необходимо для проверки правильности решения ЗЛП. В нашем случае для проверки на правильность решения нахождения оптимального плана, подставим найденный базис в целевую функцию. Т.е. условие оптимальности соответствует найденному решению следовательно - план оптимален выбранным методом.

Fmax=3*450+4*100+x3*0+x4*0+x5=1750

2.3 Структурная и функциональная схемы программы

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

Рисунок 2.1 - Структурная схема программы

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

Рисунок 2.2 - Функциональная схема программы

2.4 Описание процедур, функций и модулей

Объявление модуля:

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

Стандартные модули языка Delphi. В состав среды Delphi входит великолепный набор модулей, возможности которых удовлетворят даже самого привередливого программиста. Все модули можно разбить на две группы: системные модули и модули визуальных компонентов.

К системным модулям относятся System, SysUtils, ShareMem, Math. В них содержатся наиболее часто используемые в программах типы данных, константы, переменные, процедуры и функции. Модуль System - это сердце среды Delphi; содержащиеся в нем подпрограммы обеспечивают работу всех остальных модулей системы. Модуль System подсоединяется автоматически к каждой программе и его не надо указывать в операторе uses.

Модули визуальных компонентов (VCL - Visual Component Library) используются для визуальной разработки полнофункциональных GUI-приложений - приложений с графическим пользовательским интерфейсом (Graphical User Interface). Эти модули в совокупности представляют собой высокоуровневую объектно-ориентированную библиотеку со всевозможными элементами пользовательского интерфейса: кнопками, надписями, меню, панелями и т.д. Кроме того, модули этой библиотеки содержат простые и эффективные средства доступа к базам данных. Данные модули подключаются автоматически при помещении компонентов на форму.

Описание процедур:

procedure TForm2.Button1Click(Sender: TObject);

Эта процедура осуществляет закрытие титульного и листа и выход из программы.

procedure TForml.Button2Click(Sender: TObject);

Эта процедура открывает главное меню программы и убирает с экрана титульный лист.

procedure TForm2.Button1Click(Sender: TObject);

Эта процедура открывает окно с выбором метода решения транспортной задачи и убирает с экрана окно меню.

procedure TForm2.Button2Click(Sender: TObject);

Эта процедура открывает окно содержащие информацию о разработанной программе и убирает с экрана окно меню.

procedure TForm2.Button3Click(Sender: TObject);

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

procedure TForm2.Button4Click(Sender: TObject);

Эта процедура открывает окно о разработчике, и убирает окно меню.

procedure TForm2.Button5Click(Sender: TObject);

Эта процедура закрывает окно меню и выходит из программы.

procedure TForm3.Button1Click(Sender: TObject);

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

procedure TForm3.Button3Click(Sender: TObject);

Эта процедура закрывает окно с решениями транспортной задачи тремя методами и выводит на экран форму с решением задачи методом минимальной стоимости:

procedure TForm3.Button4Click(Sender: TObject);

Эта процедура закрывает окно с решениями транспортной задачи тремя методами и выводит на экран форму с решением задачи методом двойного предпочтения:

procedure TForm2.Button2Click(Sender: TObject);

procedure TForm2.Button3Click(Sender: TObject);

procedure TForm2.Button4Click(Sender: TObject);

Эти процедуры позволяют пользователю отправиться из главного меню в любой пункт программы: «Форма решения», «Руководство пользователя», «Сведения о разработчике», «Выход».

procedure STEP-BY-STEP;

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

procedure TForm4.Label2Click(Sender: TObject);

procedure TForm4.Label3Click(Sender: TObject);

procedure TForm4.Label4Click(Sender: TObject);

procedure TForm4.Label5Click(Sender: TObject);

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

procedure TForm1.Button8Click(Sender: TObject);

Эта процедура выполняет расчет по формулам, подставляет введенные значения и в итоге выполнения записывает результат в переменную.

procedure TForm1.Button9Click(Sender: TObject);

Эта процедура выводит ответ в текстовом поле.

procedure TForm1.Button2Click(Sender: TObject);

Эта процедура заполняет поля ввода исходными данными в соответствии с заданием на курсовой проект.

procedure TForm3.Button4Click(Sender: TObject);

procedure TForm4.Button1Click(Sender: TObject);

Эти процедуры закрывают окно с и выводит на экран форму с выбором пункта меню.

procedure ochistka;

Эта процедура очищает поля ввода и вывода, освобождает переменные от значения, которое в них хранится.

2.5 Таблица идентификаторов

Идентификатор - имя для обозначения определенных разработчикам

языка функций, констант и т.д. служат стандартные идентификаторы.

Идентификаторы пользователя - это те имена, которые дает сам программист.

Таблица 5 - Таблица идентификаторов

Название	Назначение	Тип
i	Счетчики циклов	Integer
zna4,zna4TMP,zna4TMP2	Промежуточные переменные.	Integer
MinEl	Минимальное значение	Double
Summ	Сумма	Integer
Boo ,reshil,dv	Переменные логического типа	Boolean
K, m, a, b, с	Вспомогательные переменные	Integer
Count,Count2	Размер таблицы	Integer

симплекс программный идентификатор пошаговый

Заключение

Данная курсовая работа несет в себе не только приобретение навыков по программированию в среде Delphi, а так же приобретение и закрепление практических навыков по предмету «Моделирование экономических и производственных процессов»

В ходе курсового проектирования мною были приобретены и закреплены навыки:

- Нахождение оптимального плана симплексным методом;

- Освоение библиотек (Delphi) с поддержкой математических функций и процедур;

- Написание приложения для расчета и нахождения оптимального плана;

- Подключение справочной информации к программе.

Данное приложение работает не только с исходными значениями, взятыми из задачи к курсовому проектированию, но и с любыми данными вводимыми пользователем.

Размещено на Allbest.ru