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

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

1. Целочисленное программирование. Постановка задачи, графический метод решения, пример.

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

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

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

Найти такое решение план Х=(х1, х2,…, хn), при котором линейная функция принимает максимальное или минимальное значение при ограничениях

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

1.2 Понятия о методе ветвей и границ

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

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

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

1.3 Графический метод решения задач целочисленного программирования

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

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

Если оптимальное решение этой задачи является целочисленным, то оно и является оптимальным для исходной задачи.

Если же полученное оптимальное решение не целочисленное, то строится дополнительное линейное ограничение. Оно обладает следующими свойствами:

1) Оно должно быть линейным;

2) Должно отсекать найденный оптимальный не целочисленный план;

3) Не должно отсекать ни одного целочисленного плана.

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

1. Построить систему координат x10х2 и выбрать масштаб.

2. Найти область допустимых решений (ОДР) системы ограничений задачи.

3. Построить целевую функцию, являющуюся линией уровня и на ней указать направление нормали.

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

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

5. Найти координаты, точки экстремума и значение целевой функции в ней. Если полученные значения не целочисленные, то перейти к следующему шагу.

6. Выделить у этих координат область с целочисленными значениями.

7. Определить новые координаты и построить граф.

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

1.4 Пример решения задачи целочисленного программирования

Условие задачи.

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

Решение:

1. Находим координаты точек каждого линейного уравнения системы ограничений и строим прямые

1 прямая: 3х1+2х2=1

если х1=1, то 2х2=12, х2=6

если х2= 0, то 3х1=12, х1=4

2 прямая: 2х1+5х2=20

если х1=0, то 5х2=20, х2=4;

если х2=0, то 2х1=20, х1=10

2. Находим ОДР.

Так как х1, х2 ? 0, то область будет ограничен прямыми ОХ1 и ОХ2 и построенными прямыми (см. рис.1).

3. Находим координаты точек целевой функции и строим прямую целевой функции:

7х1+4х2=0

- первая точка х1=0; х2=0

- вторая точка х1=4, х2=(-7).

4. Перемещаем прямую целевой функции по направлению через ОДР до тех пор, пока она не станет касательной к ней, и находим точку А0.

5. Находим координаты точек А0 и значение целевой функции в ней:

Х1=1,8; х2=3,27;

Z=71,8+43,27=12,6+13,08=25,68

Получен не целочисленный оптимальный план

6. выделим область относительно точки А0 беря целые значения 1 ? х1 ? 2; 3 ? х2 ? 4.

Получим координаты точек по границе этой области:

А1 (1;3,6) А2 (2;3); А3 (0;4); А4 (1;3); А5 (0;3); А6 (1;0); А7 (2;0).

7. Строим граф (рис.2)

8. Для точек с целыми значениями их координат (искомые значения х1 и х2)находим значения целевой функции:

Для точки А2 (2;3) Z2= 72+43=26

Для точки А3 (0;4) Z3= 70+44=16

Для точки А4 (1;3) Z4= 71+43=19

Для точки А5 (0;3) Z5= 70+43=12

Для точки А6 (1;0) Z6= 71+40=7

Для точки А7 (2;0) Z7= 72+40=14

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

Ответ: Z=26; х1=2; х2=3.

1.5 Задача коммивояжера

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

Задана матрица расстояний между городами cij.

Сформулированная задача - задача целочисленная. Пусть хij = 1 , если путешественник переезжает из i -ого города в j-ый и хij = 0, если это не так.

Формально введем (n+1) город, расположенный там же, где и первый город, т.е. расстояния от (n+1) города до любого другого, отличного от первого, равны расстояниям от первого города. При этом, если из первого города можно лишь выйти, то в (n+1) город можно лишь придти.

Введем дополнительные целые переменные, равные номеру посещения этого города на пути. u1 = 0, un+1 = n . Для того, чтобы избежать замкнутых путей, выйти из первого города и вернуться в (n+1) введем дополнительные ограничения, связывающие переменные xij и переменные ui. ( ui целые неотрицательные числа).

1.6 Математическая модель

Пример решения задачи.

Условия задачи:

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

Матрица расстояний cij между городами задана таблицей:

Номер города	1	2	3	4
1		19	25	11
2	37		26	58
3	10	50		39
4	38	39	24

Решение задачи.

Составляем математическую модель задачи.

Zmin=19х12+25х13+11х13+37х21+26х23+58х24+10х31+50х32+39х34+38х41+39х42+24х43

х12+х13+х14=1 х21+х31+х41=1

х21+х23+х24=1 х12+х32+х42=1

х41+х42+х34=1 х13+х23+х43=1

х21+х23+х24=1 х14+х42+х34=1

U1 - U2 + 4х12 < 3

U1 -U3 + 4х13 < 3

U1 - U4+ 4х14 < 3

U2 - U3 + 4х23 < 3

U2 -U4 + 4х24 < 3

U3 - U2+ 4х32 < 3

U3 - U4 + 4х34 < 3

U4 - U2 + 4х42 < 3

U4 -U3 + 4х43 < 3

U4 - U1+ 4х41 < 3

U3 - U1 + 4х31 < 3

U2 -U1 + 4х21 < 3

0,

Хij= - ЦЕЛЫЕ ,

1

где:

Zmin - минимальный маршрут посещения городов;

cij - расстояние между городами ij ;

Ui - номер посещения i - го города.

Строим граф посещения городов с учетом возможных маршрутов движения коммивояжера.

Граф посещения городов:

где:

--- расстояние между городами;

--- расстояние, пройденное по маршруту;

--- расстояние, пройденное по минимальному маршруту.

Номер города: 4.

Ответ:

Минимальный маршрут: 1 --- 4 --- 2 --- 3 --- 1 .

Минимальное расстояние - 86 ед.

2. Метод идеальной точки. Пример использования данного метода к решению конкретной экономической задачи

В многокритериальной задаче оптимизации сравнение решений по предпочтительности осуществляется не непосредственно, а при помощи заданных на множестве решений Хчисловых функций f1, f2,…fm, называемых критериями (а также показателями качества или эффективности, критериальными функциями, целевыми функциями и т.п.). Предполагается, что m? 2: при m=1 задача оптимизации является однокритериальной.

Математическая модель многокритериальной задачи принятия решений представляется в виде <X, f1,f2,…,fm>, где X - множество допустимых исходов, fj - числовая функция, заданная на множестве X; при этом fj(б) есть оценка исхода б?X по j-му критерию (j=1,m).

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

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

Пусть Yj - множество значений функции fi, т.е. множество всех оценок по j-му критерию (j=1,n). Тогда множество , состоящее из всевозможных упорядоченных наборов оценок по критериям 1,2,…, m, называется множеством векторных оценок. Любой элемент у?Y представляет собой вектор y=(y1,y2,…,Ym), где y?Yj. Для всякого исхода б?Х набор его оценок по всем критериям, т.е. набор (f1(б), f2(б),…, fm(б)) есть векторная оценка исхода б. Векторная оценка содержит полную информацию о ценности (полезности) этого исхода для принимающего решение и сравнение любых двух исходов заменяется сравнением их векторных оценок.

Основное отношение, по которому производится сравнение векторных оценок (значит, и сравнение исходов), ? это отношение доминирования по Парето, которое определяется следующим образом.

Говорят, что векторная оценка y=(y1,y2,…,ym) доминирует по Парето векторную оценку y`=(y`1,y`2,…,y`m), (записывается в виде yy'), если для всех j=1,n выполняется неравенство уj ? у`j, причем по крайней мере для одного индекса j=1,n неравенство должно быть строгим.

Пусть Q ? Y ? некоторое множество векторных оценок.

Векторная оценка y*?Q называется Парето-оптимальной в Q, если она является максимальным элементом множества Q относительно Парето-доминирования (т.е. если в множестве Q не существует такой векторной оценки y, которая доминирует по Парето векторную оценку y*).

Перенесем теперь эти понятия на исходы.

Говорят, что исход б1 доминирует по Парето исход б2 (записывается в виде a1a2), если векторная оценка исхода б1 доминирует по Парето векторную оценку исхода б2.

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

Исход a*?X называется Парето-оптимальным исходом в множестве Х, если он не доминируется по Парето никаким другим исходом из множества Х (т.е. если векторная оценка исходаб* является Парето-оптимальной в множестве векторных оценок Q.

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

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

В случае, когда множество допустимых исходов является дискретным (конечным), получаем «картинку» типа изображенной на рис. 1.

Задача отыскания множества Парето решается следующим образом. Находим все точки с наибольшим значением U. Если их несколько, выбираем из них точку с наибольшим значениемV. Включаем ее в множество Парето. Отсекаем точки с меньшими либо равными значениями U и V (юго-западный угол с вершиной в выбранной точке). Повторяем процедуру для оставшейся части допустимой области. Таким образом, Парето-оптимальными являются исходы {4,5,7,8}.

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

Задача

Пусть на множестве щ плоскости (x,y), определяемой системой неравенств рис 2

заданы две линейные функции: U = x + y +2 и V = x - y + 6

Требуется найти решение задачи U > max, V > max

Решение.

Рассмотрим решение данной задачи методом идеальной точки.

Множество щ представляет собой пятиугольник (рис. 7), вершины которого имеют следующие координаты: A(0;0), B(0;2), C(2;2), D(4;1), E(4;0).

В силу линейности критериев U и V пятиугольник ABCDE переходит в пятиугольник A*B*C*D*E* (рис. 8), координаты вершин которого вычисляются по формулам (1): A*(2;6), B*(4;4), C*(6;6), D*(7;9), E*(6;10).

Находим границу Парето. Это отрезок D*E*. Точка утопии M*(7;10) считается заданной (ее координаты суть наибольшее значение U и V).

Требуется найти на множестве Парето точку, ближайшую к точке утопии M*. Из рисунка видно, что искомая точка должна лежать на отрезке D*E*. Проведем через точки D* и E* прямую. Пусть бU+вV=г

? ее уравнение. Чтобы отыскать конкретные значения параметров б,в и г, подставим в него координаты обеих точек D* и E*. Получим

6б+10в=г,

7б+9в=г.

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

Положим б = в = 1. Тогда г = 16 и U + V = 16

? искомое уравнение прямой.

По условию задачи нам нужно определить на прямой U + V = 16

точку M0(U0,V0), расстояние которой от точки M*(7;10) минимально, т.е. решить экстремальную задачу:

z = (U ? 7)2 + (V ? 10)2 > min.

Так как U = 16 ? V, то последнее соотношение можно переписать в виде

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

z = (9 ? V)2 + (V ? 10)2 > min..

Возведя в квадрат и приводя подобные, получаем, что

z = 2V2 ? 38V + 181> min..

Это уравнение описывает параболу с вершиной рис 5

Тогда U0=16?V0=16?9,5=6,5.

Идеальная точка M0(6,5;9,5)

Соответствующие значения x и y легко находятся из системы линейных уравнений

6,5 = x + y + 2

9,5 = x ? y + 6

Имеем x = 4, y = 0,5.

Замечание. Мы рассмотрели задачу, в которой

Ф (x,y) > max, Ш (x,y) > max.

На практике часто встречаются случаи, когда требования выглядят по-иному -

Ф (x,y) > max, Ш (x,y) > min,

Ф (x,y) > min, Ш (x,y) > min,

Функция И = ?Ш обладает следующим свойством: она достигает наибольшего значения в точности в тех точках, где функция Ш принимает наименьшее значение, и наоборот. Иными словами, условия Ш (x,y) > min и И (x,y) > max равносильны. Поэтому, поменяв в случае необходимости знак у критерия на противоположный, мы можем свести любую двухкритериальную задачу к уже рассмотренной.

1. Определите инвестиционные операции, оптимальные по Парето по критериям «эффективность -- риск», если случайные эффективности этих операций определяются следующими рядами распределения:

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