Рефераты
 

Математичне моделювання економічних систем

Математичне моделювання економічних систем

26

Міністерство освіти і науки України

Черкаський національний університет імені Богдана Хмельницького

Факультет інформаційних технологій і

біомедичної кібернетики

РОЗРАХУНКОВА РОБОТА

з курсу „Математичне моделювання економічних систем

студента 4-го курсу спеціальності

«інтелектуальні системи прийняття рішень»

Валяєва Олександра В'ячеславовича

Черкаси - 2006 р.

Зміст

  • Зміст
  • Завдання 1. Задача лінійного програмування
  • Завдання 2. Задача цілочислового програмування
  • Завдання 3. Задача дробово-лінійного програмування
  • Завдання 4. Транспортна задача
  • Завдання 5. Задача квадратичного програмування
  • Список використаної літератури
  • Завдання 1. Задача лінійного програмування

 Для заданої задачі лінійного програмування побудувати двоїсту задачу. Знайти розв'язок прямої задачі геометричним методом і симплекс-методом. Знайти розв'язок двоїстої задачі, використовуючи результати розв'язування прямої задачі симплекс-методом:

  • 3. ,
  • Розв?язання геометричним методом
  • Побудуємо прямі, рівняння яких одержуються внаслідок заміни в обмеженнях знаків нерівностей на знаки рівностей.
  • I:

    6

    0

    0

    9

    II:

    0

    -6

    6

    0

    III:

    0

    4

    4

    0

    Визначимо півплощини, що задовольняють нашим нерівностям.

    • Умовам невід'ємності та відповідає перша чверть.

    Заштрихуємо спільну частину площини, що задовольняє всім нерівностям.

    Побудуємо вектор нормалі .

    Максимального значення функція набуває в точці перетину прямих I та II.

    Знайдемо координати цієї точки.

    Приведемо систему до канонічного вигляду

    Відповідь:

    Розв?язання симплекс-методом

    Приведемо систему рівнянь до канонічного вигляду

    x(0)=(0,0,18,6,0,4)

    Цільова функція

    Побудуємо симплекс-таблицю

    I

    базис

    P0

    2

    3

    0

    0

    0

    -M

    P1

    P2

    P3

    P4

    P5

    P6

    1

    P3

    0

    18

    3

    2

    1

    0

    0

    0

    2

    P4

    0

    6

    -1

    1

    0

    1

    0

    0

    3

    P6

    -M

    4

    1

    1

    0

    0

    -1

    1

    4

    0

    -2

    -3

    0

    0

    0

    0

    5

    -4

    -1

    -1

    0

    0

    1

    0

    Отриманий план не оптимальний

    Обраний ключовий елемент (3,2)

    I

    базис

    P0

    2

    3

    0

    0

    0

    -M

    P1

    P2

    P3

    P4

    P5

    P6

    1

    P3

    0

    10

    1

    0

    1

    0

    2

    -2

    2

    P4

    0

    2

    -2

    0

    0

    1

    1

    -1

    3

    P2

    3

    4

    1

    1

    0

    0

    -1

    -1

    4

    12

    1

    0

    0

    0

    -3

    -3

    5

    0

    0

    0

    0

    0

    0

    -1

    Отриманий план не оптимальний

    Обраний ключовий елемент (2,5)

    I

    базис

    P0

    2

    3

    0

    0

    0

    -M

    P1

    P2

    P3

    P4

    P5

    P6

    1

    P3

    0

    6

    5

    0

    1

    -2

    0

    0

    2

    P5

    0

    2

    -2

    0

    0

    1

    1

    -1

    3

    P2

    3

    6

    -1

    1

    0

    1

    0

    0

    4

    18

    -5

    0

    0

    3

    0

    0

    5

    0

    0

    0

    0

    0

    0

    -1

    Отриманий план не оптимальний

    Обраний ключовий елемент (1,1)

    I

    базис

    P0

    2

    3

    0

    0

    0

    -M

    P1

    P2

    P3

    P4

    P5

    P6

    1

    P1

    2

    6/5

    1

    0

    1/5

    -2/5

    0

    0

    2

    P5

    0

    22/5

    0

    0

    2/5

    1/5

    1

    -1

    3

    P2

    3

    36/5

    0

    1

    1/5

    3/5

    0

    0

    4

    24

    0

    0

    1

    1

    0

    0

    5

    0

    0

    0

    0

    0

    0

    1

    План оптимальний

    Розв'язок: X*(,) F*=24;

    Розв'язок двоїстої задач

    Побудуємо двоїсту функцію

    3. ,

    Система обмежень

    Скористаємось теоремою

    Якщо задача лінійного програмування в канонічній формі (7)-(9) має оптимальний план , то є оптимальним планом двоїстої задачі

    , ,

    Розв'язок:

    Fmin*= 9,6;

    Завдання 2. Задача цілочислового програмування

    Для задачі із завдання 1, як для задачі цілочислового програмування, знайти розв'язки геометричним методом і методом Гоморі.

    Розв?язання геометричним методом

    ,

    Відповідь:

    Розв?язання методом Гоморі

    Наведемо останню симплекс-таблицю

    I

    базис

    P0

    2

    3

    0

    0

    0

    -M

    P1

    P2

    P3

    P4

    P5

    P6

    1

    P1

    2

    6/5

    1

    0

    1/5

    -2/5

    0

    0

    2

    P5

    0

    22/5

    0

    0

    2/5

    1/5

    1

    -1

    3

    P2

    3

    36/5

    0

    1

    1/5

    3/5

    0

    0

    4

    24

    0

    0

    1

    1

    0

    0

    5

    0

    0

    0

    0

    0

    0

    1

    Побудуємо нерівність Гоморі за першим аргументом.

    I

    базис

    P0

    2

    3

    0

    0

    0

    0

    P1

    P2

    P3

    P4

    P5

    P7

    1

    P1

    2

    6/5

    1

    0

    1/5

    -2/5

    0

    0

    2

    P5

    0

    22/5

    0

    0

    2/5

    1/5

    1

    0

    3

    P2

    3

    36/5

    0

    1

    1/5

    3/5

    0

    0

    4

    P7

    0

    -1/5

    0

    0

    -1/5

    -3/5

    0

    1

    5

    24

    0

    0

    1

    1

    0

    0

    Обраний розв'язковий елемент (4,4)

    I

    базис

    P0

    2

    3

    0

    0

    0

    0

    P1

    P2

    P3

    P4

    P5

    P7

    1

    P1

    2

    1

    1

    0

    0

    -1

    0

    0

    2

    P5

    0

    4

    0

    0

    0

    11/5

    1

    0

    3

    P2

    3

    7

    0

    1

    0

    0

    0

    0

    4

    P4

    0

    2

    0

    0

    1

    3

    0

    1

    5

    14

    0

    0

    0

    2

    0

    0

    Отриманий план являється оптимальним і цілочисельним.

    Розв'язок: X*(1,7) Fmax*=23;

    Відповідь: цілочисельною точкою максимуму даної задачі є точка (1,7)

    Завдання 3. Задача дробово-лінійного програмування

    Для задачі дробово-лінійного програмування знайти розв'язки геометричним методом і симплекс-методом:

    ,

    Розв?язання геометричним методом

    Визначимо, в яку сторону потрібно обертати пряму навколо початку координат, щоб значення цільової функції збільшувалось. Таким чином ми визначимо яка з крайніх точок є точкою максимуму.

    f(1;0) = 2/3 f(0;1) = 3/7

    Тобто при крутінні прямої проти годинникової стрілки значення цільової функції зменшується.

    Використаємо результати обчислень і геометричних побудов з попереднього завдання.

    З графіка очевидно, що розв'язок лежить на перетині двох прямих. Для визначення точки перетину прямої І та ІІ розв?яжемо систему з двох рівнянь.

    Відповідь: функція набуває максимального значення при x1=6/5, x2=36/5.

    Розв?язання симплекс-методом

    Перейдемо від задачі дробово-лінійного програмування до задачі лінійного програмування.

    Вводим заміну:

    Вводим ще одну заміну:

    Після замін наша задача має такий вигляд:


    Приведемо її до канонічної форми і доповнимо її базисами:

    Повернемось до заміни:

    x1=0 x2=6

    Завдання 4. Транспортна задача

    Для заданих транспортних задач скласти математичну модель і розв'язати їх методом потенціалів, використавши для визначення початкового плану метод мінімального елемента або північно-західного кута.

    1. Запаси деякого однорідного продукту знаходяться на трьох пунктах постачання (базах) A1, A2, A3 і цей продукт потрiбно доставити в три пункти споживання (призначення) B1, B2, B3. Задача полягає в тому, щоб визначити, яку кiлькiсть продукту потрiбно перевезти з кожного пункту постачання (бази) до кожного пункту споживання (призначення) так, щоб забезпечити вивезення всього наявного продукту з пунктів постачання, задовільнити повністю потреби кожного пункту споживання і при цьому сумарна вартiсть перевезень була б мiнiмальною (зворотні перевезення виключаються). Вартість перевезень сij (у грн.) з бази Аi до пункту призначення Bj вказана в таблиці, де також наведені дані про запаси ai (у тонанх) продукту і його потреби (у тонах) bj.

    Пункти

    Пункти споживання

    Запаси

    постачання

    B1

    B2

    B3

    A1

    3

    5

    7

    270

    A2

    6

    9

    4

    180

    A3

    11

    8

    10

    300

    Потреби

    260

    280

    300

    Для даної транспортної задачі не виконується умова балансу , тому введемо додатковий пункт постачання з запасами 840-750=90 і тарифами С4s=0 (i=1,2,3). Тоді одержимо замкнену транспортну задачу, яка має розв'язок. Її математична модель має вигляд:

    хi,

    j 0, 1 i 4, 1 j 3.

    Пункти

    Пункти споживання

    Запаси

    постачання

    B1

    B2

    B3

    A1

    3

    5

    7

    270

    A2

    6

    9

    4

    180

    A3

    11

    8

    10

    300

    A4

    0

    0

    0

    90

    Потреби

    260

    280

    300

    840

    840

    За методом північно-західного кута знайдемо опорний план

    Пункти

    Пункти споживання

    Запаси

    постачання

    B1

    B2

    B3

    A1

    3

    260

    5

    10

    7

    270

    A2

    6

    9

    180

    4

    180

    A3

    11

    8

    90

    10

    210

    300

    A4

    0

    0

    0

    90

    90

    Потреби

    260

    280

    300

    840

    840

    За методом північно-західного кута опорний план має вигляд:

    .

    F=3*260+5*10+9*180+8*90+10*210+0*90=5270

    Перевіримо чи буде він оптимальним.

    Знаходимо потенціали для пунктів постачання

    Для тих клітинок, де, розв'яжемо систему рівнянь

    Знаходимо з системи:

    .

    Для тих клітинок, де, знайдемо числа

    Оскільки , то план Х1 не є оптимальним. Будуємо цикл перерахунку

    Пункти

    Пункти споживання

    Запаси

    постачання

    B1

    B2

    B3

    A1

    3

    5

    7

    0

    270

    260

    10

    A2

    6

    1

    9

    4

    7

    180

    -

    180

    +

    A3

    11

    -5

    8

    10

    300

    +

    90

    -

    210

    A4

    0

    -4

    0

    -2

    0

    90

    90

    Потреби

    260

    280

    300

    840

    840

    В результаті перерахунку отримаємо

    Пункти

    Пункти споживання

    Запаси

    постачання

    B1

    B2

    B3

    A1

    3

    260

    5

    10

    7

    270

    A2

    6

    9

    4

    180

    180

    A3

    11

    8

    270

    10

    30

    300

    A4

    0

    0

    0

    90

    90

    Потреби

    260

    280

    300

    840

    840

    Наступний опорний план

    F=3*260+5*10+9*180+8*90+10*210+0*90=4010

    Для тих клітинок, де, розв'яжемо систему рівнянь

    Знаходимо з системи:

    .

    Для тих клітинок, де, знайдемо числа

    Отже план є оптимальним F=4010

    Завдання 5. Задача квадратичного програмування

    Розв'язати задачу квадратичного програмування геометричним методом та аналітичним методом, використовуючи функцію Лагранжа і теорему Куна-Таккера:

    Розв'язання графічним методом

    ,

    Графік кола має центр в точці (-1, 4)

    X* (0 , 4); F*(X*)=-16

    Розв'язання аналітичним методом

    ,

    Складемо функцію Лагранжа:

    Система обмежень набуде вигляду:

    Перенесемо вільні члени вправо, і при необхідності домножимо на -1

    Зведемо систему обмежень до канонічного вигляду

    Введемо додаткові змінні для утворення штучного базису

    Розв'яжемо задачу лінійного програмування на знаходження мінімуму.

    Введемо додаткові прямі обмеження на змінні.

    ,

    Вектори з коефіцієнтів при невідомих:

    Розв'язуємо отриману задачу звичайним симплекс-методом

    I

    базис

    P0

    0

    0

    0

    0

    0

    0

    0

    0

    0

    0

    M

    M

    Px1

    Px2

    Py1

    Py2

    Py3

    Pu1

    Pu2

    Pv1

    Pv2

    Pv3

    Pz1

    Pz2

    1

    Pz1

    M

    2

    -2

    0

    -3

    1

    1

    -1

    0

    0

    0

    0

    1

    0

    2

    Pu2

    0

    8

    0

    2

    2

    1

    -1

    0

    1

    0

    0

    0

    0

    0

    3

    Pv1

    0

    18

    -3

    -2

    0

    0

    0

    0

    0

    1

    0

    0

    0

    0

    4

    Pv2

    0

    6

    -1

    1

    0

    0

    0

    0

    0

    0

    1

    0

    0

    0

    5

    Pz2

    M

    4

    1

    1

    0

    0

    0

    0

    0

    0

    0

    -1

    0

    1

    5

    -M

    M

    -3M

    M

    M

    -M

    0

    0

    0

    -M

    0

    0

    Обраний розв'язковий елемент (5,2)

    I

    базис

    P0

    0

    0

    0

    0

    0

    0

    0

    0

    0

    0

    M

    M

    Px1

    Px2

    Py1

    Py2

    Py3

    Pu1

    Pu2

    Pv1

    Pv2

    Pv3

    Pz1

    Pz2

    1

    Pz1

    M

    2

    -2

    0

    -3

    1

    1

    -1

    0

    0

    0

    0

    1

    0

    2

    Pu2

    0

    0

    -2

    0

    2

    1

    -1

    0

    1

    0

    0

    2

    0

    0

    3

    Pv1

    0

    26

    -1

    0

    0

    0

    0

    0

    0

    1

    0

    -2

    0

    0

    4

    Pv2

    0

    2

    -2

    0

    0

    0

    0

    0

    0

    0

    1

    1

    0

    0

    5

    Px2

    0

    4

    1

    1

    0

    0

    0

    0

    0

    0

    0

    -1

    0

    1

    5

    -2М

    0

    -3М

    М

    M

    0

    0

    0

    0

    0

    0

    Обраний розв'язковий елемент (2,4)

    I

    базис

    P0

    0

    0

    0

    0

    0

    0

    0

    0

    0

    0

    M

    M

    Px1

    Px2

    Py1

    Py2

    Py3

    Pu1

    Pu2

    Pv1

    Pv2

    Pv3

    Pz1

    Pz2

    1

    Pz1

    M

    2

    0

    0

    -5

    0

    2

    -1

    -1

    0

    0

    -2

    1

    2

    Py2

    0

    0

    -2

    0

    2

    1

    -1

    0

    1

    0

    0

    2

    0

    3

    Pv1

    0

    26

    -1

    0

    0

    0

    0

    0

    0

    1

    0

    -2

    0

    4

    Pv2

    0

    2

    -2

    0

    0

    0

    0

    0

    0

    0

    1

    1

    0

    5

    Px2

    0

    4

    1

    1

    0

    0

    0

    0

    0

    0

    0

    -1

    0

    5

    2M

    0

    0

    -5M

    0

    2M

    -M

    -M

    0

    0

    -2M

    0

    Обраний розв'язковий елемент (1,5)

    I

    базис

    P0

    0

    0

    0

    0

    0

    0

    0

    0

    0

    0

    M

    M

    Px1

    Px2

    Py1

    Py2

    Py3

    Pu1

    Pu2

    Pv1

    Pv2

    Pv3

    Pz1

    Pz2

    1

    Py3

    0

    1

    0

    0

    -5/2

    0

    1

    -1/2

    -1/2

    0

    0

    -1

    2

    Py2

    0

    1

    -2

    0

    -1/2

    1

    0

    -1/2

    -1/2

    0

    0

    1

    3

    Pv1

    0

    26

    -1

    0

    0

    0

    0

    0

    0

    1

    0

    -2

    4

    Pv2

    0

    2

    -2

    0

    0

    0

    0

    0

    0

    0

    1

    1

    5

    Px2

    0

    4

    1

    1

    0

    0

    0

    0

    0

    0

    0

    -1

    5

    0

    0

    0

    0

    0

    0

    0

    0

    0

    0

    0

    План отриманий в результаті розв'язування задачі симплекс-методом, не є оптимальним так як він не задовольняє умови:

    Отже перерахуємо симплекс-таблицю ще раз.

    Обраний розв'язковий елемент (2,7)

    I

    базис

    P0

    0

    0

    0

    0

    0

    0

    0

    0

    0

    0

    Px1

    Px2

    Py1

    Py2

    Py3

    Pu1

    Pu2

    Pv1

    Pv2

    Pv3

    1

    Py3

    0

    10

    0

    2

    -3

    1

    1

    -1

    0

    0

    0

    -2

    2

    Pu2

    0

    18

    0

    4

    -1

    2

    0

    -1

    1

    0

    0

    -2

    3

    Pv1

    0

    30

    0

    1

    0

    0

    0

    0

    0

    1

    0

    -3

    4

    Pv2

    0

    10

    0

    2

    0

    0

    0

    0

    0

    0

    1

    -1

    5

    Px2

    0

    4

    1

    1

    0

    0

    0

    0

    0

    0

    0

    -1

    5

    0

    0

    0

    0

    0

    0

    0

    0

    0

    0

    0

    Отриманий план оптимальний X* (0,4); F*(X*)=-16

    Список використаної літератури

    1. Карманов В. Г. Математическое программирование: Учеб. пособие. -- 5-е издание., стереотип. -- М.: ФИЗМАТЛИТ, 2001. -- 264 с.

    2. Моисеев Н. Н., Иванилов Ю. П., Столярова Е. М. Методы оптимизации --М.: Наука, 1978. -- 352 с.


© 2010 BANKS OF РЕФЕРАТ