Автор работы: Пользователь скрыл имя, 18 Декабря 2012 в 22:24, контрольная работа
Фірма для автомобільної промисловості виготовляє деталі двох типів А і В. Для їх виготовлення фірма має фонд робочого часу 4000 годин на тиждень. Для виготовлення однієї деталі типу А потрібно використати одну год., а типу В – 2 години. Потужність фірми дозволяє виготовити деталей типу А максимум 2250 од., а типу В - 1750 од. за тиждень. Кожна деталь типу А потребує 2 кг металевих стрижнів та 5 кг листового прокату, а для виготовлення деталі типу В потрібно 5 кг металевих стрижнів та 2 кг листового прокату.
Міністерство освіти і науки України
Східноєвропейський університет економіки та менеджменту
Канівська філія
Контрольна робота
з дисципліни «Математичне програмування».
Варіант 1.
Канів
2008 рік.
План
Розрахункова
частина:
Використана література
Розрахункова частина:
1. Форми постанови задач
Фірма
для автомобільної
Визначити обсяги випуску деталей кожного типу за тиждень, щоб максимізувати прибуток фірми, коли відомо, що деталь типу А дає прибуток ЗО у. о., а типу В - 40 у. о.
Створюємо математичну модель поставленої задачі:
Керованими змінними будуть обсяги випуску х1 - деталей типу А та хг - деталей типу В.
Цільовою функцією буде загальний дохід фірми
z = (30 х1 + 40 х2) у.о -> мах
До системи обмежень повинні входити обмеження на виробничий процес (використаний ресурс не повинен перевищувати наявного на тиждень функціонування фірми)
1 х1 + 2х2 < 4000 год. - ресурсу фонду робочого часу;
2х1 + 5х2 < 10000 кг. ресурсу металевих стрижнів;
5х1 + 2х2 < 10000 кг. ресурсу листового прокату.
Далі, в системі обмежень повинні бути враховані потужності фірми з випуску деталей обох типів
х1 <2250од., та х2<1750од., а також обмеження, що враховують угоди:
х1 + х2>1500од.
х1 > 600 од. та умови невід'ємності керованих змінних х1>0, х2>0.
Створену математичну модель можна записати у вигляді:
z = ЗОх1 + 40х2 → мах
| |
х1 + 2х2 < 4000, |
0) |
2х1 + 5х2 < 10000, |
(2) |
5х1 +2х2 < 10000, |
(3) |
х 1 < 2250, |
(4) |
х2 < 1750, |
(5) |
х1 > 600, |
(6) |
х 2 > 0. |
(7) |
Розв'яжемо дану ЗЛП графічним методом. На декартову систему координат нанесемо граничні прямі, що визначають область О допустимих розв'язків:
х, = 4000;
(1) хІ+2х2= 4000.
х1 = 0 =» х2 =2000; х2 = 0 => х2 = 2000;
х2 = 0 => х2 = 5000;
2х,+5х2 =10000.
(6)х2 = 600.
Виділяємо півплощини, що визначають область, і знаходимо їх перетин, (див. рис. 5). Одержимо область Ώ. - це чотирикутник АВСД.
5000
З рис. 1.1 видно, що z = z (Д).
2. Графічний метод розв’язування задач.
Графічним методом знайти оптимальні розв'язки ЗЛП, якщо
2 = х1 + х2 —> мах (міn)
х1 + х2 ≤ 6, (2)
х1 ≥ 0, х2 ≥ 0 (3)
Розв'язування.
На декартову систему координат наносимо область допустимих розв'язків М та вектор нормалі цільової функції N = {1;1}. Рівняння граничних прямих:
1) 5х1 -2х2 =7. Точки, через які проходить пряма:
Х1 =0=> х2 =- 7 / 2; х2=0=>х1= -7 / 5 .
Х| + х2 = 6; х, = 0 => х2 = 6; х2 = 0 => х1 = 6.
Рис. 1.1. ілюструє, що мін z = z (0; 0) = 0 + 0 = 0.
Максимальне значення є весь відрізок [ВС], бо пряма 3) паралельна прямій, що зображує цільову функцію. Знайдемо координати точки В, як розв’язки системи:
- х, + х2 = 5 (пряма 2)) х 1 + х2 = 6 (пряма 3))
2 х2 = 11 => х1 = - 11 / 2 => х2 = 1 /2. Мах z = z (11/2; 1/2) = 1/2 + 11/2 =5.
3. Симплекс метод розв’язування (ЗЛП)
Знайти оптимальні розв'язки ЗЛП симплекс-методом
2 = х1+ х2 -> мах(мін)
5 х1 - 2х2 < 7, - х, - х2 5,
х, + х2 < 6, х, > 0; х2 > 0
Розв'язування
Записуємо постановку ЗЛП у стандартному вигляді:
У1 = -5х1 + 2х2 + 7 > 0,
у2 = X1 - х2 + 5 > 0,
З=- х1 -Х2+6>0,
х 1> 0, х2 > 0 Записуємо симплекс-таблицю ЗЛП.
Таблиця 3.1
- х1 |
- х2 |
1 | |
У1 = |
5 |
-2 |
7 |
У2 = |
- 1 |
(X) |
5 |
У3 = |
1 |
1 |
6 |
z = |
- 1 |
-1 |
0 |
У табл. 3.1 знайдено опорний розв'язок координатами (0; 0) (стовпець вільних містить лише додатні числа), а в z - рядку усі коефіцієнти від'ємні. Звідси мін z = 2 (0; 0) = 0. Знаходимо максимум. Вибираємо за розв'язувальний другий стовпець табл. 21.
Знаходимо всі невід'ємні відношення вільних елементів до відповідних елементів розв'язувального стовпця і беремо серед них найменше: Розв'язувальним елементом буде елемент а22 =1, обведений колом в табл. 3.1.
Крок МЖВ з цим елементом призводить до табл. 3.2:
Таблиця 3.2.
-х1 |
-х2 |
1 | |
У1 = |
3 |
2 |
17 |
У2 = |
-1 |
1 |
5 |
У3 = |
2 |
-1 |
1 |
Z = |
-2 |
1 |
5 |
Крок МЖВ із розвязувальним елементом призводить до таблиці 3.3.
Таблиця 3.4.
- у3 |
- у2 |
1 | |
У1 = |
31 / 2 | ||
У2 = |
11 / 2 | ||
У3 = |
1 / 2 | ||
Z = |
1 |
0 |
6 |
Із таблиці 3.3. маємо : мах = Z (1/2; 11/2) = 6.
4. Спряжена задача ЗЛП
Для вихідної (прямої) задачі лінійного програмування
z = 20х1 - 50х2 + 50х3 + 5х4 (мах),
8х1 - х2 + 3х3 - 2х4 - 2х4 ≤ 15,
2х1 + 7х2 - х3 + 5х4 ≥ 31,
3х1 – х2 + 5х3 + 3х4 = 24,
х J ≥ 0, J = 1,4.
побудувати спряжену задачу та знайти розв'язок прямої та спряженої задачі.
Розв'язування:
Обмеження задачі подамо у вигляді
У1 = - 8х, +х2 - Зх3 + 2х4 +15 > 0,
у2 =2х, +7х2 -х3 +5х4 — 31 >0,
0 = - Зх1 + х2 - 5х3 - Зх4 + 24,
х J > 0, J = 1,4.
У цьому випадку ми маємо мішану систему обмежень. Для побудови спряженої задачі потрібно ввести змінні щ > 0, и2 > 0 і змінну м3, на яку умова невід'ємності не накладається. Тобто остання змінна буде вільною. У цьому випадку система обмежень спряженої задачі буде містити чотири нерівності, а цільова функція має вигляд:
W = 15и1 – 31и2 + 24и3
і їй потрібно надати мінімального значення:
V1 = 8и1- 2и2 + Зи3 - 20 > 0,
V 2 = - и1 – 7и2 - и3 + 50 > 0,
V3 = Зи, + и2 + 5и3 - 50 > 0,
V4 = - 2и1 - 5и2 + 3и3, > 0,
и1 ≥ 0, и2 > 0.
Поєднаємо умови прямої та спряженої задач у таблиці:
Таблиця 4.1.
|
|
у2 = |
У3 = |
У4 = |
W = | ||
-х, |
-х2 |
-х3 |
-х4 |
1 | ||
И1 |
У1 = |
8 |
-1 |
3 |
-2 |
15 |
И2 |
У 2 = |
-2 |
-7 |
1 |
-5 |
-31 |
И3 |
0 = |
3 |
- 1 |
5 |
3 |
24 |
1 |
z = |
-20 |
50 |
-50 |
0 |
0 |
Розв'язок знаходимо за допомогою, симплекс-методу. починаємо із виключення 0 - рядка. З розв'язувальним елементом 0 здійснюємо крок МЖВ. Одержуємо таблицю:
Таблиця 4.2.
У1 = |
И3 = |
v3 = |
v4 = |
W = | ||
-X1 |
0 |
- хз |
-х4 |
1 | ||
И1 |
У1 = |
5 |
-1 |
-2 |
-5 |
-9 |
И2 |
У 2 = |
-23 |
_ у |
-34 |
-26 |
-199 |
V 2 |
Х2 = |
- 3 |
-1 |
-5 |
-3 |
-24 |
1 |
z = |
130 |
50 |
200 |
145 |
1200 |