Реферат Цілочисельне програмування. Задача про призначення

Тема: Курсовые обзорные

лянемо i0 рівність системи (4.5), для якої виконується умова оптимальності, тобто

(4.6)

Нагадаємо, що найбільша ціла частина числа а, його не перевищують, позначається [а], а подрібнена позитивна-{а}. Причому

(4.7)

Наприклад, нехай а = 3,2. Маємо [3,2] = 3; {3,2} = 0,2; 3,2 = 3 +0,2. Нехай а = - 4,3. Маємо [-4,3] = -5, {-4,3} = 0,7, -4,3 = -5 + 0,7. p align="justify"> Перейдемо до подальшого вивчення рівняння (4.6). Знайдемо цілу і дробову частини його коефіцієнтів і . Відповідно до рівності (4.7), маємо:

(4.8)

Так як, за припущенням, неціле, то

Крім того, . Підставивши вираз (4.8) у рівність (4.6), отримаємо

(4.9)

Так як перший доданок рівності (4.9) є ціле число, то, для того щоб було цілим, необхідно, щоб другий доданок також було цілим, тобто величина

повинна бути цілим числом. Так як xio-координата допустимого цілочисельного рішення задачі (4.1) - (4.4), то Li0-завжди ціле число. Покажемо, що Li0? 0. Справді, величина

не може бути негативною. З умови (4.7) слід Так як Li0-ціле, то з припущення, що Li0> 0, має слідувати , що суперечить визначенню дробової частини числа.

Отже, доведено, що будь-яке припустиме рішення задачі (4.1) - (4.4) повинно задовольняти нерівності

(4.10)

Рішення задач

Завдання № 1

x1, x2, ..., x5 - план навантаження (од.)

| xi? 0, xi Є Z

| 5x1 + 8x2 + 3x3 + 2x4 + 7x5? 112

| x1 + 8x2 + 6x3 + 5x4 + 4x5? 109

x1 + 7x2 + 6x3 + 5x4 + 4x5? max.

Опорний план:

y1 = 112 y2 = 109

x1 = x2 = ... = x5 = 0