 |
|
|
Архитектура Астрономия Аудит Биология Ботаника Бухгалтерский учёт Войное дело Генетика География Геология Дизайн Искусство История Кино Кулинария Культура Литература Математика Медицина Металлургия Мифология Музыка Психология Религия Спорт Строительство Техника Транспорт Туризм Усадьба Физика Фотография Химия Экология Электричество Электроника Энергетика |
Раздел 5. Целочисленное решение задач линейного программирования
Определить оптимальные целочисленные переменные xj , j = 1,.., n в области их определения (6), при которых целевая функция F(x) достигает экстремального значения. F(x) = Σ сj*xj → max (min) (5.1) Σ aij*xj = bj , i = 1,..,m (5.2) xj ≥ 0 и целочисленные (5.3) Алгоритм определения оптимального целочисленного решения заключается в решении задачи симплекс-методом. Если решение целочисленное, цель достигнута. В противном случае следует добавить целочисленное ограничение, полученное из уравнения базисной переменной с нецелочисленным значением и повторить решение задачи симплекс-методом. Вывод ограничения, отсекающего нецелочисленное решение. Пусть оптимальное решение (5) существует и имеет конечное значение. Пусть Σ aj*xj = b (5.4) сумма нескольких уравнений из (6), каждое из которых умножено на некоторое число. Решение, удовлетворяющее системе (6), удовлетворяет и уравнению (8). Так как решение задачи может быть нецелочисленным, то в этом случае некоторые коэффициенты aj и b - не целочисленные. Чтобы получить целочисленные значения переменных xj, надо значения нецелочисленных коэффициентов aj и правой части b заменить на целочисленные [aj] и [ b], такие, что aj = [aj] + fj и b = [ b] + f, где 0 ≤ fj , f ≤ 1. При замене в (8) нецелочисленных aj и b на целочисленные [aj] и [ b] это равенство станет неравенством: Σ [aj]xj ≤ [b] (5.5) В самом деле, пусть 7x1 +4.5x2 = 31.5. Заменим 4.5 на 4, а 31.5 на 31. Тогда левая часть 7x1 +4x2 = 28 станет меньше 31. То есть 7x1 +4x2 < 31. Добавим слева в (9) . переменную x, которая для сохранения равенства должна быть целочисленной. Получим целочисленное уравнение Σ [aj] xj + x = [b] , (5.6) которое при введении в систему уравнений (6), позволит отсечь нецелочисленное решение. При решении задачи ЦЛП удобнее использовать другую форму этого ограничения, получаемую вычитанием равенства (8) из уравнения (10). При этом получим: (Σ [aj]xj + x) - Σ ajxj = [b] - b , или Σ [-fj]xj + x = -f (5.7) Приведём вывод отсекающего ограничения (11) из уравнения нецелочисленной базисной переменной. Пусть уравнение базисной переменной имеет вид: xk + Σ tijxj = b, (5.8). где xk - базисная переменная, i - строка, j – небазисные (с нулевыми значениями) переменные Пусть некоторые tij = [tij] + fij и b = [ b] + f - нецелочисленные, тогда добавляется целочисленное ограничение, отсекающее нецелочисленное решение задачи: (xk + Σ [tij]xj + x) – (xk + Σ tijxj)= [b] – b или Σ [-fj]xj + x = -f (5.9). Рассмотрим пример. 21x1 + 11x2 → max 7x1 + 4x2 ≤ 13 Необходимо получить целочисленное решение, максимизирующее цедевую функцию. Обозначим целевую функцию через x0 и добавим переменную x3 в ограничение x0 - 21x1 - 11x2 = 0 7x1 + 4x2 + x3 = 13 Выводим переменную x1 из числа нулевых, умножая ограничительное уравнение на три и складывая его с целевой функцией. Получаем базисную систему для следующей вершины симплекса. x 0 + x2 + 3x3 = 39 7x1 + 4x2 + x3 = 13 Переменные x2 и x3 равны нулю, но переменная x1 является нецелочисленной и равна 13/7. Делим ограничительное уравнение на 7 и добавляем уравнение с целочисленной переменной x4, отсекающее нецелочисленное решение x1 = 13/7. Считаем его опорным и исключаем переменную x2 из нулевых со значением, перемещающим базис в следующую вершину симплекса. Выбор переменной x2 позволяет минимально уменьшить значение целевой функции x0 = 39. x0 + x2 + 3x3 = 39 x1 + 4/7x2 + 1/7x3 = 13/7 - 4/7x2 - 1/7x3 + x4 = - 6/7 При этом получаем базисную систему для следующей вершины симплекса. x0 +11/4x3 +7/4x4 = 37.5 x1 + x4 = 1 x2 +1/4x3 - 7/4x4 = 1.5 Значение переменной x2 – не целое. Из базисного уравнения с нецелочисленной x2 выводим следующее отсекающее уравнение с целочисленной x5 и отсекающее нецелочисленное значение x2 = 1 ½. - 1/4x3 - 1/4x4 + x5 = - 0.5 С помощью этой опорной строки исключаем переменную Х3 из числа нулевых переменных. x0 - x4 + 11x5 = 32 x1 + x4 = 1 x2 - 2 x4 + x5 = 1 x3 + x4 - 4x5 = 2
На рис.5.1 представлена постановка этой же задачи в Excel
Рис.5.1 Постановка целочисленной задачи в Excel На рис.5.2 перемещаемся по Х1 в следующую вершину симплекса, в которой коэффициент при Х1 равен нулю и добавляем целочисленное уравнение, отсекающее нецелочисленное. решение
Рис.25. Отсечение первого нецелочисленного решения На рис.5.3 перемещаемся по Х2 в следующую вершину симплекса, в которой коэффициент при Х2 равен нулю и добавляем целочисленное уравнение, отсекающее нецелочисленное. решение
Рис.5.3 Отсечение второго нецелочисленного решения На рис.5.4 перемещаемся по Х3 в следующую вершину симплекса, в которой коэффициент при Х3 равен нулю и все переменные стали целочисленными.
Рис.5.4 Целочисленное решение задачи.
Варианты заданий по целочисленному программированию 21x1 + 11x2 → max 7x1 + 3x2 + x3 = 15, x1, x2, x3 ≥ 0 21x1 + 12x2 → max 7x1 + 4x2 + x3 = 16, x1, x2, x3 ≥ 0 21x1 + 11x2 → max 7x1 + 3x2 + x3 = 17, x1, x2, x3 ≥ 0 21x1 + 11x2 → max 7x1 + 3x2 + x3 = 18, x1, x2, x3 ≥ 0 22x1 + 11x2 → max 7x1 + 4x2 + x3 = 19, x1, x2, x3 ≥ 0 21x1 + 12x2 → max 7x1 + 4x2 + x3 = 20, x1, x2, x3 ≥ 0 21x1 + 11x2 → max 7x1 + 4x2 + x3 = 22, x1, x2, x3 ≥ 0 21x1 + 12x2 → max 7x1 + 5x2 + x3 = 23, x1, x2, x3 ≥ 0 21x1 + 11x2 → max 7x1 + 4x2 + x3 = 24, x1, x2, x3 ≥ 0 21x1 + 12x2 → max 8x1 + 4x2 + x3 = 25, x1, x2, x3 ≥ 0 21x1 + 11x2 → max 7x1 + 4x2 + x3 = 26, x1, x2, x3 ≥ 0 21x1 + 11x2 → max 7x1 + 4x2 + x3 = 27, x1, x2, x3 ≥ 0 21x1 + 13x2 → max 7x1 + 4x2 + x3 = 15, x1, x2, x3 ≥ 0 23x1 + 11x2 → max 7x1 + 4x2 + x3 = 29, x1, x2, x3 ≥ 0 21x1 + 11x2 → max 7x1 + 5x2 + x3 = 30, x1, x2, x3 ≥ 0 21x1 + 13x2 → max 7x1 + 4x2 + x3 = 13, x1, x2, x3 ≥ 0 21x1 + 12x2 → max 7x1 + 4x2 + x3 = 14, x1, x2, x3 ≥ 0 23x1 + 11x2 → max 7x1 + 4x2 + x3 = 15, x1, x2, x3 ≥ 0 21x1 + 12x2 → max 7x1 + 4x2 + x3 = 16 , x1, x2, x3 ≥ 0 21x1 + 15x2 → max 7x1 + 4x2 + x3 = 17, x1, x2, x3 ≥ 0 21x1 + 13x2 → max 7x1 + 4x2 + x3 = 18, x1, x2, x3 ≥ 0 21x1 + 12x2 → max 6x1 + 4x2 + x3 = 19, x1, x2, x3 ≥ 0 21x1 + 10x2 → max 7x1 + 4x2 + x3 = 20, x1, x2, x3 ≥ 0
21x1 + 12x2 → max 7x1 + 3x2 + x3 = 22, x1, x2, x3 ≥ 0 21x1 + 14x2 → max 7x1 + 4x2 + 2x3 = 23, x1, x2, x3 ≥ 0 21x1 + 12x2 → max 7x1 + 4x2 + 3x3 = 24, x1, x2, x3 ≥ 0 22x1 + 11x2 → max 7x1 + 5x2 + x3 = 25, x1, x2, x3 ≥ 0 21x1 + 12x2 → max 9x1 + 4x2 + x3 = 26, x1, x2, x3 ≥ 0 21x1 + 11x2 → max 7x1 + 4x2 + x3 = 27, x1, x2, x3 ≥ 0 20x1 + 12x2 → max 7x1 + 4x2 + x3 = 28, x1, x2, x3 ≥ 0 21x1 + 11x2 → max 7x1 + 4x2 + x3 = 29, x1, x2, x3 ≥ 0 21x1 + 10x2 → max 7x1 + 5x2 + x3 = 30, x1, x2, x3 ≥ 0 19x1 + 11x2 → max 7x1 + 4x2 + x3 = 31, x1, x2, x3 ≥ 0 20x1 + 12x2 → max 7x1 + 4x2 + x3 = 13, x1, x2, x3 ≥ 0 21x1 + 13x2 → max 7x1 + 4x2 + x3 = 14, x1, x2, x3 ≥ 0 22x1 + 14x2 → max 7x1 + 4x2 + x3 = 15, x1, x2, x3 ≥ 0 23x1 + 15x2 → max 7x1 + 4x2 + x3 = 16, x1, x2, x3 ≥ 0 24x1 + 16x2 → max 7x1 + 4x2 + x3 = 17, x1, x2, x3 ≥ 0 25x1 + 17x2 → max 7x1 + 4x2 + x3 = 18, x1, x2, x3 ≥ 0 26x1 + 18x2 → max 7x1 + 4x2 + x3 = 19, x1, x2, x3 ≥ 0 27x1 + 10x2 → max 7x1 + 4x2 + 2x3 = 20, x1, x2, x3 ≥ 0 28x1 + 11x2 → max 7x1 + 4x2 + x3 = 21, x1, x2, x3 ≥ 0 29x1 + 12x2 → max 7x1 + 4x2 + x3 = 22, x1, x2, x3 ≥ 0 21x1 + 13x2 → max 7x1 + 4x2 + x3 = 23, x1, x2, x3 ≥ 0 26x1 + 14x2 → max 7x1 + 4x2 + x3 = 24, x1, x2, x3 ≥ 0 21x1 + 15x2 → max 7x1 + 4x2 + x3 = 25, x1, x2, x3 ≥ 0 21x1 + 16x2 → max 7x1 + 4x2 + x3 = 26, x1, x2, x3 ≥ 0 21x1 + 17x2 → max 7x1 + 4x2 + x3 = 27, x1, x2, x3 ≥ 0 21x1 + 18x2 → max 7x1 + 4x2 + x3 = 28, x1, x2, x3 ≥ 0 21x1 + 10x2 → max 7x1 + 4x2 + x3 = 29, x1, x2, x3 ≥ 0 21x1 + 19x2 → max 7x1 + 4x2 + x3 = 30, x1, x2, x3 ≥ 0 21x1 + 9x2 → max 7x1 + 4x2 + x3 = 31, x1, x2, x3 ≥ 0
Поиск по сайту: |
