Міністерствоосвіти і науки України
Черкаськийнаціональнийуніверситет імені Богдана Хмельницького
Факультет інформаційнихтехнологій і
біомедичноїкібернетики
РОЗРАХУНКОВА РОБОТА
зкурсу „Математичне моделювання економічних систем”
студента4-го курсу спеціальності
«інтелектуальнісистеми прийняття рішень»
ВаляєваОлександра В’ячеславовича
Черкаси – 2006 р.
Зміст
Зміст
Завдання 1. Задача лінійного програмування
Завдання 2. Задача цілочислового програмування
Завдання 3. Задача дробово-лінійного програмування
Завдання 4. Транспортна задача
Завдання 5. Задача квадратичного програмування
Список використаної літератури
/>/>Завдання 1. Задача лінійного програмування
Для заданої задачі лінійного програмування побудувати двоїстузадачу. Знайти розв’язок прямої задачі геометричним методом і симплекс-методом.Знайти розв’язок двоїстої задачі, використовуючи результати розв’язуванняпрямої задачі симплекс-методом:
3. />,
/>
/>
Розв′язання геометричним методом
Побудуємо прямі, рівняння яких одержуються внаслідокзаміни в обмеженнях знаків нерівностей на знаки рівностей.
I: />
/> 6
/> 9
II: />
/> -6
/> 6
III: />
/> 4
/> 4
Визначимо півплощини, що задовольняють нашим нерівностям.
Умовам невід’ємності /> та /> відповідає перша чверть.
Заштрихуємо спільну частину площини, що задовольняє всім нерівностям.
Побудуємо вектор нормалі />.
Максимального значення функція набуває в точці перетину прямих I та II.
Знайдемо координати цієї точки.
Приведемосистему до канонічного вигляду
/>
/>
/>
/>
/> />
/> /> /> /> /> /> /> /> /> /> /> /> /> /> /> />
X2
X*
X1
Відповідь: /> />
Розв′язаннясимплекс-методом
Приведемо систему рівнянь до канонічного вигляду
/>
/>
/> /> /> /> /> />
/> /> x(0)=(0,0,18,6,0,4)
Цільова функція />
Побудуємо симплекс-таблицюI базис
Cб
P0 2 3 -M
P1
P2
P3
P4
P5
P6 1
P3 18 3 2 1 2
P4 6 -1 1 1 3
P6 -M 4 1 1 -1 1 4 -2 -3 5 -4 -1 -1 1
Отриманий план неоптимальний
Обраний ключовийелемент (3,2)I базис
Cб
P0 2 3 -M
P1
P2
P3
P4
P5
P6 1
P3 10 1 1 2 -2 2
P4 2 -2 1 1 -1 3
P2 3 4 1 1 -1 -1 4 12 1 -3 -3 5 -1
Отриманий план неоптимальний
Обраний ключовийелемент (2,5)I базис
Cб
P0 2 3 -M
P1
P2
P3
P4
P5
P6 1
P3 6 5 1 -2 2
P5 2 -2 1 1 -1 3
P2 3 6 -1 1 1 4 18 -5 3 5 -1
Отриманий план неоптимальний
Обраний ключовийелемент (1,1)I базис
Cб
P0 2 3 -M
P1
P2
P3
P4
P5
P6 1
P1 2 6/5 1 1/5 -2/5 2
P5 22/5 2/5 1/5 1 -1 3
P2 3 36/5 1 1/5 3/5 4 24 1 1 5 1
План оптимальний
Розв’язок: X*(/>,/>) F*=24;
Розв’язок двоїстоїзадач
Побудуємо двоїстуфункцію
3. />,
Система обмежень
/>
Скористаємось теоремою
Якщо задача лінійного програмування в канонічній формі (7)-(9) маєоптимальний план />, то /> є оптимальним планом двоїстої задачі
/>, />,/>
/>/>/>
Розв’язок:
/>/>
Fmin*=9,6;
/>Завдання 2.Задача цілочислового програмування
Для задачі із завдання 1, як для задачі цілочислового програмування,знайти розв’язки геометричним методом і методом Гоморі.
Розв′язаннягеометричним методом
/>,
/>
/>
/> />
/>
/> />
Відповідь: /> />
Розв′язанняметодом Гоморі
Наведемо останню симплекс-таблицюI базис
Cб
P0 2 3 -M
P1
P2
P3
P4
P5
P6 1
P1 2 6/5 1 1/5 -2/5 2
P5 22/5 2/5 1/5 1 -1 3
P2 3 36/5 1 1/5 3/5 4 24 1 1 5 1
Побудуємо нерівність Гоморі за першим аргументом.
/>
/>
/>
/>
/>
/>
/>
/>
/>I базис
Cб
P0 2 3
P1
P2
P3
P4
P5
P7 1
P1 2 6/5 1 1/5 -2/5 2
P5 22/5 2/5 1/5 1 3
P2 3 36/5 1 1/5 3/5 4
P7 -1/5 -1/5 -3/5 1 5 24 1 1
Обраний розв’язковий елемент (4,4)I базис
Cб
P0 2 3
P1
P2
P3
P4
P5
P7 1
P1 2 1 1 -1 2
P5 4 11/5 1 3
P2 3 7 1 4
P4 2 1 3 1 5 14 2
Отриманий планявляється оптимальним і цілочисельним.
Розв’язок: 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 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
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 270 260 10 A2 6 1 9 4 7 180 - 180 + A3 11 -5 8 10 300 + 90 - 210 A4 -4 -2 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
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 M M
Px1
Px2
Py1
Py2
Py3
Pu1
Pu2
Pv1
Pv2
Pv3
Pz1
Pz2 1
Pz1 M 2 -2 -3 1 1 -1 1 2
Pu2 8 2 2 1 -1 1 3
Pv1 18 -3 -2 1 4
Pv2 6 -1 1 1 5
Pz2 M 4 1 1 -1 1 5 -M M -3M M M -M -M
Обраний розв’язковий елемент (5,2)I базис
Cб
P0 M M
Px1
Px2
Py1
Py2
Py3
Pu1
Pu2
Pv1
Pv2
Pv3
Pz1
Pz2 1
Pz1 M 2 -2 -3 1 1 -1 1 2
Pu2 -2 2 1 -1 1 2 3
Pv1 26 -1 1 -2 4
Pv2 2 -2 1 1 5
Px2 4 1 1 -1 1 5 2М -2М -3М М M -М
Обраний розв’язковий елемент (2,4)I базис
Cб
P0 M M
Px1
Px2
Py1
Py2
Py3
Pu1
Pu2
Pv1
Pv2
Pv3
Pz1
Pz2 1
Pz1 M 2 -5 2 -1 -1 -2 1 2
Py2 -2 2 1 -1 1 2 3
Pv1 26 -1 1 -2 4
Pv2 2 -2 1 1 5
Px2 4 1 1 -1 5 2M -5M 2M -M -M -2M
Обраний розв’язковий елемент (1,5)I базис
Cб
P0 M M
Px1
Px2
Py1
Py2
Py3
Pu1
Pu2
Pv1
Pv2
Pv3
Pz1
Pz2 1
Py3 1 -5/2 1 -1/2 -1/2 -1 2
Py2 1 -2 -1/2 1 -1/2 -1/2 1 3
Pv1 26 -1 1 -2 4
Pv2 2 -2 1 1 5
Px2 4 1 1 -1 5
План отриманий в результаті розв’язування задачі симплекс-методом, не єоптимальним так як він не задовольняє умови:
/>
Отже перерахуємо симплекс-таблицю ще раз.
Обраний розв’язковий елемент (2,7)I базис
Cб
P0
Px1
Px2
Py1
Py2
Py3
Pu1
Pu2
Pv1
Pv2
Pv3 1
Py3 10 2 -3 1 1 -1 -2 2
Pu2 18 4 -1 2 -1 1 -2 3
Pv1 30 1 1 -3 4
Pv2 10 2 1 -1 5
Px2 4 1 1 -1 5
Отриманий план оптимальний X*(0,4); F*(X*)=-16
/>Списоквикористаної літератури
1. КармановВ. Г. Математическое программирование: Учеб. пособие. — 5-е издание.,стереотип. — М.: ФИЗМАТЛИТ, 2001. — 264 с.
2. МоисеевН. Н., Иванилов Ю. П., Столярова Е. М. Методы оптимизации —М.: Наука, 1978. — 352 с.