Реферат по предмету "Информатика, программирование"


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

Міністерствоосвіти і науки України
Черкаськийнаціональнийуніверситет імені Богдана Хмельницького
 
Факультет інформаційнихтехнологій і
біомедичноїкібернетики
РОЗРАХУНКОВА РОБОТА
зкурсу „Математичне моделювання економічних систем”

студента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 базис

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 базис

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 базис

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 базис

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 базис

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 базис

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 базис

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 базис

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 базис

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 базис

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 базис

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 базис

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


Не сдавайте скачаную работу преподавателю!
Данный реферат Вы можете использовать для подготовки курсовых проектов.

Поделись с друзьями, за репост + 100 мильонов к студенческой карме :

Пишем реферат самостоятельно:
! Как писать рефераты
Практические рекомендации по написанию студенческих рефератов.
! План реферата Краткий список разделов, отражающий структура и порядок работы над будующим рефератом.
! Введение реферата Вводная часть работы, в которой отражается цель и обозначается список задач.
! Заключение реферата В заключении подводятся итоги, описывается была ли достигнута поставленная цель, каковы результаты.
! Оформление рефератов Методические рекомендации по грамотному оформлению работы по ГОСТ.

Читайте также:
Виды рефератов Какими бывают рефераты по своему назначению и структуре.

Сейчас смотрят :

Реферат Черепно-мозговые нервы 123 пары
Реферат Изучение реакции гибридов кукурузы на сроки посева
Реферат Особенности экономики России
Реферат Hard Times By Charles Dickens Essay Research
Реферат Постановление приговора
Реферат Активно быстрыми темпами увеличиваться сырьевой сектор экономики, который вскоре (в семидесятые годы) занял главенствующее положение в народном хозяйстве страны
Реферат Искусство второй половины Нового царства (14 - 2 вв. до н.э.)
Реферат Наближене обчислення визначених інтегралів, що не беруться через елементарні функції (Укр.)
Реферат Аспекти діяльності міського дитячого кардіоревматологічного центру
Реферат The Enlightened Machine Essay Research Paper Brain
Реферат Issn 1857-1336 universitatea de stat din moldova moldova state university
Реферат Использование занимательных материалов для развития познавательных интересов учащихся на уроках физики
Реферат Сущность комплекса маркетинга и особенности его разработки для ОАО "Свiтанак"
Реферат Контроль результатов деятельности как главный элемент управления персоналом
Реферат Болезнь Дауна.Болезнь Шерешевского-Тернера. Болезнь Клайнфельтера