Целочисленные задачи линейного программирования

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

Курсовая работа

Целочисленные задачи линейного программирования



Оглавление

линейный программирование целочисленный задача

Введение

1. Целочисленные задачи линейного программирования. Метод Гомори

Заключение

Список литературы



Введение

Настоящая курсовая работа выполнена на тему: «Целочисленные задачи линейного программирования» и посвящена одной из важных проблем применения математических методов.

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

Составными частями математического программирования являются линейное, нелинейное и динамическое программирование. Впервые постановка задачи линейного программирования в виде предложения по составлению оптимального плана перевозок, позволяющего минимизировать суммарный километраж, дана в работе советского экономиста А.Н.Толстого (1930 г.).

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



1. Целочисленные задачи линейного программирования. Метод Гомори

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

Целочисленные задачи линейного программирования. Метод Гомори

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

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

Пример 1.

В цехе предприятия решено установить дополнительное оборудование, для размещения которого выделено площади. На приобретение оборудования предприятие может израсходовать 10 тыс. руб., при этом оно может купить оборудование двух видов. Комплект оборудования I вида стоит 1000 руб., а II вида - 3000 руб. Приобретение одного комплекта оборудования I вида позволяет увеличить выпуск продукции в смену на 2 ед., а одного комплекта оборудования II вида - на 4 ед. Зная что для установки одного комплекта оборудования I вида требуется 2 м2 площади, а оборудования II вида - 1 м2 площади определить такой набор дополнительного оборудования, которых дает возможность максимально увеличить выпуск продукции

Таким образом, приходим к следующей математической задаче: найти максимальное значение линейной функции (2) при выполнении условий (1), (3) и (4). Так как неизвестные могут принимать только целые значения, то задача (1) - (4) является задачей целочисленного программирования. Поскольку число неизвестных задачи равно двум, решение данной задачи можно найти, используя ее геометрическую интерпретацию. Для этого, прежде всего, построим многоугольник решений задачи, состоящей в определении максимального значения линейной функции (2) при выполнении условий (1) и (3) (рис. 11). Координаты всех точек построенного многоугольника решений ОАЕВС удовлетворяют системе линейных неравенств (1) и условию неотрицательности переменных (3). Вместе с тем условию (4), т. е. условию целочисленности переменных, удовлетворяют координаты лишь 12 точек, отмеченных на рис. 11. Чтобы найти точку, координаты которой определяют решение исходной задачи, заменим многоугольник ОАВС многоугольником OKEMNF, содержащим все допустимые точки с целочисленными координатами и таким, что координаты каждой из вершин являются целыми числами. Значит, если найти точку максимума функции (2) на многоугольнике OKEMNF, то координаты этой точки и определят оптимальный план задачи.

Решение. Составим математическую модель задачи. Предположим, что предприятие приобретет x1 комплектов оборудования I вида и x2 комплектов оборудования II вида. Тогда переменные x1 и x2 должны удовлетворять следующим неравенствам:

(1)



Если предприятие приобретет указанное количество оборудования, то общее увеличение выпуска продукции составит

(2)

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

(3)

x1, x2- целые. (4)

Для этого построим вектор и прямую проходящую через многоугольник решений OKEMNF (число 12 взято произвольно).

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

В данном случае искомой является точка E(1;3), в которой целевая функция принимает максимальное значение . Следовательно, координаты точки Е определяют оптимальный план задачи (1) - (4). В соответствии с этим планом предприятию следует приобрести один комплект оборудования 1 вида и три комплекта оборудования II вида. Это обеспечит предприятию при имеющихся у него ограничениях на производственные площади и денежные средства максимальное увеличение выпуск продукции, равное 14 ед. в смену.

Пример 2.

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

Решение. Введем переменную xij, значение которой равно 1, если при выполнении i-й работы используется j-й механизм, и равно 0 в противном случае. Тогда условия использования каждого механизма только на одной работе выражаются равенствами

(5)

а условия выполнения работы только одним механизмом - равенствами

(6)

(7)

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

(8)

Сформулированная задача является задачей целочисленного программирования.

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

(9)

при условиях

(10)

(11)

- целые (12)

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

Метод Гомори. Нахождение решения задачи целочисленного программирования методом Гомори начинают с определения симплексным методом оптимального плана задачи (9) - (11) без учета целочисленности переменных. После того как этот план найден, просматривают его компоненты. Если среди компонент нет дробных чисел, то найденный план является оптимальным планом задачи целочисленного программирования (9) - (12). Если же в оптимальном плане задачи (9) - (11) переменная принимает дробное значение, то к системе уравнений (10) добавляют неравенство

(13)

и находят решение задачи (9) - (11), (13).

В неравенстве (13) и - преобразованные исходные величины и значения которых взяты из последней симплекс-таблицы, а и - дробные части чисел (под дробной частью некоторого числа а понимается наименьшее неотрицательное число b такое, что разность между а и b есть целое). Если в оптимальном плане задачи (9) - (11) дробные значения принимают несколько переменных, то дополнительное неравенство (13) определяется наибольшей дробной частью.

Если в найденном плане задачи (9) - (11), (13) переменные принимают дробные значения, то снова добавляют одно дополнительное ограничение и процесс вычислений повторяют. Проводя конечное число итераций, либо получают оптимальный план задачи целочисленного программирования (9) - (12), либо устанавливают ее неразрешимость.

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

(14)

где определяются из следующих соотношений:



1) для , которые могут принимать нецелочисленные значения,

(15)

2) для , которые могут принимать только целочисленные значения,

(16)

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

1. Используя симплексный метод, находят решение задачи (9) - (11) без учета требования целочисленности переменных.

2. Составляют дополнительное ограничение для переменной, которая в оптимальном плане задачи (9) - (11) имеет максимальное дробное значение, а в оптимальном плане задачи (9) - (12) должна быть целочисленной.

3. Используя двойственный симплекс-метод, находят решение задачи, получающейся из задачи (9) - (11) в результате присоединения дополнительного ограничения.

4. В случае необходимости составляют еще одно дополнительное ограничение и продолжают итерационный процесс до получения оптимального плана задачи (78) - (81) или установления ее неразрешимости.

Пример 3.

Методом Гомори найти максимальное значение функции

(17)



при условии

(18)

(19)

- целые (20)

Дать геометрическую интерпретацию решения задачи.

Решение. Для определения оптимального плана задачи (17) - (20) сначала находим оптимальный план задачи (17) - (19) (табл. 22).

Таблица 22

i	Базис	Сб	Р0	3	2	0	0	0
				P1	P2	P3	p4	p5
1 2 3 4 1 2 3 4 1 2 3 4	p3 P4 p5 p3 P1 p5 p2 P1 p5	0 0 0 0 3 0 2 3 0	13 6 9 0 7 6 27 18 7/2 19/2 34 71/2	1 1 -3 -3 0 1 0 0 0 1 0 0	1 -1 1 -2 2 -1 -2 -5 1 0 0 0	1 0 0 0 1 0 0 0 1/2 1/2 1 5/2	0 1 0 0 -1 1 3 3 -1/2 1/2 2 1/2	0 0 1 0 0 0 1 0 0 0 1 0

Как видно из табл. 22, найденный оптимальный план задачи (17) - (19) не является оптимальным планом задачи (17) - (20), поскольку две компоненты и имеют нецелочисленные значения. При этом дробные части этих чисел равны между собой. Поэтому для одной из этих переменных составляется дополнительное ограничение. Составим, например, такое ограничение для переменной . Из последней симплекс-таблицы (табл. 22) имеем

Таким образом, к системе ограничений задачи (17) - (20) добавляем неравенство

или

т.е.

(21)

Таблица 23

i	Базис	Сб	Р0	3	2	0	0	0	0
				P1	P2	P3	p4	p5	P6
1 2 3 4 5 1 2 3 4 5	p2 P1 p5 p6 p2 P1 p5 p4	2 3 0 0 2 3 0 0	7/2 19/2 34 -1 71/2 4 9 32 1 35	0 1 0 0 0 0 1 0 0 0	1 0 0 0 0 1 0 0 0 0	1/2 1/2 1 -1 5/2 1 0 -1 1 2	-1/2 1/2 2 -1 1/2 0 0 0 1 0	0 0 1 0 0 0 0 1 0 0	0 0 0 1 0 -1/2 1/2 2 -1 1/2

Находим теперь максимальное значение функции (17) при выполнении условий (18), (19) и (21) (табл. 23).

Из таблицы 23 видно, что исходная задача целочисленного программирования имеет оптимальный план При этом плане значение целевой функции равно . Дадим геометрическую интерпретацию решения задачи. Областью допустимых решений задачи (17) - (19) является многоугольник OABCD (рис. 12). Из рис. 12 видно, что максимальное значение целевая функция принимает в точке С (19/2; 7/2), т. e. что Х = (19/2; 7/2; 0; 0; 34) является оптимальным планом. Это непосредственно видно и из таблицы 22. Так как Х = (19/2; 7/2; 0; 0; 34) не является оптимальным планом задачи (17) - (20) (числа и - дробные), то вводится дополнительное ограничение . Исключая из него и подстановкой вместо них соответствующих значений из уравнений системы ограничений (18), получим отсекающий от многоугольника OABCD треугольник EFC.

Как видно областью допустимых решений полученной задачи является многоугольник OABEFD. В точке Е(9; 4) этого многоугольника целевая функция данной задачи принимает максимальное значение. Так как координаты точки Е - целые числа и неизвестные , и принимают целочисленные значения при подстановке в уравнение (18) значений и , то является оптимальным планом задачи (17) - (20). Это следует и из таблицы 23.

Пример 4.

Методом Гомори найти решение задачи, состоящей в определении максимального значения функции

(22)

при условиях



(23)

(24)

- целые. (25)

Дать геометрическую интерпретацию решения задачи.

Решение. Сформулированную задачу перепишем так: найти максимальное значение функции

(26)

при условиях

(27)

(28)

- целые. (29)

Задача (26) - (29) является частично целочисленной, так как переменные и могут принимать нецелочисленные значения.

Находим симплексным методом решение задачи (26) - (28) (таблица 24).

Таблица 24

i	Базис	Сб	Р0	1	4	0	0
				P1	P2	P3	p4
1 2 3 1 2 3	p3 P4 p3 P2	0 0 0 4	19/3 4 0 5 4/3 16/3	2 1 -1 5/3 1/3 1/3	1 3 -4 0 1 0	1 0 0 1 0 0	0 1 0 -1/3 1/3 4/3



Дадим геометрическую интерпретацию решения задачи. На рис. 13 показана область допустимых решений задачи (26) - (28). Из рисунка видно, что максимальное значение целевая функция принимает в точке , т.е. что является оптимальным планом задачи (26) - (28). В то же время не является планом задачи (26) - (29), так как переменная принимает дробное значение. Поэтому вводим дополнительное ограничение откуда, подставляя вместо его значение из второго уравнения системы уравнений (27), получаем . Этому неравенству на рис. 13 соответствует полуплоскость, ограниченная прямой , отсекающей от многоугольника ОАВС треугольник ADE. В области ODEBC находим точку Е(1; 1), в которой функция (26) принимает максимальное значение. Так как координаты точки Е - целые числа, то является оптимальным планом задачи (26) - (28). Это видно и из таблицы 25

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

(30)

Находим теперь решение задачи, состоящей в определении максимального значения функции (26) при условиях (27), (28) и (30). Данную задачу решаем двойственным симплекс-методом (таблица 25).

Таблица

i	Базис	Сб	Р0	1	4	0	0	0
				P1	P2	P3	p4	p5
1 2 3 4 1 2 3 4	p3 P2 p5 p3 P2 p1	0 4 0 0 4 1	5 4/3 -1 16/3 10/3 1 1 5	5/3 1/3 -1 1/3 0 0 1 0	1 1 0 0 0 1 0 0	1 0 0 0 1 0 0 0	-1/3 1/3 -1 4/3 -2 0 1 1	0 0 1 0 5/3 1/3 -1 1/3

Из таблицы видно, что является оптимальным планом построенной задачи. Так как при этом плане переменные и принимают целые значения, то он также является оптимальным планом исходной задачи (26) - (29).



Заключение

Настоящая курсовая работа выполнена на тему: «Целочисленные задачи линейного программирования» и посвящена одной из важных проблем применения математических методов.

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

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

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



Список литературы

1.Агальцов В.П., Волдайская И.В. Математические методы в программировании: Учебник. - М.: ИД «ФОРУМ»: ИНФРА-М, 2006. - 224 с.

2. Ашманов С.А. Линейное программирование. - М.: Физматгиз, 1981. - 340 с.

3. Боглаев Ю.П. Вычислительная математика и программирование: Учеб. пособие для студ. втузов. - М.: Высшая школа, 1990. - 544 с.

4. Вентцель Е.С. Исследование операций. Задачи, принципы, методология: Учеб. пособие для вузов. - М.: Дрофа, 2004. - 208 с.

5. Вентцель Е.С. Элементы теории игр. - М.: Физматгиз, 1959. - 67 с.

6. Гасс С. Линейное программирование (методы и приложения). - М.: Физматгиз, 1961. - 303 с.

7. Гермейер Ю.Б. и др. Задачи по исследованию операций. Учеб. пособ./ Гермейер Ю.Б., Морозов В.В.. Сухарев А.Г., Фёдоров В.В. - М.: Изд-во Моск. Ун-та, 1979. - 167 с.

8. Горстко А.Б. В поисках правильного решения. - М.: Изд-во «Знание», 1970.-77 с.

9. Гультяев А. MATLAB 5.2. Имитационное моделирование в среде Windows. - М.: Корона принт, 1999.

10. Калихман И.Л., Войтенко М.А. Динамическое программирование в примерах и задачах: Учеб. пособие. - М.: Высшая школа, 1979. - 125 с.

11. Капустин В.Ф. Практические занятия по курсу математического программирования. - Л.: Изд-во Ленингр. ун-та, 1976. - 192 с.

12. Красс М.С., Чупрынов Б.П. Основы математики и её приложения в экономическом образовании: учеб. - М.: Дело, 2001. - 688 с.

13. Кудрявцев Е.М. Mathcad 2000 Pro. - М.: ДМК Пресс, 2001. - 576 с.

14. Кузнецов Ю.Н. и др. Математическое программирование. Учеб. пособие для вузов/ Кузнецов Ю.Н.. Кузубов В.И.. Волощенко А.Б. - М.: Высшая школа, 1976. - 352 с.

15. Лежнёв А.В. Динамическое программирование в экономических задачах. - М.: БИНОМ. Лаборатория знаний, 2006. - 176 с.

16. Линейное и нелинейное программирование/ Ляшенко И.Н., Карагодова Е.А., Черникова Н.В., Шор Н.З. - Киев: «Вища школа», 1975. - 372 с.

17. Лефевр В.А., Смолян Г.Л. Алгебра конфликта. - М.: Изд-во «Знание», 1968. - 63 с.

18. Монахов В.М., Беляева Э.с., Краснер Н.Я. Методы оптимизации. Применение математических методов в экономике. Пособие для учителя. - М.: «Просвещение», 1978. - 175 с.

19. Мещеряков В.В. Задачи по математике с MATLAB®&SIMULINK®. - М.: ДИАЛОГ-МИФИ, 2007. - 528 с.

20. Минько А.А. Принятие решений с помощью Excel. Просто как дважды два. - М.: Эксмо, 2007. - 240 с.

21. Могилёв А. В., Пак Н. И., Хеннер Е. К. Информатика: Учеб. пособие для студ. - М.: Изд. Центр «Академия», 2000. - 816 с.

22. Мышкис А.Д. Элементы теории математических моделей. - М.: КомКнига, 2007. - 192 с.

23. Партыка Т.Л., Попов И.И. Математические методы: учебник. - М.: ФОРУМ: ИНФРА-М, 2007. - 464 с.

24. Плис А.И., Сливина Н.А. Лабораторный практикум по высшей математике: Учеб. пособие для втузов. - М.: Высшая школа, 1994. - 416 с.

25. Саульев В.К. Вероятностно-статистические методы теории исследования операций. - М.: Общество «Знание», 1973. - 53 с.

26. Советов Б. Я., Яковлев С. А. Моделирование систем: Учеб. для вузов. - М.: Высшая школа, 2001.

27. Тихонов А.Н., Костомаров Д.П. Вводные лекции по прикладной математике. - М.: Наука. Физматгиз, 1984. - 192 с.

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