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

Задача лінійного програмування. Розв’язання задачі геометричним методом. Приведення системи рівнянь до канонічного вигляду. Розв’язання симплекс-методом. Розв’язок двоїстої задачі. Задача цілочислового програмування і дробово-лінійного програм.

Рубрика Программирование, компьютеры и кибернетика
Вид контрольная работа
Язык украинский
Дата добавления 04.06.2009
Размер файла 385,2 K

Отправить свою хорошую работу в базу знаний просто. Используйте форму, расположенную ниже

Студенты, аспиранты, молодые ученые, использующие базу знаний в своей учебе и работе, будут вам очень благодарны.

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

    базис

    Cб

    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

    базис

    Cб

    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

    базис

    Cб

    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

    базис

    Cб

    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

    базис

    Cб

    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

    базис

    Cб

    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

    базис

    Cб

    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

    базис

    Cб

    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

    базис

    Cб

    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

    базис

    Cб

    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

    базис

    Cб

    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

    базис

    Cб

    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 с.


Подобные документы

  • Застосування симплекс-методу для розв’язання оптимізаційних задач лінійного програмування, що містять три змінні. Функції ітераційної обчислювальної процедури, що виконують приведення до зручного для розв’язання оптимального вигляду ЗЛП за кілька кроків.

    курсовая работа [359,5 K], добавлен 18.09.2013

  • Використання мови програмуванння Java при виконанні "задачі лінійного програмування": її лексична структура і типи даних. Методи розв’язання задачі. Особливості логічної структури програми, побудова її зручного інтерфейсу за допомогою симплекс методу.

    курсовая работа [437,9 K], добавлен 24.01.2011

  • Лінійне програмування як один з найбільш популярних апаратів математичної теорії оптимального управління рішень. Опис існуючих методів розв’язку задач лінійного програмування. Завдання, основні принципи, алгоритми і головна мета лінійного програмування.

    курсовая работа [363,8 K], добавлен 03.12.2009

  • Розв’язок багатокритеріальної задачі лінійного програмування з отриманням компромісного рішення (для задач з кількома функціями мети) за допомогою теоретико-ігрового підходу. Матриця мір неоптимальності та рядок функції мети. Модуль опису класу.

    курсовая работа [588,8 K], добавлен 15.05.2011

  • Теоретичні основи та приклади економічних задач лінійного програмування. Розробка математичної моделі задачі (запис цільової функції і системи обмежень) і програмного забезпечення її вирішення за допомогою "Пошуку рішень" в Excel симплекс-методом.

    курсовая работа [993,9 K], добавлен 10.12.2010

  • Загальні відомості та геометричний зміст розв'язання задачі Коші. Використання методу Ейлера для розв'язання звичайних диференціальних рівнянь першого порядку. Розробка блок-схеми та реалізація алгоритму в середовищі програмування Borland Delphi 7.0.

    курсовая работа [398,1 K], добавлен 14.10.2012

  • Початковий опорний план, перехід від одного до іншого. Оптимальний розв’язок, його головні критерії. Знаходження опорного плану задачі, складання симплексної таблиці. Приклад оформлення першої та другої таблиці для розв’язку задач лінійного програмування.

    лекция [479,7 K], добавлен 10.10.2013

Работы в архивах красиво оформлены согласно требованиям ВУЗов и содержат рисунки, диаграммы, формулы и т.д.
PPT, PPTX и PDF-файлы представлены только в архивах.
Рекомендуем скачать работу.