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

ЛИЧНЫЙ КАБИНЕТ 

 

Здравствуйте гость!

 

Логин:

Пароль:

 

Запомнить

 

 

Забыли пароль? Регистрация

Повышение уникальности

Предлагаем нашим посетителям воспользоваться бесплатным программным обеспечением «StudentHelp», которое позволит вам всего за несколько минут, выполнить повышение уникальности любого файла в формате MS Word. После такого повышения уникальности, ваша работа легко пройдете проверку в системах антиплагиат вуз, antiplagiat.ru, etxt.ru или advego.ru. Программа «StudentHelp» работает по уникальной технологии и при повышении уникальности не вставляет в текст скрытых символов, и даже если препод скопирует текст в блокнот – не увидит ни каких отличий от текста в Word файле.

Результат поиска


Наименование:


Курсовик Целочисленное программирование.Метод отсекающих плоскостей

Информация:

Тип работы: Курсовик. Предмет: Программирование. Добавлен: 14.11.2013. Сдан: 2012. Страниц: 31. Уникальность по antiplagiat.ru: < 30%

Описание (план):


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

Белгородский государственный технологический университет
им. В. Г. Шухова


Институт ИТиУС


Кафедра информационных технологий


Курсовая работа
по математическим методам кибернетики
на тему:


«Целочисленное программирование.
Метод отсекающих плоскостей»


Белгород, 2012г.
Содержание
Введение 3
1. Постановка задачи и определение основных требований к разрабатываемому программному средству 4
1.1 Основание для разработки 4
1.2 Назначение программного средства и область применения 4
1.3 Требования к программному средству 4
1.3.1 Требования к функциональным характеристикам 4
1.3.2 Требования к надежности 4
1.3.3 Отказы из-за некорректных действий оператора 4
2. Условия эксплуатации 5
2.1 Климатические условия эксплуатации 5
2.2 Требования к составу и параметрам технических средств 5
2.3 Требования к информационно - программной совместимости 5
3. Теоретические сведения 6
3.1 Основные понятия линейного программирования 6
3.3 Метод Гомори (метод отсекающих плоскостей) 9
3.5 Пример решения 12
4. Проектирование программного средства и программная реализация 14
4.1 Разработка модульной структуры 14
4.2 Описание структур, типов данных и глобальных переменных 14
4.3 Описание процедур и функций 15
4.4 Разработка алгоритма программы 16
Заключение 22
Список литературы 23
Приложение 1. Руководство пользователя 24
Приложение 2. Исходный код программы 25


?
Введение

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

1. Постановка задачи и определение основных требований к разрабатываемому программному средству
1.1 Основание для разработки
Данное программное средство создается в соответствии с учебным планом специальности «Информационные технологии» и в соответствии с заданием на курсовую работу по дисциплине «Математические методы кибернетики».
1.2 Назначение программного средства и область применения
Разрабатываемое программное средство предназначено для решения задач о целочисленном программировании. В качестве метода решения выбран метод отсекающих плоскостей (метод Гомори).
1.3 Требования к программному средству

1.3.1 Требования к функциональным характеристикам
Основные требования к программному средству по функциональному набору:
- возможность удобного ввода данных;
- возможность изменения вводимых данных;
- возможность просмотра найденного решения.
1.3.2 Требования к надежности
Программа должна предусматривать ошибочные действия пользователя.
1.3.3 Отказы из-за некорректных действий оператора
Отказы системы возможны вследствие некорректных действий оператора (пользователя) при взаимодействии с программой. Во избежание возникновения отказов программы следует внимательно изучить руководство пользователя.


2. Условия эксплуатации
2.1 Климатические условия эксплуатации
Носитель, на который записана программа, не должен подвергаться грубому внешнему воздействию. Хранить при влажности воздуха не более 70% и температуре от -200С до 850С.
2.2 Требования к составу и параметрам технических средств
Для работы программы необходимо наличие IBM совместимого компьютера с операционной системой Microsoft Windows XP, наличие мыши и клавиатуры. Требования к свободному дисковому пространству не менее 11Мб.
Требования к информационно - программной совместимости
Программа корректно работает под управлением ОС Windows XP.
Базовый язык программирования – Delphi
?
3. Теоретические сведения
3.1 Основные понятия линейного программирования

Линейное программирование — раздел математического программирования, применяемый при разработке методов отыскания экстремума линейных функций нескольких переменных при линейных дополнительных ограничениях, налагаемых на переменные. По типу решаемых задач его методы разделяются на универсальные и специальные. С помощью универсальных методов могут решаться любые задачи линейного программирования (ЗЛП). Специальные методы учитывают особенности модели задачи, ее целевой функции и системы ограничений.
Особенностью задач линейного программирования является то, что экстремума целевая функция достигает на границе области допустимых решений. Классические же методы дифференциального исчисления связаны с нахождением экстремумов функции во внутренней точке области допустимых значений. Отсюда — необходимость разработки новых методов.
Формы записи задачи линейного программирования:
Общей задачей линейного программирования называют задачу
? max??(min) Z=?_(j=1)^n-?c_j x_(j ) (3.1.1)?
при ограничениях
{-(?_(j=1)^n-?a_ij x_j ??b_i при (i=1..m_1 ) (3.1.2)@?_(j=1)^n-?a_ij x_j ?=b_i при (i=m_1+1..m_2 ) (3.1.3)@?_(j=1)^n-?a_ij x_j ??b_i при (i=m_2+1..m) (3.1.4) )+


x_ji?0 (j=1,n_1 ) (3.1.5)
x_j-произвольные ( j= n_1+1…n) (3.1.6)
Где c_j,a_ij,b_i - заданные действительные числа; (3.1.1) – целевая функция; (3.1.1) – (3.1.6) –ограничения; ?x =(x_1… x_n) - план задачи.
Пусть ЗЛП представлена в следующей записи:
max??Z=cx (3.1.7)?
A_1 x_1+ A_2 x_2+?+A_n x_n= A_0 (3.1.8)
x_1?0 ,x_2?0 ,… ,x_n?0 (3.1.9)
Чтобы задача (3.1.7) – (3.1.8) имела решение, система её ограничений (3.1.8) должна быть совместной. При r=n (ранг матрицы равен числу неизвестных) система имеет единственное решение, которое будет при x_j?0 ( j=1,n) оптимальным. В этом случае проблема выбора оптимального решения теряет смысл.
Выясним структуру координат угловой точки многогранных решений. Пусть r Если свободные переменные приравнять нулю, а базисные переменные при этом примут неотрицательные значения, то полученное частное решение системы (3.1.8) называют опорным решением (планом).
3.2 Основные понятия целочисленного программирования
По смыслу значительной части экономических задач, относящихся к задачам линейного программирования, компоненты решения должны выражаться в целых числах, т.е. быть целочисленными. К ним относятся, например, задачи, в которых переменные означают количество единиц неделимой продукции, число станков при загрузке оборудования, число судов при распределениях по линиям, число турбин в энергосистеме, число вычислительных машин в управляющем комплексе и многие другие.
Задача линейного целочисленного программирования формируется следующим образом: найти такое решение (план) X = (x1,x2,...,xn), при котором линейная функция
(3.2.1)
принимает максимальное или минимальное значение при ограничениях
=bi, i=1, 2…, m. (3.2.2)
хj ? 0, j=1, 2,..., п. (3.2.3)
xj - целые числа (3.2.4)
?
3.3 Метод Гомори (метод отсекающих плоскостей)
В основе метода Гомори заложена идея, состоящая в том, что сначала решается задача линейного программирования без учета условий целочисленности. Если полученное таким образом решение целочисленное, то оно принимается за оптимальный план задачи. Если решение нецелочисленное, то система ограничений дополняется условием, которое отсекает от множества планов задачи нецелочисленный оптимальный план, но при этом сохраняет целочисленные вершины множества планов. Затем решается задача линейного программирования с дополнительным условием. Если полученное таким образом решение целочисленное, то оно оптимально и для задачи. Если же и после этого не для всех переменных выполняется условие целочисленности, то вводится новое условие-отсечение. Условия - отсечения выбираются таким образом, чтобы за конечное число шагов прийти к целочисленному решению, если оно у данной задачи существует.
Описание алгоритма.
Приведем обобщенную схему алгоритма Гомори. Структурно он делится на так называемые большие итерации. Каждая большая итерация содержит этапы:
1. Сначала задача решается методами линейного программирования (малые итерации), обычно симплекс-методом, и анализируется результат, если результатом являются целые числа, то на этом решение заканчивается, а если дробные, то производят следующие операции:
2. В оптимальном плане (симплекс-таблице) выбирают строку, для которой выполняется одно из ограничений:
a)?_i=maxT(k?I)???_k ? б)?_i/(?_(j?S)-?_ij )=maxT(k?I)???_k/(?_(j?S)-?_kj )?, где S – мнржество индексов свободных переменных;
{-(?_ij=frac(a_ij ), j?S, 0??_ij<1@?_i=frac(b_i ), ?03. Построение для найденной компоненты условия отсечения. Исходя из уравнения по данной строке xk=bk – ak,1*x1 - … - ak,n*xn в систему ограничений добавляем неравенство, в котором коэффициенты будут дробными частями коэффициентов данного уравнения: {bk}–{ ak,1}*x1 -… -{ ak,n}*xn ?0. Переводим к каноническому виду, добавляя новую переменную xn+1, получим: {bk}–{ ak,1}*x1 -… -{ar,n}*xn+xn+1 =0 и соответственно добавляем в симплекс-таблицу новый базисный вектор по новой переменной xn+1.
4. Переход на начало следующей большой итерации.
3.4 Постановка задачи
Дана линейная функция:
которая принимает максимальное или минимальное значение при ограничениях

=bi, i=1, 2…, m. , где
хj ? 0, j=1, 2,..., п. и xj - целые числа.

Этап 1:
Найти оптимальное решение задачи линейного программирования с ослабленными ограничениями, соответствующей исходной полностью целочисленной задаче.
?_(k=1)^n-?c_k y_k>max?
?_(k=1)^n-?a_ik y_k= b_i , i=1,m?
y_k?0 , k=1,n ,y_k?N?{0} , k=1,n
Этап 2:
Прекратить вычисления, если оптимальное решение задачи ЛП с ослабленными ограничениями удовлетворяют требованию целочисленности. В противном случае, выбрать базисное переменное yi, которому в оптимальном решении соответствует нецелое значение (условия выбора описаны выше).
Из оптимальной симплекс-таблицы выписать уравнение
y_i+?_(j?S)-?a_ij y_j=b_i ?

Содержащее это базисное переменное, и получить ограничение
?_(j?S)-??_ij y_j??_i ?
Этап 3:
В задачу линейного программирования с ослабленными ограничениями ввести ограничение

?_(j?S)-??_ij y_j??_i ?
Переходя к стандартной форме записи
?_(j?S)-??_ij y_j-y_(n+1)+y_(n+2)=?_i ?
Где yn+1 – новое неотрицательное переменное, yn+2 – искусственное неотрицательное переменное.
Найти оптимальное решение вновь полученной задачи линейного программирования с ослабленными ограничениями и перейти к этапу 2.
?
3.5 Пример решения
Рассмотрим следующую полностью целочисленную задачу:
{-(7x_1+9x_2>max;@-x_1+3x_2?6, x_1+1/7 x_2?5,@x_1,x_2?0, x_1,x_2?N?{0} )+
которая может быть представлена в стандартной форме
{-(7x_1+9x_2>max;@-y_1+3y_2+y_3=6, ?7y?_1+y_2+y_4=35,@y_k?0,k=1..4,y_k?N?{0},k=1..4)+
Где y1=x1, y2=x2, а y3 и y4 – новые переменные задачи. В таблице представлено решение задачи линейного программирования с ослабленными ограничениями, соответствующей рассматриваемой полностью целочисленной задаче.
Итерация Базисные переменные Значение y1 y2 y3 y4
0 y3
y4 6
35 -1
7 3
1 1
0 0
1
? 0 -7 -9 0 0
1 y2
y4 2
33 -1/3
22/3 1
0 1/3
-1/3 0
1
? 18 -10 0 3 0
2 y1
y2 9/2
7/2 1
0 0
1 -1/22
7/22 3/22
1/22
? 63 0 0 28/11 15/11
Её оптимальное решение Y^*=(9/2 7/2 0 0)^Tне удовлетворяет требованию целочисленности. Выбираем y2=7/2 и выписываем соответствующее уравнение из оптимальной симплекс-таблицы:
y_2+7/22 y_3+1/22 y_4=7/2. А так как в этом случае ?2=1/2, ?23=7/22, ?24=1/22, то новое ограничение имеет вид:
7/22 y_3+1/22 y_4?1/2 .
При переходе к стандартной форме записи этого ограничения:
7/22 y_3+1/22 y_4-y_5+y_6=1/2.
(вводим новое переменное модели y5 и искусственное переменное y6).
Продолжим решение задачи линейного программирования с ослабленными ограничениями, в которой учтено новое ограничение.
Итерация Базисные переменные Значение y1 y2 y3 y4 y5
3 y1
y2
y6 9/2
7/2
1/2 1
0
0 0
1
0 -1/22
7/22
7/22 3/22
1/22
1/22 0
0
-1
? 63 0 0 28/11 15/11 0
4 y1
y2
y3 32/7
3
11/7 1
0
0 0
1
0 0
0
1 1/7
0
1/7 -1/7
1
-22/7
? 59 0 0 0 1 8
Вновь полученное оптимальное решение не удовлетворяет требованию целочисленности. Выбираем y1=32/7 и выписываем соответствующее уравнение из оптимальной симплекс-таблицы:
y_1+1/7 y_4-1/7 y_5=32/7. А так как в этом случае ?1=4/7, ?14=1/7, ?15=6/7, то новое ограничение имеет вид: 1/7 y_4+6/7 y_5?4/7.
Вводим новое переменное модели y7 и искусственное переменное y8.
Для продолжения решения задачи линейного программирования с ослабленными ограничениями, в которой учтено новое ограничение, воспользуемся же известным приёмом с учётом того, что y8 – искусственное переменное.
Итерация Базисные переменные Значение y1 y2 y3 y4 y5 y7
5 y1
y2
y3
y8 32/7
3
11/7
4/7 1
0
0
0 0
1
0
0 0
0
1
0 1/7
0
1/7
1/7 -1/7
1
-22/7
6/7 0
0
0
-1
? 59 0 0 0 1 8 0
6 y1
y2
y3
y5 14/3
7/3
11/3
2/3 1
0
0
0 0
1
0
0 0
0
1
0 1/6
-1/6
2/3
1/6 0
0
0
1 -1/6
7/6
-11/3
-7/6
? 161/3 0 0 0 -1/3 0 28/3
7 y1
y2
y3
y4 4
3
1
4 1
0
0
0 0
1
0
0 0
0
1
0 0
0
0
1 -1
1
-4
6 1
0
1
-7
? 55 0 0 0 0 2 7
Полученное оптимальное решение определяет оптимальное решение X^0=(4 3)^T исходной полностью целочисленной задачи.


4. Проектирование программного средства и программная реализация


4.1 Разработка модульной структуры


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


4.2 Описание структур, типов данных и глобальных переменных
Переменные:
n - число строк в матрице ограничений
m - число столбцов в матрице ограничений
A - матрица ограничений
n1 – количество базисных переменных
it – первоначальное количество базисных переменных
flagn – флаг несовместности
sol – массив структур rec
Структуры:
rec – структура базисов:
rec.line – строка
rec.x – столбец
rec.number - значение
?
4.3 Описание процедур и функций

При разработке программы была выявлена необходимость в следующих функциях и процедурах:
Gomory – процедура расчета по методу Гомори
Simplex - симплекс-метод
Poisk_resh – поиск оптимального решения
Poisk_elem_st – поиск разрешающей строчки
El_preobr – преобразования матрицы
Proverki – проверка системы на несовместность


?
4.4 Разработка алгоритма программы


Рис.2. Процедура Sm_strok


Рис.3. Процедура El_preobr

Рис.4. Процедура Poisk_elem_st


Рис.5. Процедура Proverki

Рис.6. Процедура Poisk_resh

Рис.7. Процедура Simplex

Рис.8. Процедура Gomory

Рис.9. Процедура Delenie


Рис.10. Основной алгоритм
Заключение

В главах 1-2 приведен анализ требований, предъявляемых к данной программе.
В главе 3 приведены краткие теоретические сведения о применяемом методе и пример решения задачи.
В главе 4 приведена модульная структура программного средства, алгоритм программы и описание структур, типов данных, глобальных переменных и процедур.
Приложение 1 представляет собой руководство пользователя с иллюстрациями режимов работы программы.
Приложение 2 содержит исходный код программы, написанной на языке Delphi.
В ходе работы исследован метод целочисленного программирования, не изучаемый нами в рамках лабораторного проектирования, - метод отсекающих плоскостей, и его основе было спроектировано приложение.

?
Список литературы
Г.Вагнер. Основы исследования операций: Том 2-М.: Мир, 1973г.-488с.
Таха, Хэмди А. Введение в исследование операций. 6-е издание.: Пер. с англ. – М.: Издательский дом «Вильямс», 2001 г. -912с.
И.К Волков, Е.А. Загоруйко. Исследование операций: Учебник для вузов - М.: Изд-во МГТУ им. Н.Э. Баумана, 2000г. – 436с.

?
Приложение 1. Руководство пользователя
Запуск приложение осуществляется запуском программы Гомори.exe.
Пользователю будет доступно следующее окно:

Рис.11. Интерфейс пользователя

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


Приложение 2. Исходный код программы

unit Unit1;
interface
uses
Windows, Messages, SysUtils, Variants, Classes, Graphics, Controls, Forms,
Dialogs, StdCtrls, Grids, Spin;
type
TForm1 = class(TForm)
Label1: TLabel;
Stolb: TSpinEdit;
Label2: TLabel;
CelFunc: TStringGrid;...




Перейти к полному тексту работы


Скачать работу с онлайн повышением уникальности до 90% по antiplagiat.ru, etxt.ru или advego.ru


Смотреть похожие работы


* Примечание. Уникальность работы указана на дату публикации, текущее значение может отличаться от указанного.