ИРКУТСКИЙ НАЦИОНАЛЬНЫЙ ИССЛЕДОВАТЕЛЬСКИЙ ТЕХНИЧЕСКИЙ УНИВЕРСИТЕТ
Заочно-вечерний
наименование факультета
Кафедра вычислительной техники
наименование кафедры
Контрольная работа по дисциплине _______ Исследование операций_______
наименование учебной дисциплины
Разработал студент ЭВМбз-12-1 ____________ О.В. Самсонюк
шифр группы подпись И.О. Фамилия
Руководитель ___________ О.С. Бучнев
подпись И.О. Фамилия
Иркутск 2016 г.
Постановка задачи
Задача 11
Мебельная фабрика выпускает два вида изделий: шкафы и тумбочки, расходуя для их производства ресурсы четырех типов: ДСП, фанеру, стекло, крепежные изделия. Нормы расхода ресурсов на одно изделие каждого типа и суточные запасы, которыми располагает фабрика, приведены в табл.1.
| Виды ресурсов | Объем ресурсов | Нормы расхода на одно изделие | |
| Шкафы | Тумбочки | ||
| ДСП | |||
| Фанера | |||
| Стекло | |||
| Крепежные изделия |
Определить оптимальную программу выпуска из условия максимума прибыли, если прибыль от реализации одного шкафа 2 у.е., а тумбочки 3 у.е.
Построение математической модели
2x1+ 3x2 →max
ОДЗ:
1) x1 + 2x2≤18
2) 2x1 + x2≤21
3) x1 + x2≤22
4) x1 + x2≤23 – не используем так как, 3)ОДЗ лежит внутри области 4)
Решение задачи графическим методом
Построим графики согласно ОДЗ
X1,X2≥0
Теперь выделим область, удовлетворяющую всем ограничениям (ABCD):
и построим нашу функцию, приравняв её к 0:
2x1+ 3x2 =0
Будем двигать эту прямую параллельным образом до последнего касания обозначенной области.
Так как точка C получена в результате пересечения прямых (1) и (2), то ее координаты удовлетворяют уравнениям этих прямых:
x1+2x2=18
2x1+x2=21
Решив систему уравнений, получим: x1 = 8, x2 = 5
Теперь найдем максимум:
2*8+3*5=31
Решение задачи симплекс методом
Вводим базисные переменные:
2x1+ 3x2+0s1+0s2+0s3=А0
ОДЗ:
1) x1 + 2x2+s1≤18
2) 2x1 + x2+s2≤21
3) x1 + x2+s3≤22
А0=0+2x1+ 3x2
S1=18-x1-2x2
S2 = 21-2x1-x2
S3 = 22-x1-x2
В выражении А0 присутствуют положительные коэффициенты
Выберем новую базисную переменную Х2 (max коэффициент)
Определим новую свободную переменную
Min (18/2, 21/1, 22/1)=9 (S1)
X2= 9*-0,5x1*-0,5S1
Новая система уравнений:
А0=0+2x1+ 3(9*-0,5x1*-0,5S1)
S2 = 21-2x1-(9*-0,5x1*-0,5S1)
S3 = 22-x1-(9*-0,5x1*-0,5S1)
А0=27+0,5x1-1,5S1
X2= 9-0,5x1-0,5S1
S2 = 12-1,5x1+0,5S1
S3 = 13-0,5x1+0,5S1
В выражении А0 присутствуют положительные коэффициенты
Выберем новую базисную переменную Х1 (max коэффициент)
Определим новую свободную переменную
Min (9/0,5, 12/1,5, 13/0,5)=8 (S2)
Х1=8+1/3S1-2/3S2
Новая система уравнений:
А0=27+0,5(8+1/3S1-2/3S2)-1,5S1
X2= 9-0,5(8+1/3S1-2/3S2)-0,5S1
Х1=8+1/3S1-2/3S2
S3 = 13-0,5(8+1/3S1-2/3S2)+0,5S1
А0=31-4/3S1-1/3S2
X2= 5-2/3S1+1/3S2
Х1=8+1/3S1-2/3S2
S3 = 9+1/3S1+1/3S2
В выражении А0 отсутствуют положительные коэффициенты
Небазисные элементы S приравняем к 0:
А0=31
X2= 5
Х1=8
Max=31
Решение задачи использованием Симплекс-таблиц
Вводим базисные переменные:
2x1+ 3x2+0s1+0s2+0s3→max
ОДЗ:
1) x1 + 2x2+s1≤18
2) 2x1 + x2+s2≤21
3) x1 + x2+s3≤22
Построим таблицу:
| Ci | |||||||
| Bx | A0 | X1 | X2 | S1 | S2 | S3 | |
| S1 | |||||||
| S2 | |||||||
| S3 | |||||||
| ∆ | -2 | -3 |
в индексной строке находятся отрицательные коэффициенты.
Итерация №1
В качестве ведущего выберем столбец, соответствующий переменной x2, так как это наименьшее чисто в индексной строке.
Выбор ведущей строки:
Min (18/2, 21/1, 22/1)=9 (первая строка)
Построим таблицу2:
Строка X2= ведущая строка /разрешающий элемент(2)
НЭ = СЭ - (А*В)/РЭ
НЭ-новый элемент
СЭ-старый элемент
РЭ-разрещающий элемент
A-элемент ведущей строки в этом столбце
B-элемент ведущего столбца в этой строке
| Ci | |||||||
| Bx | A0 | X1 | X2 | S1 | S2 | S3 | |
| X2 | 1/2 | 1/2 | |||||
| S2 | 3/2 | 1/2 | |||||
| S3 | 1/2 | 1/2 | |||||
| ∆ | -1/2 | 3/2 |
в индексной строке находятся отрицательныq коэффициент.
Итерация №2
Ведущий столбец – Х1
Ведущая строка – min(18,8,26,)=8 S2
Построим таблицу3:
| Ci | |||||||
| Bx | A0 | X1 | X2 | S1 | S2 | S3 | |
| X2 | 2/3 | -1/3 | |||||
| X1 | 1/3 | 3/2 | |||||
| S3 | -1/3 | -1/3 | |||||
| ∆ | 4/3 | 1/3 |
В индексной строке все коэффициенты положительные
X1=8
X2=5
Max=31