Целочисленное программирование - umotnas.ru o_O
Главная
Поиск по ключевым словам:
страница 1
Похожие работы
Целочисленное программирование - страница №1/1

Целочисленное программирование

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





(9)



  целые.

Система (9) с точки зрения зависимостей ничем не отличается от задачи линейного программирования. Единственное отличие заключается в том, что в ней есть строка   целые, которая оказывает существенное влияние на решение задачи и значительно его усложняет. Число целочисленных переменных k может удовлетворять одному из двух вариантов. Если k = n, где n – общее число всех переменных, то в ответе все переменные должны быть только целыми. В таком случае задачу называют полностью целочисленной. Если k < n, в ответе только k переменных должны быть целыми, а остальные в заданных граничных условиях могут принимать любые значения. То есть в ответе должны быть целые, но не все. В этом случае задачу называют частично целочисленной. Для решения задачи все целочисленные переменные должны иметь верхнюю границу.

Рассмотрим решение целочисленной задачи на следующем примере:
F = x1 + x2 → max;

11x1 + 4,5x2 ≤ 49,5; (10)

5x1 +19x2 ≤ 95;

x1,2 ≥ 0 – целые.


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

Таблица 12 – Решение непрерывной задачи




F

x1

x2

7,03

2,75

4,28



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

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

Из рисунка 2 видно, что оптимальным решением задачи без учета требований целочисленности являются координаты точки А, приведенные в таблице 12, но они требованиям целочисленности не удовлетворяют.

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

Предположение, что решение недопустимое, потому что округление одной из координат было произведено в большую сторону, не совсем верно, так как в точке С координата х1 также округлена в большую сторону, а решение допустимое. Рассмотрим точки, ближайшие к оптимальной точке непрерывной задачи, удовлетворяющие условиям целочисленности. Кроме точки С (3, 3) это будет еще точка D (2, 4). Координаты всех рассмотренных точек и значения целевой функции в них приведены в таблице 13.
Таблица 13


Точка (рис.2)

х1

х2

F

Решение

A

2,75

4,28

7,03

Непрерывное

B

3

4

7

Недопустимое

C

3

3

6

Допустимое

D

2

4

6

Допустимое

Как видно из таблицы, в точках С и D значение целевой функции одинаково, несмотря на то, что они по-разному удалены от оптимальной точки А непрерывной задачи. Точка D расположена существенно дальше от точки А, чем точка С.

На основании всего вышесказанного можно сделать следующие выводы:


  1. Округление оптимальных значений переменных в непрерывном решении даже в меньшую сторону может привести к недопустимому решению;

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

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

Метод ветвей и границ. Рассмотрим этот метод на следующем примере:

F = 7x1 + 3x2 → max;

5x1 + 2x2 ≤ 20; (11)

8x1 + 4x2 ≤ 38;

x1,2 ≥0;

x1,2 – целые.


Назовем эту задачу задачей 1 и решим ее как непрерывную. Оптимальное решение задачи 1: В полученном решении x2 = 7,5 не удовлетворяет требованиям целочисленности. Поэтому для дальнейшего решения составим две задачи с граничными условиями, исключающими возможность получения x2 = 7,5:

Задача 2


F = 7x1 + 3x2 → max;

5x1 + 2x2 ≤ 20; (12)

8x1 + 4x2 ≤ 38;

x1 ≥0;

0 ≤ x2 ≤ 7.

Задача 3


F = 7x1 + 3x2 → max;

5x1 + 2x2 ≤ 20; (12)

8x1 + 4x2 ≤ 38;

x1 ≥0;

x2 ≥ 8.

В результате решения непрерывных задач 2 и 3 были получены следующие значения: Далее необходимо ввести требования на граничные условия, исключающие возможность получения значений



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

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