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

 

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

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

                   (1.2)

 

Метод отсекающих плоскостей

 

Метод отсекающих плоскостей разработан Р. Гомори в 1957-1958 годах. Алгоритм метода включает этапы:

Этап 1. Ослабленная задача. Целочисленность искомых переменных игнорируется, симплекс-методом определяется оптимальный план.

Этап 2. Расширенная задача. Если план нецелочисленный, составляется дополнительное ограничение, “отсекающее” дробную часть искомой переменной. Дополнительное ограничение включается в систему ограничений и решается расширенная задача [3].

 

 

Метод ветвей и границ

 

Метод ветвей и границ применяется для решения полностью или частично целочисленных задач. Предложен А Лэндом и Дж. Дойгом в 1960 г.

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

при ограничениях                                                        (1.3)

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

 

.                                       (1.4)

 

В начале  итерации метода ветвей и границ необходимо иметь:

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

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

Пусть в результате  итераций метода получили список из  задач:  и существует . Алгоритм метода ветвей и границ содержит этапы:

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

2 Этап. Если задача  имеет решение , то переходим к этапу 3. Иначе – исключаем задачу  из списка, = . Переход к этапу 1. При  делаем вывод, что исходная задача не имеет решения и процесс решения заканчивается.

3 Этап. Если , то переходим к этапу 4. В противном случае задача  исключается из списка. Переход к этапу 1.

4 Этап. Если все компоненты вектора  удовлетворяют условию целочисленности, то переходим к этапу 5. В противном случае задача  из списка исключается. План  запоминается, . Переход к этапу 1. При  вектор  является решением исходной задачи и процесс решения заканчивается.

5 Этап Задача  из списка исключается. В список включаются две новые задачи линейного программирования – задача  и задача , = . Переход к этапу 1. Процесс разбиения задачи  на две новые задачи линейного программирования осуществляется следующим образом. Пусть  - дробная компонента в полученном оптимальном плане  и  целая часть. Тогда задача  имеет вид:

при ограничениях

                                              (1.5)

Тогда задача  имеет вид:

при ограничениях

                                              (1.6)

Процесс решения продолжается пока не будут решены все задачи линейного программирования из списка. Решение задачи будет  на последней итерации [4].

 

Практическая работа №1

«Метод отсечения в моделировании систем»

 

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

Используемые приемы и технологии: линейное программирование, целочисленное программирование.

Ключевые термины: математическая модель, симплекс-метод, метод отсекающих плоскостей, метод ветвей и границ.

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

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

 

Варианты заданий

 

Разработайте программу на языке С++, формализующую алгоритм решения оптимизационной задачи симплекс-методом

 

Вариант 1                     Вариант 2                   Вариант 3

           

при ограничениях         при ограничениях          при ограничениях

                           

Вариант 4                     Вариант 5                   Вариант 6

         

при ограничениях         при ограничениях          при ограничениях

                           

Вариант 7                     Вариант 8                   Вариант 9

     

при ограничениях         при ограничениях          при ограничениях

                               

Вариант 10                   Вариант 11                     Вариант 12

     

при ограничениях         при ограничениях          при ограничениях

                            

 

Методические указания

 

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

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

3 Разработать алгоритм решения задачи.

4 Разработать программу выбора оптимального проекта информационной системы.

5 Оформить отчет по практической работе.

Содержание отчета должно включать:

Титульный лист

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

2 Описание алгоритма решения задачи

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

4 Диаграмма классов.

5 Оптимальное решение математической модели информационной системы.

 

1.3. 3 Контрольные вопросы

 

1 Что называется математической моделью?

2 Что называется оптимальным решением?

3 Что называется допустимым решением?

4 Какие этапы метода Гаусса-Жордана?

5 Какой алгоритм метода обыкновенное Жорданово исключение?

6 Какой алгоритм метода модифицированное Жорданово исключение?

7 Какие этапы алгоритма метода отсекающих плоскостей?

8 Какие этапы  алгоритма метода ветвей и границ?

9 Как формулируется условие оптимальности?

10 Как формулируется условие допустимости?