6 ответов

Следуйте этому примеру: предположим, что уравнения:

7 = x + 3y + 4z + 9w 12 = 4x + 2y + 3z + 7w

Существует 2 уравнения и 4 неизвестных. Вы можете установить 2 из неизвестных как параметры, поэтому система будет иметь столько уравнений, сколько неизвестных:

7 - (4z + 9w) = x + 3y 12 - (3z + 7w) = 4x + 2y

Мы будем использовать x и y как неизвестные. Его можно решить и оставить w и z в качестве параметров в линейном решении:

X = (22 - 3w - z)/10 y = (16 - 29w - 13z)/10

Теперь вам нужно сделать числители делящимися на 10, знаменатель. Если есть решение, вы можете проверить все параметры от 1 до 10.

В общем, вы делаете это:

• Выберите параметры так, чтобы было столько неизвестных, как уравнения. Попытайтесь оставить неизвестные, которые генерируют наименьшее абсолютное значение для определителя (в примере это было 10, но выбор y и z был бы лучше, так как это было бы | det | = 3)
• Решите линейную систему и создайте ответ в зависимости от параметров
• Проверьте значения параметров от 1 до абсолютного значения det (если есть решение, вы найдете его в этой точке), пока не будет целочисленное решение для всех неизвестных (именно поэтому вы выбираете наименьшее детерминантное значение перед) и проверьте, является ли оно положительным (это не было проиллюстрировано в примере).

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

EDIT1

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

22 = 3w + z (congruent, mod 10) 16 = 29w + 13z (congruent, mod 10)

Применение модуля:

2 = 3w + z (congruent, mod 10) 6 = 9w + 3z (congruent, mod 10)

Вы можете сделать систему конгруэнций треугольной (гауссово исключение), умножая конгруэнцию обратными в модуле 10 и суммируя до других. Обратный к 9 в модуле 10 равен -1, поэтому мы умножаем последнюю конгруэнцию:

2 = 3w + z (congruent, mod 10) -6 = -9w + -3z (congruent, mod 10)

Эквивалент:

2 = 3w + z (congruent, mod 10) 4 = w + 7z (congruent, mod 10)

Затем умножьте на -3 и добавьте к первому:

2 - 3*4 = 3w + z -3w - 21z (congruent, mod 10) 4 = w + 7z (congruent, mod 10)

Эквивалент:

10 = -20z (congruent, mod 10) 4 = w + 7z (congruent, mod 10)

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

Сообщите мне, есть ли еще что-то непонятное!

Если я правильно понимаю проблему, у вас есть несколько пакетов, каждый из которых имеет разные почтовые расходы. Вы хотите оплатить эти почтовые расходы из пула марок, которые у вас есть. Можно решить проблему с целым программированием. Решение ниже решает для всех пакетов сразу. У вас будет число переменных, равное numPackages * numStampDenominations (вероятно, неудобно для большого количества пакетов).

Ограничение равенства выглядит как Aeqx = beq. Матрица Aeq для двух пакетов с четырьмя марками (numVarsnumPackages) выглядит так:

21 .68 .47 .01 .00 .00 .00 .00 .89 * x = .00 .00 .00 .00 .21 .68 .47 .01 .50

Первая строка - это коэффициенты ограничений (значения штампа) для пакета 1. Ненулевые коэффициенты - это значения штампа. Нулевая переменная, связанная с другими пакетами, не заботится.

Второй набор ограничений (неравенство) касается пула марок, которые у меня имеются. Ограничение неравенства выглядит как A * x = b. Матрица A для 4 штампов и 8 переменных (numPackages * numStampDenominations) выглядит так:

1 0 0 0 1 0 0 0 10 0 1 0 0 0 1 0 0 10 * x <= 0 0 1 0 0 0 1 0 10 0 0 0 1 0 0 0 1 20

Функция стоимости - это f "* x, которая представляет собой общее количество штампов. Его коэффициенты являются просто единицами в виде вектора столбца.

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

% The value of each stamp available as a 4x1 matrix sv = [.21; .68; .47; .01]; % The number of each stamp available as a 4x1 matrix sq = ; % Number of demominations m = size(sv, 1); % The postage required for each package as a 4x1 matrix % -- probably read from a file postage = [.89;.50;1.01;.47;.47]; % Number of packages -- just a count of the postage rows packageCount = size(postage, 1); % Number of variables is m*packageCount numVar = m*packageCount; % lower bound -- zero stamps of a given denomination lb = zeros(numVar,1); % upper bound -- use constraints for upper bound ub = ; % The cost function -- minimize the number of stamps used % min(f"*x) f = ones(numVar,1); % integer constraints intcon = 1:numVar; % Construct postage constraint matrix Aeq = zeros(numVar, packageCount); for i = 1:packageCount first = i*m - 3; last = first + 3; Aeq(first:last,i) = sv(:); end % Construct stamp count constraint matrix A = zeros(numVar, m); for r = 1:m for j = 1:m c = (j-1)*m + 1; A(c,r) = 1; end end x = intlinprog(f, intcon, A", b, Aeq", beq, lb, ub)

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

Вы просто находите решения, как если бы это была обычная система, поэтому вы можете найти бесконечно много решений:

Пример:

Y = x + 3

то действительная пара чисел (2,5) является возможным реальным решением для этой системы, как только у вас будет бесконечно много решений, вы просто ограничиваете подмножество решений, которые производятся целыми числами.

Конечно, у вас есть ограничения, в нашем случае решение имеет только 1 свободную переменную, поэтому мы можем написать все такие решения:

(x, x+3)

Удивление:

Если там где-то есть иррациональное число, нет целочисленных решений:

(x, x+pi) => neither 1st or 2nd number here can be whole at same time

Таким образом, вы можете найти целочисленные решения тогда и только тогда, когда ваши "бесконечно много решений" ограничены целыми или рациональными числами.

Предположим, что у вас есть следующий вектор:

(3x, (2/5)y, y, x, x+y)

Тогда целое решение может быть:

X=3 y=10/2

Если вы чувствуете, что ответ вам не подходит, просто скажите: я удалю его, чтобы не получить очки бонусов.

Уравнения в целых числах – это алгебраические уравнения с двумя или более неизвестными переменными и целыми коэффициентами. Решениями такого уравнения являются все целочисленные (иногда натуральные или рациональные) наборы значений неизвестных переменных, удовлетворяющих этому уравнению. Такие уравнения ещё называют диофантовыми , в честь древнегреческого математика , который исследовал некоторые типы таких уравнений ещё до нашей эры.

Современной постановкой диофантовых задач мы обязаны французскому математику . Именно он поставил перед европейскими математиками вопрос о решении неопределённых уравнений только в целых числах. Наиболее известное уравнение в целых числах – великая теорема Ферма: уравнение

не имеет ненулевых рациональных решений для всех натуральных n > 2.

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

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

При решении уравнений в целых и натуральных числах можно условно выделить следующие методы:

способ перебора вариантов;

применение алгоритма Евклида;

представление чисел в виде непрерывных (цепных) дробей;

разложения на множители;

решение уравнений в целых числах как квадратных (или иных) относительно какой-либо переменной;

метод остатков;

метод бесконечного спуска.

Задачи с решениями

1. Решить в целых числах уравнение x 2 – xy – 2y 2 = 7.

Запишем уравнение в виде (x – 2y)(x + y) = 7.

Так как х, у – целые числа, то находим решения исходного уравнения, как решения следующих четырёх систем:

1) x – 2y = 7, x + y = 1;

2) x – 2y = 1, x + y = 7;

3) x – 2y = –7, x + y = –1;

4) x – 2y = –1, x + y = –7.

Решив эти системы, получаем решения уравнения: (3; –2), (5; 2), (–3; 2) и (–5; –2).

Ответ: (3; –2), (5; 2), (–3; 2), (–5; –2).

а) 20х + 12у = 2013;

б) 5х + 7у = 19;

в) 201х – 1999у = 12.

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

Ответ: решений нет.

б) Подберём сначала некоторое конкретное решение. В данном случае, это просто, например,

x 0 = 1, y 0 = 2.

5x 0 + 7y 0 = 19,

5(х – x 0) + 7(у – y 0) = 0,

5(х – x 0) = –7(у – y 0).

Поскольку числа 5 и 7 взаимно простые, то

х – x 0 = 7k, у – y 0 = –5k.

Значит, общее решение:

х = 1 + 7k, у = 2 – 5k,

где k – произвольное целое число.

Ответ: (1+7k; 2–5k), где k – целое число.

в) Найти некоторое конкретное решение подбором в данном случае достаточно сложно. Воспользуемся алгоритмом Евклида для чисел 1999 и 201:

НОД(1999, 201) = НОД(201, 190) = НОД(190, 11) = НОД(11, 3) = НОД(3 , 2) = НОД(2, 1) = 1.

Запишем этот процесс в обратном порядке:

1 = 2 – 1 = 2 – (3 – 2) = 2·2 – 3 = 2· (11 – 3·3) – 3 = 2·11 – 7·3 = 2·11 – 7(190 – 11·17) =

121·11 – 7·190 = 121(201 – 190) – 7·190 = 121·201 – 128·190 =

121·201 – 128(1999 – 9·201) = 1273·201 – 128·1999.

Значит, пара (1273, 128) является решением уравнения 201х – 1999у = 1. Тогда пара чисел

x 0 = 1273·12 = 15276, y 0 = 128·12 = 1536

является решением уравнения 201х – 1999у = 12.

Общее решение этого уравнения запишется в виде

х = 15276 + 1999k, у = 1536 + 201k, где k – целое число,

или, после переобозначения (используем, что 15276 = 1283 + 7·1999, 1536 = 129 + 7·201),

х = 1283 + 1999n, у = 129 + 201n, где n – целое число.

Ответ: (1283+1999n, 129+201n), где n – целое число.

3. Решить в целых числах уравнение:

а) x 3 + y 3 = 3333333;

б) x 3 + y 3 = 4(x 2 y + xy 2 + 1).

а) Так как x 3 и y 3 при делении на 9 могут давать только остатки 0, 1 и 8 (смотрите таблицу в разделе ), то x 3 + y 3 может давать только остатки 0, 1, 2, 7 и 8. Но число 3333333 при делении на 9 даёт остаток 3. Поэтому исходное уравнение не имеет решений в целых числах.

б) Перепишем исходное уравнение в виде (x + y) 3 = 7(x 2 y + xy 2) + 4. Так как кубы целых чисел при делении на 7 дают остатки 0, 1 и 6, но не 4, то уравнение не имеет решений в целых числах.

Ответ: целочисленных решений нет.

а) в простых числах уравнение х 2 – 7х – 144 = у 2 – 25у;

б) в целых числах уравнение x + y = x 2 – xy + y 2 .

а) Решим данное уравнение как квадратное относительно переменной у. Получим

у = х + 9 или у = 16 – х.

Поскольку при нечётном х число х + 9 является чётным, то единственной парой простых чисел, которая удовлетворяет первому равенству, является (2; 11).

Так как х, у – простые, то из равенства у = 16 – х имеем

2 х 16, 2 у 16.

С помощью перебора вариантов находим остальные решения: (3; 13), (5; 11), (11; 5), (13; 3).

Ответ: (2; 11), (3; 13), (5; 11), (11; 5), (13; 3).

б) Рассмотрим данное уравнение как квадратное уравнение относительно x:

x 2 – (y + 1)x + y 2 – y = 0.

Дискриминант этого уравнения равен –3y 2 + 6y + 1. Он положителен лишь для следующих значений у: 0, 1, 2. Для каждого из этих значений из исходного уравнения получаем квадратное уравнение относительно х, которое легко решается.

Ответ: (0; 0), (0; 1), (1; 0), (1; 2), (2; 1), (2; 2).

5. Существует ли бесконечное число троек целых чисел x, y, z таких, что x 2 + y 2 + z 2 = x 3 + y 3 + z 3 ?

Попробуем подбирать такие тройки, где у = –z. Тогда y 3 и z 3 будут всегда взаимно уничтожаться, и наше уравнение будет иметь вид

x 2 + 2y 2 = x 3

или, иначе,

x 2 (x–1) = 2y 2 .

Чтобы пара целых чисел (x; y) удовлетворяла этому условию, достаточно, чтобы число x–1 было удвоенным квадратом целого числа. Таких чисел бесконечно много, а именно, это все числа вида 2n 2 +1. Подставляя в x 2 (x–1) = 2y 2 такое число, после несложных преобразований получаем:

y = xn = n(2n 2 +1) = 2n 3 +n.

Все тройки, полученные таким образом, имеют вид (2n 2 +1; 2n 3 +n; –2n 3 – n).

Ответ: существует.

6. Найдите такие целые числа x, y, z, u, что x 2 + y 2 + z 2 + u 2 = 2xyzu.

Число x 2 + y 2 + z 2 + u 2 чётно, поэтому среди чисел x, y, z, u чётное число нечётных чисел.

Если все четыре числа x, y, z, u нечётны, то x 2 + y 2 + z 2 + u 2 делится на 4, но при этом 2xyzu не делится на 4 – несоответствие.

Если ровно два из чисел x, y, z, u нечётны, то x 2 + y 2 + z 2 + u 2 не делится на 4, а 2xyzu делится на 4 – опять несоответствие.

Поэтому все числа x, y, z, u чётны. Тогда можно записать, что

x = 2x 1 , y = 2y 1 , z = 2z 1 , u = 2u 1 ,

и исходное уравнение примет вид

x 1 2 + y 1 2 + z 1 2 + u 1 2 = 8x 1 y 1 z 1 u 1 .

Теперь заметим, что (2k + 1) 2 = 4k(k + 1) + 1 при делении на 8 даёт остаток 1. Поэтому если все числа x 1 , y 1 , z 1 , u 1 нечётны, то x 1 2 + y 1 2 + z 1 2 + u 1 2 не делится на 8. А если ровно два из этих чисел нечётно, то x 1 2 + y 1 2 + z 1 2 + u 1 2 не делится даже на 4. Значит,

x 1 = 2x 2 , y 1 = 2y 2 , z 1 = 2z 2 , u 1 = 2u 2 ,

и мы получаем уравнение

x 2 2 + y 2 2 + z 2 2 + u 2 2 = 32x 2 y 2 z 2 u 2 .

Снова повторив те же самые рассуждения, получим, что x, y, z, u делятся на 2 n при всех натуральных n, что возможно лишь при x = y = z = u = 0.

Ответ: (0; 0; 0; 0).

7. Докажите, что уравнение

(х – у) 3 + (y – z) 3 + (z – x) 3 = 30

не имеет решений в целых числах.

Воспользуемся следующим тождеством:

(х – у) 3 + (y – z) 3 + (z – x) 3 = 3(х – у)(y – z)(z – x).

Тогда исходное уравнение можно записать в виде

(х – у)(y – z)(z – x) = 10.

Обозначим a = x – y, b = y – z, c = z – x и запишем полученное равенство в виде

Кроме того очевидно, a + b + c = 0. Легко убедиться, что с точностью до перестановки из равенства abc = 10 следует, что числа |a|, |b|, |c| равны либо 1, 2, 5, либо 1, 1, 10. Но во всех этих случаях при любом выборе знаков a, b, c сумма a + b + c отлична от нуля. Таким образом, исходное уравнение не имеет решений в целых числах.

8. Решить в целых числах уравнение 1! + 2! + . . . + х! = у 2 .

Очевидно, что

если х = 1, то у 2 = 1,

если х = 3, то у 2 = 9.

Этим случаям соответствуют следующие пары чисел:

х 1 = 1, у 1 = 1;

х 2 = 1, у 2 = –1;

х 3 = 3, у 3 = 3;

х 4 = 3, у 4 = –3.

Заметим, что при х = 2 имеем 1! + 2! = 3, при х = 4 имеем 1! + 2! + 3! + 4! = 33 и ни 3, ни 33 не являются квадратами целых чисел. Если же х > 5, то, так как

5! + 6! + . . . + х! = 10n,

можем записать, что

1! + 2! + 3! + 4! + 5! + . . . + х! = 33 + 10n.

Так как 33 + 10n – число, оканчивающееся цифрой 3, то оно не является квадратом целого числа.

Ответ: (1; 1), (1; –1), (3; 3), (3; –3).

9. Решите следующую систему уравнений в натуральных числах:

a 3 – b 3 – c 3 = 3abc, a 2 = 2(b + c).

3abc > 0, то a 3 > b 3 + c 3 ;

таким образом имеем

Складывая эти неравенства, получим, что

С учётом последнего неравенства, из второго уравнения системы получаем, что

Но второе уравнение системы также показывает, что а – чётное число. Таким образом, а = 2, b = c = 1.

Ответ: (2; 1; 1)

10. Найти все пары целых чисел х и у, удовлетворяющих уравнению х 2 + х = у 4 + у 3 + у 2 + у.

Разложив на множители обе части данного уравнения, получим:

х(х + 1) = у(у + 1)(у 2 + 1),

х(х + 1) = (у 2 + у)(у 2 + 1)

Такое равенство возможно, если левая и правая части равны нулю, или представляют собой произведение двух последовательных целых чисел. Поэтому, приравнивая к нулю те или иные множители, получим 4 пары искомых значений переменных:

х 1 = 0, у 1 = 0;

х 2 = 0, у 2 = –1;

х 3 = –1, у 3 = 0;

х 4 = –1, у 4 = –1.

Произведение (у 2 + у)(у 2 + 1) можно рассматривать как произведение двух последовательных целых чисел, отличных от нуля, только при у = 2. Поэтому х(х + 1) = 30, откуда х 5 = 5, х 6 = –6. Значит, существуют ещё две пары целых чисел, удовлетворяющих исходному уравнению:

х 5 = 5, у 5 = 2;

х 6 = –6, у 6 = 2.

Ответ: (0; 0), (0; –1), (–1; 0), (–1; –1), (5; 2), (–6; 2.)

Задачи без решений

1. Решить в целых числах уравнение:

а) ху = х + у + 3;

б) х 2 + у 2 = х + у + 2.

2. Решить в целых числах уравнение:

а) х 3 + 21у 2 + 5 = 0;

б) 15х 2 – 7у 2 = 9.

3. Решить в натуральных числах уравнение:

а) 2 х + 1 = у 2 ;

б) 3·2 х + 1 = у 2 .

4. Доказать, что уравнение х 3 + 3у 3 + 9z 3 = 9xyz в рациональных числах имеет единственное решение

5. Доказать, что уравнение х 2 + 5 = у 3 в целых числах не имеет решений.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Введение

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

3. Параметрическое программирование

3.1 Задача с параметром в целевой функции

3.2 Задача с параметром в свободных членах системы ограничений

3.3 Задача, целевая функция и правая часть ограничений которой содержит параметр

4. Целочисленное параметрическое программирование

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

4.2 Пример решения задачи целочисленного программирования с параметром в свободных членах системы ограничений

Заключение

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

Введение

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

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

при условиях , где и – заданные функции, а – некоторые действительные числа.

В зависимости от свойств функций

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

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

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

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

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

В первой главе данной работы рассмотрены основные понятия линейного программирования.

Во второй главе сформулирована задача целочисленного программирования и рассмотрены методы её решения. Приведён пример решение задачи целочисленного программирования.

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

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

При написании диплома использовалась следующая справочная литература: Кузнецов Ю.Н., Кузубов В.И., Волощенко А.Б. Математическое программирование, Ашманов С.А. Линейное программирование. Некоторые примеры были взяты из книг Копылов В.И. Лекции и практические занятия по математическому программированию, Акулич И.Л. Математическое программирование в примерах и задачах. Алгоритмы методов решения задач целочисленного и параметрического программирования наиболее доступно и полно, на мой взгляд, раскрываются в книге Акулич И.Л.

1. Основные понятия линейного программирования

Различают три основные формы задач линейного программирования в зависимости от ограничений разного типа.

Стандартная задача

(1.1) (1.2)

В матричной форме задача (1.1) - (1.2) имеет вид:

- матрица коэффициентов. Вектор называют вектором коэффициентов линейной формы, вектор – вектором ограничений.

Каноническая задача линейного программирования имеет вид:

или, в матричной форме:

Общая задача линейного программирования – часть ограничений выражается в виде неравенств, часть – в виде уравнений. Кроме того, не ко всем переменным относится условие неотрицательности:

Теорема. Стандартная, каноническая и общая задачи линейного программирования эквивалентны.

Замечание. Тот случай, когда в стандартной задаче требуется минимизировать линейную форму, легко сводится к задаче на максимум – следует рассмотреть задачу на максимум функции

при тех же ограничениях на переменные, что и в исходной задаче.

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

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

2.1 Постановка задачи и методы решения

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

Требуется найти минимальное значение линейной функции

(2.1.1)

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

(2.1.2) (2.1.3)
- целые. (2.1.4)

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

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

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

2) так как линейная функция достигает оптимума в угловой точке многогранника решений, то построением такого многогранника и обеспечивается целочисленность оптимального решения.

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

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

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