Банк рефератов содержит более 364 тысяч рефератов, курсовых и дипломных работ, шпаргалок и докладов по различным дисциплинам: истории, психологии, экономике, менеджменту, философии, праву, экологии. А также изложения, сочинения по литературе, отчеты по практике, топики по английскому.
Полнотекстовый поиск
Всего работ:
364139
Теги названий
Разделы
Авиация и космонавтика (304)
Административное право (123)
Арбитражный процесс (23)
Архитектура (113)
Астрология (4)
Астрономия (4814)
Банковское дело (5227)
Безопасность жизнедеятельности (2616)
Биографии (3423)
Биология (4214)
Биология и химия (1518)
Биржевое дело (68)
Ботаника и сельское хоз-во (2836)
Бухгалтерский учет и аудит (8269)
Валютные отношения (50)
Ветеринария (50)
Военная кафедра (762)
ГДЗ (2)
География (5275)
Геодезия (30)
Геология (1222)
Геополитика (43)
Государство и право (20403)
Гражданское право и процесс (465)
Делопроизводство (19)
Деньги и кредит (108)
ЕГЭ (173)
Естествознание (96)
Журналистика (899)
ЗНО (54)
Зоология (34)
Издательское дело и полиграфия (476)
Инвестиции (106)
Иностранный язык (62791)
Информатика (3562)
Информатика, программирование (6444)
Исторические личности (2165)
История (21319)
История техники (766)
Кибернетика (64)
Коммуникации и связь (3145)
Компьютерные науки (60)
Косметология (17)
Краеведение и этнография (588)
Краткое содержание произведений (1000)
Криминалистика (106)
Криминология (48)
Криптология (3)
Кулинария (1167)
Культура и искусство (8485)
Культурология (537)
Литература : зарубежная (2044)
Литература и русский язык (11657)
Логика (532)
Логистика (21)
Маркетинг (7985)
Математика (3721)
Медицина, здоровье (10549)
Медицинские науки (88)
Международное публичное право (58)
Международное частное право (36)
Международные отношения (2257)
Менеджмент (12491)
Металлургия (91)
Москвоведение (797)
Музыка (1338)
Муниципальное право (24)
Налоги, налогообложение (214)
Наука и техника (1141)
Начертательная геометрия (3)
Оккультизм и уфология (8)
Остальные рефераты (21692)
Педагогика (7850)
Политология (3801)
Право (682)
Право, юриспруденция (2881)
Предпринимательство (475)
Прикладные науки (1)
Промышленность, производство (7100)
Психология (8692)
психология, педагогика (4121)
Радиоэлектроника (443)
Реклама (952)
Религия и мифология (2967)
Риторика (23)
Сексология (748)
Социология (4876)
Статистика (95)
Страхование (107)
Строительные науки (7)
Строительство (2004)
Схемотехника (15)
Таможенная система (663)
Теория государства и права (240)
Теория организации (39)
Теплотехника (25)
Технология (624)
Товароведение (16)
Транспорт (2652)
Трудовое право (136)
Туризм (90)
Уголовное право и процесс (406)
Управление (95)
Управленческие науки (24)
Физика (3462)
Физкультура и спорт (4482)
Философия (7216)
Финансовые науки (4592)
Финансы (5386)
Фотография (3)
Химия (2244)
Хозяйственное право (23)
Цифровые устройства (29)
Экологическое право (35)
Экология (4517)
Экономика (20644)
Экономико-математическое моделирование (666)
Экономическая география (119)
Экономическая теория (2573)
Этика (889)
Юриспруденция (288)
Языковедение (148)
Языкознание, филология (1140)

Контрольная работа: Розв`язання задач графічним методом, методом потенціалів, методом множників Лангранжа та симплек

Название: Розв`язання задач графічним методом, методом потенціалів, методом множників Лангранжа та симплек
Раздел: Рефераты по математике
Тип: контрольная работа Добавлен 08:35:08 14 апреля 2011 Похожие работы
Просмотров: 200 Комментариев: 20 Оценило: 2 человек Средний балл: 5 Оценка: неизвестно     Скачать

Контрольна робота

З дисциплiни:Математичне програмування

Варіант№5

Київ 2009 рiк.

Завдання 1. Скласти математичну модель задачі та розв'язати її графічним методом

На виробництво двох видів продукції використовується три групи устаткування. Необхідна кількість устаткування для випуску одиниці продукції та прибуток від реалізації одиниці продукції (у тис. грн.) зазначено в таблиці. Потрібно організувати випуск продукції так, щоб прибуток від її реалізації був найбільшим.

Група виробничого

устаткування

Кількість устаткування для випуску

одиниці продукції

Кількість

устаткування

в групі

Продукція І Продукція ІІ
А 2 3 12
В 1 2 8
С 4 0 16
Прибуток, тис. грн. 1 3

Рішення:

Позначимо через x1 і x2 кількість продукції І і ІІ. Тоді умови для необхідногоустаткування будуть описуватися наступними нерівностями:

2x1 + 3x2 ≤ 12

1x1 + 2x2 ≤ 8

4x1 + 0x2 ≤ 16

x1 , x2 ≥ 0

А умова найбільшого прибутку:

f = 1x1 + 3x2 → max


Для розв'язання задачі графічним методом замість нерівностей системи обмежень беремо відповідні рівняння граничних прямих і будуємо їх графіки:

Звертаючи увагу на півплощини, в яких виконуються відповідні нерівності, знаходимо спільну область, помічену сірим кольором. Стрілкою вказуємо вектор зростання цільової функції f, компоненти якого (1; 3) дорівнюють коефіцієнтам при x1 і x2 у виразі цієї функції.

Бачимо, що максимального значення функція f набуває в точці М, на перетині прямої 2x1 + 3x2 = 12 і вісі x2 . Підставляючи x1 = 0 в це рівняння, отримуємо:

2*0 + 3x2 = 12

x2 = 4

М = (x1 ; x2 ) = (0; 4)

Значення функції f в точці М:

fmax = 1*0+3*4 = 12


Відповідь:

Найбільший прибуток у розмірі 12 тис. грн. буде від реалізації 4 одиниць продукції ІІ без випуску продукції І.

Завдання 2. Для заданої ЗЛП побудувати двоїсту, розв'язати одну з пари двоїстих задач симплекс-методом і за її розв'язком знайти розв'язок іншої задачі

F = x1 + x2 → max

x1 - x2 ≥ -6
3x1 +4x2 ≤ 26
2x1 - x2 ≤ 10

x1 ≥ 0, x2 ≥ 0

Рішення.

Перепишемо ЗЛП, помноживши першу нерівність на -1:

F = x1 + x2 → max

-x1 + x2 ≤ 6

3x1 + 4x2 ≤ 26

2x1 - x2 ≤ 10

x1 ≥ 0, x2 ≥ 0

Двоїста задача записується у вигляді:

F* = 6y1 + 26y2 + 10y3 → min

-1y1 + 3y2 + 2y3 ≥ 1

1y1 + 4y2 - 1y3 ≥ 1

y1 ≥ 0, y2 ≥ 0, y3 ≥ 0

Зведемовихіднузадачудоканонічноїформи [5, с. 14]. Для цього добавимо невід'ємні величини x3 , x4 , x5 , щоб нерівності перетворити в рівняння:

F - x1 - x2 → max

-x1 + x2 + x3 = 6

3x1 + 4x2 + x4 = 26

2x1 - x2 + x5 = 10

x1 ≥ 0, x2 ≥ 0, x3 ≥ 0, x4 ≥ 0, x5 ≥ 0

Розв'яжемо дану задачу симплекс-методом [5, с. 18]. Заповнюємо симплекс-таблицю початковими значеннями, вибираємо стовпець (x1 ) з першим від'ємним значенням (-1) в останньому рядку, вибираємо рядок (x5 ) з найменшим значенням bi /xi (5) і виділяємо розв'язувальний елемент (2):

xб b x1 x2 x3 x4 x5 bi /xi
x3 6 -1 1 1 0 0
x4 26 3 4 0 1 0 26/3
x5 10 2 -1 0 0 1 5 (min)
Δ 0 -1 -1 0 0 0

Вводимо в базис x1 замість x5 і перераховуємо таблицю. Вибираємо стовпець (x2 ) з єдиним від'ємним значенням (-3/2) в останньому рядку, вибираємо рядок (x4 ) з найменшим значенням bi /xi (2) і виділяємо розв'язувальний елемент (11/2):

xб b x1 x2 x3 x4 x5 bi /xi
x3 11 0 1/2 1 0 1/2 22
x4 11 0 11/2 0 1 -3/2 2 (min)
x1 5 1 -1/2 0 0 1/2
Δ 5 0 -3/2 0 0 1/2

Вводимо в базис x2 замість x4 і перераховуємо таблицю:

xб b x1 x2 x3 x4 x5 bi /xi
x3 10 0 0 1 -1/11 7/11
x2 2 0 1 0 2/11 -3/11
x1 6 1 0 0 1/11 4/11
Δ 8 0 0 0 3/11 1/11

В останньому рядку не залишилося від'ємних величин, тому стовбець b містить рішення вихідної задачі — максимум функції F:

x1 = 6

x2 = 2

Fmax = 8

Запишемо рішення двоїстої задачі з останнього рядка останньої симплекс-таблиці:

y1 = 0

y2 = 3/11

y3 = 1/11

F* min = 8

Відповідь:

Вихідна задача: Fmax = F(6; 2) = 8

Двоїста задача: F* min = F* (0; 3/11; 1/11) = 8

Завдання 3. Розв'язати методом потенціалів транспортну задачу

ai \ bj 90 50 60 80
120 5 4 3 4
100 3 2 5 5
60 1 6 3 1

Рішення.

Підраховуємо загальні запаси постачальників: 120 + 100 + 60 = 280

Підраховуємо загальні потреби споживачів: 90 + 50 + 60 + 80 = 280

Дана модель закрита [5, с. 55], тому що загальні потреби споживачів дорівнюють загальним запасам постачальників.

Запишемо умову задачі у вигляді наступної таблиці:

В1 В2 В3 В4 Запаси
А1 5 4 3 4 120
А2 3 2 5 5 100
А3 1 6 3 1 60
Потреби 90 50 60 80

Для визначення опорного плану транспортної задачі застосуємо спочатку метод мінімального елемента [5, с. 50]. Для цього будемо послідовно вибирати клітинки з мінімальним тарифом і робити спробу максимально задовольнити вимоги споживачів і постачальників.

Перший мінімальний елемент (1) знаходяться в клітинці А­3 В­1 , тому записуємо в неї запас постачальника А­3 (60) і коректуємо колонки запасів та потреб:

В1 В2 В3 В4 Запаси
А1 120
А2 100
А3 60 0
Потреби 30 50 60 80

Наступні мінімальні елементи (2 та 3) знаходяться в клітинках А2 В2 , А1 В3 та А2 В1 , тому записуємо в них потреби споживачів В2 (50), В3 (60) та В1 (30) і коректуємо колонки запасів та потреб:


В1 В2 В3 В4 Запаси
А1 60 60
А2 30 50 20
А3 60 0
Потреби 0 0 0 80

Залишилися вільні клітинки А1 В4 та А2 В4 , тому записуємо в них запаси постачальників А1 (60) та А2 (20) і коректуємо колонки запасів та потреб:

В1 В2 В3 В4 Запаси
А1 60 60 0
А2 30 50 20 0
А3 60 0
Потреби 0 0 0 0

Підрахуємо вартість перевезення для отриманого опорного плану:

60*3 + 60*4 + 30*3 + 50*2 + 20*5 + 60*1 = 770

Для визначення оптимальності отриманого опорного плану застосуємо метод потенціалів [5, с. 51]. Для цього задамо нульовий потенціал першому рядку, а решту потенціалів визначимо враховуючи отримані клітинки:

В1 В2 В3 В4 потенц.
А1 3 4 0
А2 3 2 5 1
А3 1 1
потенц. 2 1 3 4

Визначаємо оцінки для вільних клітинок, знаходимо максимальну додатну оцінку (4) в клітинці А­3 В­4 і позначаємо для неї цикл [5, с. 51]:


В1 В2 В3 В4 потенц.
А1 -3 -3 0
А2 (+) -1 (-) 1
А3 (-) -4 1 4(+) 1
потенц. 2 1 3 4

В вершинах циклу зі знаком (-) вибираємо мінімальне значення (20) у клітинці А­2 В­4 опорного плану. Додаємо його до вершин циклу зі знаком (+) і віднімаємо його від вершин циклу зі знаком (-):

В1 В2 В3 В4 Запаси
А1 60 60 0
А2 50 50 0
А3 40 20 0
Потреби 0 0 0 0

При цьому вартість перевезення для цього поліпшеного опорного плану:

60*3 + 60*4 + 50*3 + 50*2 + 40*1 + 20*1 = 730

Для визначення оптимальності поліпшеного опорного плану знову застосуємо метод потенціалів — задамо нульовий потенціал першому рядку, а решту потенціалів визначимо враховуючи отримані клітинки:

В1 В2 В3 В4 потенц.
А1 3 4 0
А2 3 2 -1
А3 1 1 -3
потенц. 4 3 3 4

Визначаємо оцінки для вільних клітинок:

В1 В2 В3 В4 потенц.
А1 -1 -1 0
А2 -3 -2 -1
А3 -6 -3 -3
потенц. 4 3 3 4

Оскільки всі отримані оцінки не більші нуля, то останній опорний план є оптимальним [5, с. 51]. Отримуємо оптимальний план перевезення:

Маршрут Кількість Вартість
А­1 — В3 60 180
А­1 — В­4 60 240
А­2 — В­1 50 150
А­2 — В­2 50 100
А­3 — В­1 40 40
А­3 — В­4 20 20
Всього 730

Відповідь:

Вартість оптимального плану транспортної задачі дорівнює 730.

Завдання 4. Методом множників Лагранжа знайти умовні екстремуми функцій

f = x1 2 + x1 x2 + x2 2 - 3x1 - 6x2 за умови x1 + x2 = 3.

Рішення.

Перепишемо умову у вигляді c(x1 , x2 ) = 0:

x1 + x2 - 3 = 0

Тоді функція Лагранжа [5, с. 153]:


L(x1 , x2 , λ) = f(x1 , x2 ) + λ c(x1 , x2 )

L(x1 , x2 , λ) = x1 2 + x1 x2 + x2 2 - 3x1 - 6x2 + λ(x1 + x2 - 3)

УточціекстремумучастинніпохідніфункціїЛагранжадорівнюютьнулю [5, с. 154]:

∂L(x1 , x2 , λ) / ∂x1 = 2x1 + x2 - 3 + λ

∂L(x1 , x2 , λ) / ∂x2 = x1 + 2x2 - 6 + λ

Отримуємонаступнусистему:

2x1 + x2 - 3 + λ = 0

x1 + 2x2 - 6 + λ = 0

x1 + x2 - 3 = 0

Віднімаємодругерівняннясистемивідпершогоівизначаємоx2 :

x1 - x2 + 3 = 0

x2 = x1 + 3

Підставляємо отримане x2 в третє рівняння системи:

x1 = 0

x2 = x1 + 3 = 3

Отже точка (0; 3) — умовний екстремум функції f, який дорівнює:

f(0; 3) = 32 - 6*3 = -9

Розглянемо іншу довільну точку (3; 0), для якої виконується умова задачі. Значення функції для цієї точки:

f(3; 0) = 32 - 3*3 = 0

Оскільки f(0; 3) < f(3; 0), то знайдений умовний екстремум — це умовний мінімум.

Відповідь: Умовний мінімум функції f досягається в точці (0; 3) і дорівнює -9.


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

1. Вітлінський В.В., Наконечний С.І., Терещенко Т.О. Математичне програмування: Навчально-методичний посібник для самостійного вивчення дисципліни. — К.: КНЕУ, 2001. — 248 с.

2. Заварыкин В.М., Житомирский В.Г., Лапчик М.П. Численные методы: Учебное пособие для студентов. — М.: Просвещение, 1991. — 176 с.

3. Лавренчук В.П., Веренич І.І., Готинчан Т.І., Дронь В.С., Кондур О.С. Математичне програмування (методичний посібник для студентів економічних спеціальностей). — Чернівці: Рута, 1998. — 168 с.

4. Наконечний С.І., Савіна С.С. Математичне програмування: Навчальний посібник. — К.: КНЕУ, 2003. — 452 с.

5. Попов Ю.Д., Тюптя В.І., Шевченко В.І. Методи оптимізації. — К.: КНУ, 2003. — 215 с.

Оценить/Добавить комментарий
Имя
Оценка
Комментарии:
Срочная помощь учащимся в написании различных работ. Бесплатные корректировки! Круглосуточная поддержка! Узнай стоимость твоей работы на сайте 64362.ru
06:15:05 12 сентября 2021
Привет студентам) если возникают трудности с любой работой (от реферата и контрольных до диплома), можете обратиться на FAST-REFERAT.RU , я там обычно заказываю, все качественно и в срок) в любом случае попробуйте, за спрос денег не берут)
Olya15:13:29 01 сентября 2019
.
.15:13:29 01 сентября 2019
.
.15:13:28 01 сентября 2019
.
.15:13:27 01 сентября 2019

Смотреть все комментарии (20)
Работы, похожие на Контрольная работа: Розв`язання задач графічним методом, методом потенціалів, методом множників Лангранжа та симплек

Назад
Меню
Главная
Рефераты
Благодарности
Опрос
Станете ли вы заказывать работу за деньги, если не найдете ее в Интернете?

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



Результаты(285975)
Комментарии (4150)
Copyright © 2005-2021 BestReferat.ru support@bestreferat.ru реклама на сайте

Рейтинг@Mail.ru