F7 IO ODZ

МІНІСТЕРСТВО ОСВІТИ І НАУКИ, МОЛОДІ ТА СПОРТУ УКРАЇНИ

СУМСЬКИЙ ДЕРЖАВНИЙ УНІВЕРСИТЕТ

ФАКУЛЬТЕТ ЕЛЕКТРОНІКИ ТА ІНФОРМАЦІЙНИХ ТЕХНОЛОГІЙ

ОБОВ’ЯЗКОВЕ ДОМАШНЄ ЗАВДАННЯ

з курсу:

«Дослідження операцій»

Варіант F-7

Підготував

студент гр. ФЕ-01 Педченко Богдан Олександрович

Перевірила Щокотова Ірина Володимирівна

Суми – 2012

Вариант F-7. Мебельная фабрика собирает из готовых комплектующих два вида кухонных шкафов обычные и дорогие. Обычный шкаф покрывается белой краской, а дорогой лаком. Покраска и покрытие лаком производится на одном производственном покрасочном участке. Сборочная линия фабрики ежедневно может собрать не более 220 обычных шкафов и 160 дорогих. Лакирование одного дорогого шкафа требует в 2 раза больше времени, чем покраска одного простого шкафа. Если покрасочный участок занят только лакированием дорогих шкафов, то за день здесь можно подготовить 190 таких шкафов. Фабрика оценивает доход от обычных и дорогих кухонных шкафов $90 и $140 соответственно.

Сформулируйте задачу линейного программирования и составьте оптимальное ежедневное расписание работы покрасочного участка.

Пусть х₁ – количество обычных шкафов, а х₂ - количество дорогих шкафов, собираемых сборочной линией фабрики ежедневно.

По условию задачи, х₁≤220, а х₂≤160.

Если покрасочный участок будет занят только лакированных шкафов (х₁=0), то их количество х₂ будет равняться 190. Это можно отобразить уравнением: х₂=-kх₁+190, где k – некий коэффициент, который мы находим из дальнейшего условия – лакирование одного дорогого шкафа требует в 2 раза больше времени, чем покраска одного простого. То есть х₂≡(1/2) х₁. Знак минус перед коэффициентом k означает обратную зависимость между х₁ и х₂. Итак, полученное уравнение имеет вид:

х₂=-(1/2)х₁+190.

Исходя из данных условия, что цена простого шкафа равна $90, а дорогого – $140, составим уравнение дохода фабрики:

Z=90x₁+140x₂ .

Построим графики уравнений: х₂=-(1/2)х₁+190 – график I и

Z=90x₁+140x₂ – график II, где z возьмем например $10000.

Учитывая, что по условию задачи х₁≤220, а х₂≤160, и то, что количество шкафов не может быть отрицательным, делаем вывод, что область решений находится в прямоугольнике OACE, который отсекает от прямой І отрезок BD, который удовлетворяет всю систему ограничений задачи.

Определим графически максимальное значение целевой функции Z=90x₁+140x₂ при следующих условиях–ограничениях:

x₁≤220

x₂≤160

x₁+2x₂≤380

Максимальный доход фабрики будет соответствовать угловой точке области ABDEO. Найдем максимальный доход в точках B и D:

Z_B=90*60+140*160=27800

Z_D=90*220+140*80=31000

Где х₁ и х₂ мы нашли из уравнения x₁+2x₂=380, принимая, что в точке B х₂=160, а в точке D х₁=220.

Как видим доход в точке D будет больше, чем в точке B.

Ответ: Если фабрика будет производить 220 дешевых и 80 дорогих шкафов, доход будет максимальным ($31000).

Чтобы решить прямую задачу линейного программирования симплексным методом, с использованием симплексной таблицы,

определим максимальное значение целевой функции z = 90x₁+140x₂ при следующих условиях–ограничениях:

x₁≤220

x₂≤160

x₁+2x₂≤380

Вводим базисные переменные S1, S2, S3 и преобразуем неравенства в равенства:

x₁ + S1 = 220

x₂ + S2 = 160

x₁ + 2x₂ + 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 выбираем максимальный по модулю элемент. В качестве ведущего выберем столбец, соответствующий переменной x₂, так как это наибольший коэффициент по модулю. Находим минимальное соотношение свободного коэффициента к соответствующему элементу ведущего столбца. 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. Проверка критерия оптимальности. Среди значений индексной строки нет отрицательных. Поэтому эта таблица определяет оптимальный план задачи.

Ответ: оптимальный план можно записать так:

x₁ = 220 – количество дешевых шкафов

x₂ = 80 – количество дорогих шкафов

z = 90*220 + 140*80 = 31000 – общий ежедневный доход в $.

Вывод: результаты, полученные на первом этапе (графический метод) и на втором (симплекс метод), совпадают.