Модели целочисленного программирования

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

Павлодарский экономический колледж

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

Предмет: «Моделирование производственных и экономических процессов»

Тема: Модели целочисленного программирования

КП1304000.4-13П.33.2012ПЗ

Специальность: 1304000 «Вычислительная техника и программное обеспечение»

Исполнитель:

Шиканов Р.А.

Руководитель:

Сембаева Г.М.

СОДЕРЖАНИЕ

ВВЕДЕНИЕ

1. МОДЕЛИ ЦЕЛОЧИСЛЕННОГО ПРОГРАММИРОВАНИЯ

1.1 Описание моделей целочисленного программирования

1.2 Методы целочисленного программирования

1.3 Целочисленное программирование как метод оптимизации

2. ПОСТРОЕНИЕ МАТЕМАТИЧЕСКОЙ МОДЕЛИ

2.1 Постановка задачи

2.2 Математическая модель и решение задачи

3. ПРОЕКТИРОВАНИЕ ЗАДАЧИ

3.1 Требования к техническому и программному обеспечению

3.2 Структура компьютерной модели задачи

ЗАКЛЮЧЕНИЕ

СПИСОК ИСПОЛЬЗУЕМЫХ ИСТОЧНИКОВ

ВВЕДЕНИЕ

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

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

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

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

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

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

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

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

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

1. МОДЕЛИ ЦЕЛОЧИСЛЕННОГО ПРОГРАММИРОВАНИЯ

1.1 Описание моделей целочисленного программирования

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

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

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

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

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

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

1.2 Методы целочисленного программирования

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

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

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

Вначале задача целочисленного программирования рассматривается как линейная программа и алгоритм решает ее с помощью прямого или двойственного симплекс-метода.

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

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

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

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

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

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

Получена задача линейного целочисленного программирования. Она реализована эвристическим алгоритмом, основанным на принципе последовательной обработки предварительно упорядоченной информации. Исходными нормативными данными являются сведения справочников М8, М10 и МП. Из множества приборов, указанного пользователем, отбираются те, обслуживание которых в соответствии с план-графиком должно быть выполнено не позднее планируемого месяца. Эти данные объединяются во вспомогательный файл.

Типичный пример задачи целочисленного программирования: имеется ранец объема V и неограниченное количество каждого из N различных предметов.

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

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

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

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

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

Для точного решения задач целочисленного программирования с малым числом существенных ограничений (не более 2 - 3) часто оказываются полезными принципы динамического программирования.

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

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

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

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

1.3 Целочисленное программирование как метод оптимизации

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

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

(1)

Задача оптимизации в общем случае, включает три компоненты - целевую функцию F, ограничения gi и граничные условия, и имеет следующую математическую постановку:

(2)

где aj и bj --нижнее и верхнее предельно допустимые значения хj.

Задачу (2) можно представить в еще более общей компактной форме записи

(3)

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

Задачи оптимального программирования классифицируются:

1. по характеру изменения переменных:

- линейные;

- нелинейные.

2. по характеру изменения переменных:

- непрерывные;

- дискретные.

3. по учету фактора времени:

- статические;

- динамические.

4. по наличию информации о переменных:

- полная определенность;

- в условиях неполной информации;

- задачи в условиях неопределенности.

5. по числу критериев оценки альтернативы:

-однокритериальные;

- многокритериальные.

Частный раздел оптимального программирования являющийся в свою очередь разделом прикладной математики изучающий задачи условной оптимизации является - линейное программирование.

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

Целевая функция имеет вид:

(4)

Ограничения имеют вид

(5)

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

Наиболее распространенным методом решения линейного программирования является симплекс-метод.

математическая модель метод целочисленное программирование

2 РЕШЕНИЕ ЗАДАЧИ ДЛЯ НАХОЖДЕНИЯ ОПТИМАЛЬНОГО ПЛАНА ПРЕДПРИЯТИЯ

2.1 Постановка задачи

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

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

Тип ресурса	Нормы затрат ресурсов на единицу продукции	Наличие ресурсов
	1	2	3	4
Сырье	3	5	2	4	60
Рабочее время	22	14	18	30	400
Оборудование	10	14	8	16	128
Прибыль на единицу продукции	30	25	8	16

2.2 Разработка математической модели задачи

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

F(X) = 30x1 + 25x2 + 8x3 + 16x4

при следующих условиях-ограничений:

3x1 + 5x2 + 2x3 + 4x4<=60

22x1 + 14x2 + 18x3 + 30x4<=400

10x1 + 14x2 + 8x3 + 16x4<=128

Для построения первого опорного плана систему неравенств приведем к системе уравнений путем введения дополнительных переменных (переход к канонической форме).

3x1 + 5x2 + 2x3 + 4x4 + 1x5 + 0x6 + 0x7 = 60

22x1 + 14x2 + 18x3 + 30x4 + 0x5 + 1x6 + 0x7 = 400

10x1 + 14x2 + 8x3 + 16x4 + 0x5 + 0x6 + 1x7 = 128

Матрица коэффициентов A = a(ij) этой системы уравнений имеет вид:

3524100

22141830010

1014816001

Решим систему уравнений относительно базисных переменных: x5, x6, x7, полагая, что свободные переменные равны 0, получим первый опорный план (таблица 2): X1 = (0,0,0,0,60,400,128).

Таблица 2. Первый опорный план

Базис	B	x1	x2	x3	x4	x5	x6	x7
x5	60	3	5	2	4	1	0	0
x6	400	22	14	18	30	0	1	0
x7	128	10	14	8	16	0	0	1
F(X0)	0	-30	-25	-8	-16	0	0	0

Переходим к основному алгоритму симплекс-метода. Текущий опорный план неоптимален, так как в индексной строке находятся отрицательные коэффициенты. В качестве ведущего выберем столбец, соответствующий переменной x1, так как это наибольший коэффициент по модулю. Вычислим значения Di по строкам как частное от деления: bi / ai1 и из них выберем наименьшее. Следовательно, 3-ая строка является ведущей.

Разрешающий элемент равен (10) и находится на пересечении ведущего столбца и ведущей строки. (Таблица 3).

Таблица 3

Базис	В	Х1	Х2	Х3	Х4	Х5	Х6	Х7	Min
Х5	60	3	5	2	4	1	0	0	20
Х6	400	22	14	18	30	0	1	0	182/11
Х7	128	10	14	8	16	0	0	1
F(X1)	0	-30	-25	-8	-16	0	0	0	0

Получаем новую симплекс-таблицу(таблица 4):

Таблица 4

Базис	B	x1	x2	x3	x4	x5	x6	x7
x5	213/5	0	4/5	-2/5	-4/5	1	0	-3/10
x6	1182/5	0	-164/5	2/5	-51/5	0	1	-21/5
x1	124/5	1	12/5	4/5	13/5	0	0	1/10
F(X1)	384	0	17	16	32	0	0	3

Конец итераций: индексная строка не содержит отрицательных элементов - найден оптимальный план.

Окончательный вариант симплекс-таблицы(Таблица 5):

Таблица 5

Базис	B	x1	x2	x3	x4	x5	x6	x7
x5	213/5	0	4/5	-2/5	-4/5	1	0	-3/10
x6	1182/5	0	-164/5	2/5	-51/5	0	1	-21/5
x1	124/5	1	12/5	4/5	13/5	0	0	1/10
F(X2)	384	0	17	16	32	0	0	3

Оптимальный план можно записать так: x5 = 213/5, x6 = 1182/5, x1 = 124/5, F(X) = 30*124/5 = 384

3. ПРОЕКТИРОВАНИЕ ЗАДАЧ НА ПК

3.1 Требования к техническим и инструментальным средствам

Для работы задачи курсового проекта необходима ЭВМ, отвечающая следующими аппаратно - техническим и программным требованиям:

операционная система Windows XP и выше;

Процессор Pentium 2 и выше;

256Мб оперативной памяти;

40 Гб жесткого диска;

Монитор;

Клавиатура.

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

Для разработки задачи необходимо следующее программное обеспечение:

операционная система Windows XP;

ППП Microsoft Office.

Задача разрабатывается в операционной среде Windows, имеет только локальное назначение. Документация для задачи разрабатывается в операционной среде Windows с использованием пакета прикладных программ Microsoft Office.

3.2 Структура компьютерной модели задачи

Пусть значение х1, х2, х3, х4 хранятся в ячейки А2:А3:А4:А5, а значение целевой функции F - в ячейке С2. Введем ограничения системы неравенств в ячейки:

С3=3*А2+5*А3+2*А4+4*А5;

С4=22*А2+14*А3+18*А4+30*А5;

С5=10*А2+14*А3+8*А4+16*А5.

C2=30*А2+25*А3+8*А4+16*А5.

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

В поле установить целевую ячейку отражатеся адрес целевой ячейки. В поле равной по умолчанию будет стоять галочка против поля максимальному значению. В поле Изменяя ячейки адрес изменяемых ячеек А2:А3: А4: А5. В поле ограничения ввести адреса ограничений и значения неотрицательности значений х1, х2, х3, х4, х5. После внесения адресов ячеек, активизирывали кнопку Выполнить. Появится следующие диалоговое окно и решение задачи. В диалоговом окне Результаты поиска решения щелкните по кнопке ОК.

12,8		384
0		38,4
0		281,6
0		128

Из решения видно, что х1=12,8, х2=0, х3=0, х4= 0 и целевая функция равна F(x)=384, это означает, что для получения максимальной прибыли необходимо 12,8 изделий вида А и 6 видов В. Тогда прибыль составит 384 у.е.

Процесс формализации задачи называется построением ее математической модели. Он состоит из трех этапов:

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

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

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

Заключение

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

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

MS Excel стал стандартом в сфере научно-исследовательских работ, и является одними из самых распространенных программным продуктом, используемым во всем мире, где без специальных навыков программирования можно решать достаточно сложные задачи, в том числе и задачи оптимизации. Кроме MS Excel в процессе выполнения курсовой работы были использованы и другие программы пакета MS Office. В частности, для оформления курсовой работы был использован текстовый редактор этого пакета - MS Word.

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

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

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

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

СПИСОК ИСПОЛЬЗУЕМЫХ ИСТОЧНИКОВ

Абрамов В.Г., Трифонов Н.П., Трифонова Г.Н. Введение в язык Паскаль. - М.: Наука, 1988;

Абрамов С.А., Зима Е.В. Начала программирования на языке Паскаль. - М.: Наука, 1987;

Ашманов С.А. Линейное программирование. М.: Наука, 2001.

Белолипецкий В. М. Математическое моделирование в задачах. / В.М. Белолипецкий, Ю.И. Шокин. - М.: Финансы и статистика, 2002.- 774 с.

Вирт Н. Алгоритмы и структуры данных./Пер. с англ. М.: Мир, 1989;

Калихман И.Л. Линейная алгебра и программирование. - М.: Высшая школа, 1987

Красс М.С. Основы математики и ее приложения в экономическом образовании.

Лонгу К.К. Линейное программирование. Руководство к решению задач. - М.: ФИЗМАТЛИТ, 2005.

Солодовников А.С. Математика в экономике. / А.С. Солодовников, В.А. Бабайцев, А.В. Браилов. - М.: Изд.- во МГУ, 1999. - 591 с.

Черемных Ю.Н. Математические методы в экономике. 2 - изд. / Ю.Н. Черемных. - М.: Дело и сервис, 2001. - 657 с.

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