Лінійне програмування - PDF скачати безкоштовно

ГЛАВА 1 Лінійне програмування 1.1. Що таке лінійне програмування 1.1.1. Приклад: проблема режиму Поллі [1, с.3]. Добові потреби: Енергія: 2000 ккал Білок: 55 г Кальцій: 800 мг Доступна їжа Порція Енергія (ккал) Білок (г) Кальцій (мг) Ціна/порція Зернові культури 28 г 110 4 2 3 Курка 100 г 205 32 12 24 Яйця 2 великі 160 13 54 13 Цільне молоко 237 куб. См. 160 8 285 9 Терпкий пиріг 170 г 420 4 22 20 Свинина та квасоля 260 г 260 14 80 19 Який вибір для Полі? Обмеження: Крупи: не більше 4 порцій на день Курка: не більше 3 порцій на день Яйця: не більше 2 порцій на день Молоко: не більше 8 порцій на день Пиріг: не більше 2 порцій на день Свинина і квасоля: не більше 2 порцій на день Завдання 1.1.1. Чи може Поллі знайти рішення? Як формалізувати проблему? (моделювання) Що робить проблему конкретною? Чи знаєте ви, як вирішити подібні проблеми? 1.1.2. Стандартна форма задачі лінійного програмування. Проблема. [1, с. 5] 1

лінійне

2 1. ЛІНІЙНЕ ПРОГРАМУВАННЯ Визначення. Задача лінійного програмування у стандартній формі: Розгорнути: За обмеженнями: z: = cjxja ij xjbi, для i = 1.mxj 0, для j = 1. n Вибір змінних (x 1.xn) називається рішенням задачі. Рішення можливо, якщо воно відповідає обмеженням. z називається цільовою функцією. З кожним рішенням воно пов'язує значення. Рішення є оптимальним, якщо воно здійсненне та максимізує цільову функцію. Вправа 1. Чи можемо ми подати попередні приклади у стандартній формі? 1.1.3. Існування оптимальних рішень? Завдання 1.1.2. [1, с. 7] Розглянемо наступні три стандартні задачі лінійного програмування, написані із синтаксисом комп'ютерної системи алгебри MuPAD: Chvatal7a: = [[x1 0. Якщо рівняння в таблиці не обмежують X i, система необмежена: половина -лінія, описана (0, 0, X i, 0, 0) для X i 0, складається з можливих рішень, які дають величини, наскільки великі, як бажано, до z.

1.3. ПАСТКИ І ЯК ЇХ УНИКНУТИ 9 Приклад. Впровадження допоміжної системи P 0, щоб визначити, чи можливо P: Розгорнути: x 0 За обмеженими умовами: 2x 1 x 2 + 2x 3 x 0 4 2x 1 3x 2 + x 3 x 0 5 x 1 + x 2 2x 3 x 0 1 x 0, x 1, x 2, x 3 0 Примітки: P 0 можливо (взяти x 0 досить великим); Доцільні рішення P відповідають можливим рішенням P 0 з x 0 = 0; P можливо тоді і тільки тоді, коли P 0 має можливе рішення з x 0 = 0. Давайте вивчимо цю нову систему: Chvatal40: = [[-x1 + x2-2 * x3 - x0