Содержание:

Введение

1. Теоретический аспект целочисленного программирования……………. 4  

  1.1 Предпосылки появления целочисленного программирования………..4

  1.2 Основные понятия целочисленного программирования……………....4

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

2.Экономическая и геометрическая интерпретация задачи

     целочисленного программирования………………………………………8

  2.1. Пример и решение……………………………………………………….8

3.Определение оптимального плана задачи целочисленного программирования…………………………………………………………....11

4. Метод Гомори………………………………………………………………12

  4.1. Пример и решение………………………………………………………14

Заключение

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

Введение

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

1.Теоретический аспект целочисленного программирования

1.1 Предпосылки появления целочисленного программирования

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

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

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

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

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

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

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

                                                                                                                              (1)

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

                                                                                                  (2)

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

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

                                                                                                                (3)

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

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

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

- линейные;

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

              (4)

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

              (5)

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

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

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

2.Экономическая и геометрическая интерпретация задачи целочисленного программирования. 

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

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

Пример 1.

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

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

(1)

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

(2)

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

(3)

x1, – целые. (4)

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

  Для этого построим вектор и прямую проходящую через многоугольник решений 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)

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

3. Определение оптимального плана задачи целочисленного программирования. 

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

(9)

при условиях

(10)

(11)

– целые (12)

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

4. Метод Гомори. 

  Нахождение решения задачи целочисленного программирования методом Гомори начинают с определения симплексным методом оптимального плана задачи (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. В случае необходимости составляют еще одно дополнительное ограничение и продолжают итерационный процесс до получения оптимального плана задачи (9) – (12) или установления ее неразрешимости.

Пример 3.

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

(17)

при условии

(18)

(19)

– целые (20)

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

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

Таблица 22

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

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

или

т.е.

(21)

Таблица 23

  Находим теперь максимальное значение функции (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.

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

Пример 4.

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

(22)

при условиях

(23)

(24)

– целые. (25)

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

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

(26)

при условиях

(27)

(28)

– целые. (29)

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

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

Таблица 24

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

(30)

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

Таблица 25

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

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

Заключение

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

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

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

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

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

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

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

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

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

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

2