Автор: Пользователь скрыл имя, 02 Мая 2012 в 22:11, контрольная работа
Задание 1
Для выпуска двух видов продукции требуются затраты сырья, рабочего времени и оборудования. Исходные данные в таблице:
Найдите оптимальный план выпуска продукции по критерию «максимум прибыли».
Определите остатки каждого вида сырья.
1) Составьте математическую модель задачи.
2) Решите задачу симплекс-методом.
3) Решите задачу графическим методом. Покажите соответствие опорных решений, полученных при решении симплекс-методом, и угловых точек – вершин допустимой области.
4) Найдите решение двойственной задачи, используя теоремы двойственности.
7x1+4x2<=28
2x1+3x2>=9
x1+2x2=9
x1>=0, x2>=0
Приведем задачу к канонической форме:
7x1+4x2+x3=28
2x1+3x2-x4=9
x1+2x2=9
x1>=0, x2>=0
F(x)=2x1+x2 (max)
В третьем уравнении нет базисных неизвестных. Введём искусственную базисную переменную Y1 и заполним первую симплекс-таблицу.
7x1+4x2+x3=28
2x1+3x2-x4=9
x1+2x2+у1=9
x1>=0, x2>=0
F(x)=2x1+x2-М*у1 (max)
| 2 | 1 | 0 | 0 | -М |
| ||
Базис | С | План | X1 | X2 | X3 | X4 | У1 | Q |
X3 | 0 | 28 | 7 | 4 | 1 | 0 | 0 | 7 |
X4 | 0 | 9 | 2 | 3 | 0 | -1 | 0 | 3 |
У1 | -М | 9 | 1 | 2 | 0 | 0 | 1 | 4,5 |
F=М2 |
| ∆ | -М-2 | -2М-1 | 0 | 0 | 0 |
|
Разрешающий элемент в ячейке (2;3) - 4. Выводим из базиса переменную У1 и вводим х2.
| 3 | 1 | 0 | 0 |
| ||
Базис | С | План | X1 | X2 | X3 | X4 | Q |
X3 | 0 | 10 | 5 | 0 | 1 | 0 | 2 |
X4 | 0 | 4,5 | -0,5 | 0 | 0 | 1 | - |
Х2 | 1 | 4,5 | 0,5 | 1 | 0 | 0 | 9 |
F=4,5 |
| ∆ | -2,5 | 0 | 0 | 0 |
|
Разрешающий элемент в ячейке (1;3) - 5. Выводим из базиса переменную Х3 и вводим Х1.
| 3 | 1 | 0 | 0 |
| ||
Базис | С | План | X1 | X2 | X3 | X4 | Q |
X1 | 2 | 2 | 0 | 0 | 0,2 | 0 |
|
X4 | 0 | 5,5 | 0 | 0 | 0,1 | 1 |
|
Х2 | 1 | 3,5 | 1 | 1 | -0,1 | 0 |
|
F=7,5 |
| ∆ | 0 | 0 | 0,3 | 0 |
|
Т.к. среди оценок ∆ нет отрицательных, то полученный план (2; 3,5; 0; 5,5) оптимальный.
F(x1,x2)=2*2+1*3,5=7,5 (max).
2) составим двойственную задачу
Выписываем расширенную матрицу из коэффициентов при переменных системы ограничений, столбца свободных членов и дополнительной строки из коэффициентов целевой функции.
Транспонируем матрицу А
По транспонированной матрице, используя свойства, составляем двойственную задачу.
7y1 +2 y2 + y3 >=2
4 y1 + 3y2+2 y3 >=1
yi >=0, i=1,2,3.
g(y1,у2,у3)=28y1+9y2+9y3
Задание 3
Доски длиной L=3,8, имеющиеся в достаточном количестве, следует распилить на заготовки двух видов: длиной l1=1,5 и длиной l2=1,1. Заготовок первого вида должно быть получено не менее n1=70 штук, заготовок второго вида – не менее n2 =67 штук. Каждая доска может быть распилена на указанные заготовки несколькими способами. Определить, сколько досок надо распилить каждым способом, чтобы необходимое количество заготовок было получено из наименьшего числа досок.
1) Составьте математическую модель в виде задачи линейного программирования, указав предварительно все возможные способы распила доски на заготовки нужной длины.
2) Решите задачу методом отсечений (Гомори).
Решение:
Пусть x1 – количество заготовок, распиленных первым способом
х2 – количество заготовок, распиленных 2-ым способом,
х3 – количество заготовок, распиленных 3-м способом
Способ распила | Длины досок | |
l1=1.5 | l2=1.1 | |
1 | 1 | 2 |
2 | 2 | 0 |
3 | 0 | 3 |
Количество заготовок | 70 | 67 |
L(x)=x1+x2 +x3 (min)
x1+2x2=70
2x1+3x3=67
x1>=0, x2>=0,x3>=0
Вместо задачи на минимум будем решать задачу на максимум, заменив знаки перед коэффициентами в целевой функции. Приведем задачу к канонической форме:
F(x)=-x1-x2 -x3 (max)
1/2x1+x2=65
2/3x1+x3=67/3
x1>=0, x2>=0,x3>=0
| -1 | -1 | -1 |
| ||
Базис | С | План | X1 | X2 | X3 | Q |
X2 | -1 | 35 | 1/2 | 1 | 0 | 70 |
X3 | -1 | 67/3 | 2/3 | 0 | 1 | 33,5 |
F=0 |
| ∆ | -1/6 | 0 | 0 |
|