F7 IO ODZ
.docxМІНІСТЕРСТВО ОСВІТИ І НАУКИ, МОЛОДІ ТА СПОРТУ УКРАЇНИ
СУМСЬКИЙ ДЕРЖАВНИЙ УНІВЕРСИТЕТ
ФАКУЛЬТЕТ ЕЛЕКТРОНІКИ ТА ІНФОРМАЦІЙНИХ ТЕХНОЛОГІЙ
ОБОВ’ЯЗКОВЕ ДОМАШНЄ ЗАВДАННЯ
з курсу:
«Дослідження операцій»
Варіант F-7
Підготував
студент гр. ФЕ-01 Педченко Богдан Олександрович
Перевірила Щокотова Ірина Володимирівна
Суми – 2012
Вариант F-7. Мебельная фабрика собирает из готовых комплектующих два вида кухонных шкафов обычные и дорогие. Обычный шкаф покрывается белой краской, а дорогой лаком. Покраска и покрытие лаком производится на одном производственном покрасочном участке. Сборочная линия фабрики ежедневно может собрать не более 220 обычных шкафов и 160 дорогих. Лакирование одного дорогого шкафа требует в 2 раза больше времени, чем покраска одного простого шкафа. Если покрасочный участок занят только лакированием дорогих шкафов, то за день здесь можно подготовить 190 таких шкафов. Фабрика оценивает доход от обычных и дорогих кухонных шкафов $90 и $140 соответственно.
Сформулируйте задачу линейного программирования и составьте оптимальное ежедневное расписание работы покрасочного участка.
Пусть х1 – количество обычных шкафов, а х2 - количество дорогих шкафов, собираемых сборочной линией фабрики ежедневно.
По условию задачи, х1≤220, а х2≤160.
Если покрасочный участок будет занят только лакированных шкафов (х1=0), то их количество х2 будет равняться 190. Это можно отобразить уравнением: х2=-kх1+190, где k – некий коэффициент, который мы находим из дальнейшего условия – лакирование одного дорогого шкафа требует в 2 раза больше времени, чем покраска одного простого. То есть х2≡(1/2) х1. Знак минус перед коэффициентом k означает обратную зависимость между х1 и х2. Итак, полученное уравнение имеет вид:
х2=-(1/2)х1+190.
Исходя из данных условия, что цена простого шкафа равна $90, а дорогого – $140, составим уравнение дохода фабрики:
Z=90x1+140x2 .
Построим графики уравнений: х2=-(1/2)х1+190 – график I и
Z=90x1+140x2 – график II, где z возьмем например $10000.
Учитывая, что по условию задачи х1≤220, а х2≤160, и то, что количество шкафов не может быть отрицательным, делаем вывод, что область решений находится в прямоугольнике OACE, который отсекает от прямой І отрезок BD, который удовлетворяет всю систему ограничений задачи.
Определим графически максимальное значение целевой функции Z=90x1+140x2 при следующих условиях–ограничениях:
x1≤220
x2≤160
x1+2x2≤380
Максимальный доход фабрики будет соответствовать угловой точке области ABDEO. Найдем максимальный доход в точках B и D:
ZB=90*60+140*160=27800
ZD=90*220+140*80=31000
Где х1 и х2 мы нашли из уравнения x1+2x2=380, принимая, что в точке B х2=160, а в точке D х1=220.
Как видим доход в точке D будет больше, чем в точке B.
Ответ: Если фабрика будет производить 220 дешевых и 80 дорогих шкафов, доход будет максимальным ($31000).
Чтобы решить прямую задачу линейного программирования симплексным методом, с использованием симплексной таблицы,
определим максимальное значение целевой функции z = 90x1+140x2 при следующих условиях–ограничениях:
x1≤220
x2≤160
x1+2x2≤380
Вводим базисные переменные S1, S2, S3 и преобразуем неравенства в равенства:
x1 + S1 = 220
x2 + S2 = 160
x1 + 2x2 + S3 = 380
Составляем таблицу:
Базис |
x1 |
x2 |
S1 |
S2 |
S3 |
Значение |
S1 |
1 |
0 |
1 |
0 |
0 |
220 |
S2 |
0 |
1 |
0 |
1 |
0 |
160 |
S3 |
1 |
2 |
0 |
0 |
1 |
380 |
z |
-90 |
-140 |
0 |
0 |
0 |
0 |
1. Проверка критерия оптимальности. Текущий опорный план не оптимален, так как в индексной строке находятся отрицательные коэффициенты.
Определяем ведущий столбец и строку. В индексной строке z выбираем максимальный по модулю элемент. В качестве ведущего выберем столбец, соответствующий переменной x2, так как это наибольший коэффициент по модулю. Находим минимальное соотношение свободного коэффициента к соответствующему элементу ведущего столбца. 160<190, следовательно, 2-ая строка является ведущей.
Пересчет симплекс-таблицы. Формируем следующую часть симплексной таблицы.
Производим расчеты и после преобразований получаем новую таблицу.
x1 |
x2 |
x3 |
x4 |
x5 |
Значение |
|
|
|
|
|
|
0 / 1 = 0 |
1 / 1 = 1 |
0 / 1 = 0 |
1 / 1 = 1 |
0 / 1 = 0 |
160 / 1 = 160 |
|
|
|
|
|
|
|
|
|
|
|
|
Базис |
x1 |
x2 |
S1 |
S2 |
S3 |
Значение |
S1 |
1 |
0 |
1 |
0 |
0 |
220 |
x2 |
0 |
1 |
0 |
1 |
0 |
160 |
S3 |
1 |
0 |
0 |
-2 |
1 |
60 |
z |
-90 |
0 |
0 |
140 |
0 |
22400 |
2. Проверка критерия оптимальности. Текущий опорный план не оптимален, так как в индексной строке находятся отрицательные коэффициенты.
Определяем ведущий столбец и строку аналогично предыдущему пункту.
Пересчет симплекс-таблицы. Формируем следующую часть симплексной таблицы.
Производим расчеты и после преобразований получаем новую таблицу.
x1 |
x2 |
x3 |
x4 |
x5 |
Значение |
|
|
|
|
|
|
|
|
|
|
|
|
1 / 1 = 1 |
0 / 1 = 0 |
0 / 1 = 0 |
-2 / 1 = -2 |
1 / 1 = 1 |
60 / 1 = 60 |
|
|
|
|
|
|
Базис |
x1 |
x2 |
S1 |
S2 |
S3 |
Значение |
S1 |
0 |
0 |
1 |
2 |
-1 |
160 |
x2 |
0 |
1 |
0 |
1 |
0 |
160 |
x1 |
1 |
0 |
0 |
-2 |
1 |
60 |
z |
0 |
0 |
0 |
-40 |
90 |
27800 |
3. Проверка критерия оптимальности. Текущий опорный план не оптимален, так как в индексной строке находятся отрицательные коэффициенты.
Определяем ведущий столбец и строку аналогично предыдущему пункту.
Пересчет симплекс-таблицы. Формируем следующую часть симплексной таблицы.
Производим расчеты и после преобразований получаем новую таблицу.
x1 |
x2 |
x3 |
x4 |
x5 |
Значение |
0 / 2 = 0 |
0 / 2 = 0 |
1 / 2 = 0.5 |
2 / 2 = 1 |
-1 / 2 = -0.5 |
160 / 2 = 80 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Базис |
x1 |
x2 |
S1 |
S2 |
S3 |
Значение |
S2 |
0 |
0 |
0.5 |
1 |
-0.5 |
80 |
x2 |
0 |
1 |
-0.5 |
0 |
0.5 |
80 |
x1 |
1 |
0 |
1 |
0 |
0 |
220 |
z |
0 |
0 |
20 |
0 |
70 |
31000 |
4. Проверка критерия оптимальности. Среди значений индексной строки нет отрицательных. Поэтому эта таблица определяет оптимальный план задачи.
Ответ: оптимальный план можно записать так:
x1 = 220 – количество дешевых шкафов
x2 = 80 – количество дорогих шкафов
z = 90*220 + 140*80 = 31000 – общий ежедневный доход в $.
Вывод: результаты, полученные на первом этапе (графический метод) и на втором (симплекс метод), совпадают.