Контрольная работа
Задание 1
Решение задач линейного программирования графическим методом
Цель задания: приобрести практические навыки решения задач линейного программирования графическим методом.
Индивидуальное задание
Найти максимум и минимум линейной формы графическим методом по исходным данным задачи ЛП (таблица 1).
Таблица 1
|
Номер варианта |
Целевая функция |
Ограничения задачи линейного программирования |
|
|
6 |
|
|
|
Решение задачи
Построим область L допустимых решений. Заменим в каждом неравенстве задачи знак неравенства на знак равенства. Получим уравнения прямых:
x1+4x2=8, 2x1-x2=4, x1+x2-=1,x1=0,x2=0.
Область L определяется как общая часть полуплоскостей, соответствующих неравенствам ограничений (рисунок 1).
Рисунок 1. Графическое решение задачи ЛП
В данной задаче она составляет многоугольник ABCD. Для нахождения экстремума функции Z=-2x1+4x2 , строим разрешающую прямую, приравнивая линейную форму нулю:Z=0. Строим градиент целевой функции C(2;4).
Минимальное значение функция принимает в точке D(4,5;0,7) , а максимальное в точке B.
Анализ решения задачи линейного программирования
В результате решения задачи линейного программирования были получены минимум и максимум рассматриваемой функции, вследствие того, что область ограничений представляет собой замкнутый многоугольник, если бы фигура области ограничений была не замкнута, функция могла бы не иметь одного или обоих экстремумов в заданной области.
Задание 2
Решение задач ЛП симплексным методом с использованием симплекс-таблиц
Цель задания: закрепить теоретические сведения и приобрести практические навыки решения задач ЛП симплекс-методом.
Индивидуальное задание
Найти максимум линейной формы
Z=c1x1+c2x2
при условиях:
Данные представлены в таблице 2.
|
Номер варианта |
A11 |
A12 |
A21 |
A22 |
A31 |
A32 |
B1 |
B2 |
B3 |
C1 |
C2 |
|
|
6 |
4 |
1 |
3 |
6 |
8 |
7 |
43 |
74 |
76 |
7 |
4 |
|
Приведем задачу ЛП к каноническому виду:
-Z= -Z = -7x1 -4x2
при ограничениях
x3, x4, x5 -- дополнительные переменные.
Во втором уравнении дополнительная переменная введена с коэффициентом -1 и уравнение умножено на -1.
Постановка задачи в виде матрицы системы ограничений
Решение задачи ЛП с составленными симплекс-таблицами
Единичные векторы A3, A4, A5 образуют базис трехмерного пространства (m=3). Решать эту задачу алгоритмом симплекс-метода можно, поскольку переменные x3, x4, x5 входят с коэффициентом +1 соответственно в первое, второе и третье ограничения. Таким образом, x3, x4, x5 - базисные переменные, а остальные небазисные. Полагая небазисные переменные в ограничениях равными нулю, получим исходное допустимое базисное решение:
X0=(0,0,43,-74,76).
Заполняем исходную симплекс-таблицу (таблица 2)
Таблица 2. Нулевая симплекс-таблица
|
i |
Бx |
Сб |
A0 |
-7 |
-4 |
0 |
0 |
0 |
T |
|
|
A1 |
A2 |
A3 |
A4 |
A5 |
|
|||||
|
1 |
A3 |
0 |
43 |
4 |
1 |
1 |
0 |
0 |
|
|
|
2 |
A4 |
0 |
74 |
-3 |
-6 |
0 |
1 |
0 |
||
|
3 |
A5 |
0 |
76 |
-8 |
7 |
0 |
0 |
1 |
||
|
4 |
|
0 |
7 |
4 |
0 |
0 |
0 |
|||
Так как среди разностей есть положительные, то X0 не является оптимальным решением. Строим новое базисное решение.
.
Выводим из базиса вектор A3,так как
.
Разрешающий элемент таблицы x12 выделим кругом, а разрешающий столбец и строку стрелками.
Таблица 3. Первая симплекс-таблица
|
i |
Бx |
Cб |
A0 |
-7 |
-4 |
0 |
0 |
0 |
T |
|
|
A1 |
A2 |
A3 |
A4 |
A5 |
|
|||||
|
1 |
A1 |
-7 |
|
1 |
|
|
0 |
0 |
||
|
2 |
A4 |
0 |
|
0 |
|
|
1 |
0 |
||
|
3 |
A5 |
0 |
162 |
0 |
9 |
2 |
0 |
1 |
||
|
4 |
|
0 |
|
|
0 |
0 |
||||
Так как среди разностей есть положительные, то оптимальное решение не получено. Строим новое базисное решение.
.
Выводим из базиса вектор A4,так как
.
Таблица 4. Вторая симплекс-таблица
|
i |
Бx |
Cб |
A0 |
-7 |
-4 |
0 |
0 |
0 |
T |
|
|
A1 |
A2 |
A3 |
A4 |
A5 |
|
|||||
|
1 |
A2 |
-4 |
43 |
4 |
1 |
4 |
0 |
0 |
||
|
2 |
A4 |
0 |
736 |
21 |
0 |
|
1 |
0 |
||
|
3 |
A5 |
0 |
-225 |
-36 |
0 |
-34 |
0 |
1 |
||
|
4 |
|
-9 |
0 |
|
0 |
0 |
||||
Так как все разности во второй таблице (таблица 4) неположительны: , т получено оптимальное решение:
min(-Z)= -225.
Тогда max(Z)= -min(-Z)= 225
Анализ оптимального плана.
Использование переменной x1 нецелесообразно.
Задание 3
Моделирование и решение задач ЛП на ЭВМ
Цель задания: приобрести практические навыки моделирования задач ЛП и их решения симплекс-методом с использованием прикладной программы SIMC.
Индивидуальное задание
Предприятие может работать по 5-ти технологическим процессам, причем кол-во единиц выпускаемой продукции по разным ТП за ед. времени соответственно равны 300, 260, 320, 400, 450 шт. затраты производственных факторов в гривнах при работе по разным ТП в течение 1 ед. времени и располагаемые ресурсы этих факторов в табл.5.
Найти программу максимального выпуска продукции.
Таблица 5.
|
факторы |
Способ производства |
Ресурсы, грн |
|||||
|
1 |
2 |
3 |
4 |
5 |
|||
|
Сырье |
12 |
15 |
10 |
12 |
11 |
1300 |
|
|
Эл.энергия |
0,2 |
0,1 |
0,2 |
0,25 |
0,3 |
30 |
|
|
Зарплата |
3 |
4 |
5 |
4 |
2 |
400 |
|
|
Накладные расходы |
6 |
5 |
4 |
6 |
4 |
800 |
|
Математическая интерпретация задачи
Исходные массивы, записанные в виде, пригодном для решения задачи по программе SIMC
5
4
12.000 15.000 10.000 12.000 11.000 < 1300.000
0.200 0.100 0.200 0.250 0.300 < 30.000
3.000 4.000 5.000 4.000 2.000 < 400.000
6.000 5.000 4.000 6.000 4.000 < 800.000
300.000 260.000 320.000 400.000 450.000
Распечатка ЭВМ в результатом решения
ИТЕРАЦИЯ N=1 РЕШЕНИЕ НАЙДЕНО !!!
ТЕКУЩАЯ СИМПЛЕКС-ТАБЛИЦА ЗАДАЧА НЕ ВЫРОЖДЕНА
Бx Cб Po 1 2 3 4 5
6 0.000 1300.000 12.000 15.000 10.000 12.000 11.000
7 0.000 30.000 0.200 0.100 0.200 0.250 0.300
8 0.000 400.000 3.000 4.000 5.000 4.000 2.000
9 0.000 800.000 6.000 5.000 4.000 6.000 4.000
0.000 300.000 260.000 320.000 400.000 450.000
КОД ОШИБКИ=0
ОПТИМАЛЬНОЕ ЗНАЧЕНИЕ БАЗИС-ВЕКТОРА И РЕШЕНИЕ
ОПТИМУМ ЦЕЛЕВОЙ ФУНКЦИИ = 0.0000
ИТЕРАЦИЯ N=1 ПРОДОЛЖЕНИЕ РЕШЕНИЯ ТЕКУЩАЯ СИМПЛЕКС-ТАБЛИЦА ЗАДАЧА НЕ ВЫРОЖДЕНА
Бx Cб Po 1 2 3 4 5
6 0.000 1300.000 12.000 15.000 10.000 12.000 11.000
7 0.000 30.000 0.200 0.100 0.200 0.250 0.300
8 0.000 400.000 3.000 4.000 5.000 4.000 2.000
9 0.000 800.000 6.000 5.000 4.000 6.000 4.000
0.000 -300.000 -260.000 -320.000 -400.000 -450.000
В БАЗИС ВВОДИТСЯ 5 СТОЛБЕЦ
ИЗ БАЗИСА ВЫВОДИТСЯ 7 СТОЛБЕЦ
ИТЕРАЦИЯ N=2 ПРОДОЛЖЕНИЕ РЕШЕНИЯ ТЕКУЩАЯ СИМПЛЕКС-ТАБЛИЦА ЗАДАЧА НЕ ВЫРОЖДЕНА
Бx Cб Po 1 2 3 4 7
6 0.000 200.000 4.667 11.333 2.667 2.833 -36.667
5 450.000 100.000 0.667 0.333 0.667 0.833 3.333
8 0.000 200.000 1.667 3.333 3.667 2.333 -6.667
9 0.000 400.000 3.333 3.667 1.333 2.667 -13.333
45000.000 -0.000 -110.000 -20.000 -25.000 1500.000
В БАЗИС ВВОДИТСЯ 2 СТОЛБЕЦ
ИЗ БАЗИСА ВЫВОДИТСЯ 6 СТОЛБЕЦ
ИТЕРАЦИЯ N=3 ПРОДОЛЖЕНИЕ РЕШЕНИЯ ТЕКУЩАЯ СИМПЛЕКС-ТАБЛИЦА ЗАДАЧА НЕ ВЫРОЖДЕНА
Бx Cб Po 1 3 4 6 7
2 260.000 17.647 0.412 0.235 0.250 0.088 -3.235
5 450.000 94.118 0.529 0.588 0.750 -0.029 4.412
8 0.000 141.176 0.294 2.882 1.500 -0.294 4.118
9 0.000 335.294 1.824 0.471 1.750 -0.324 -1.471
46941.176 45.294 5.882 2.500 9.706 1144.118
КОД ОШИБКИ=0
ОПТИМАЛЬНОЕ ЗНАЧЕНИЕ БАЗИС-ВЕКТОРА И РЕШЕНИЕ
X2=17.6471
X5=94.1176
ОПТИМУМ ЦЕЛЕВОЙ ФУНКЦИИ = 46941.1765
РЕШЕНИЕ НАЙДЕНО !!!
Оптимальный план. Экономическая интерпретация оптимального решения. В соответствии с полученным результатом выпуск продукции по 1,3 и 4 технологическим процессам нецелесообразен.
Задание 4
Моделирование транспортных задач и их решение методом потенциалов
Цель задания: приобрести практические навыки моделирования и решения транспортной задачи ЛП методом потенциалов.
Индивидуальное задание
Составить оптимальное распределение трех видов механизмов на четырех участках работ, обеспечивающих минимальную себестоимость выполнения всей работы. Количество единиц механизмов, потребности участков в механизмах и себестоимость выполнения единицы работы каждым механизмом на соответствующем участке приведены в таблице 6.
Таблица 6. 06 вариант транспортной задачи
|
Вид механизма |
Себестоимость выполнения единицы работы механизма ,гр. |
Количество единиц ai механизмов |
||||
|
B1 |
B2 |
B3 |
B4 |
|
||
|
A1 |
11 |
4 |
3 |
1 |
15 |
|
|
A2 |
6 |
8 |
9 |
7 |
10 |
|
|
A3 |
4 |
8 |
4 |
2 |
35 |
|
|
Потребности bj участков в механизмах |
25 |
20 |
10 |
5 |
||
Математическая формулировка транспортной задачи
Пусть xij - количество единиц работы, выполненной механизмом вида ai, на участке работы bj.Требуется определить план распределения механизмов, минимизирующий себестоимость выполнения всей работы:
при ограничениях:
1) ; - все механизмы должны быть задействованы;
2); - все участки должны быть загружены;
3) ; - количество единиц работы не может быть отрицательным
Условие разрешимости задачи выполняется:
25+20+10+5=15+10+35; 60=60.
Исходный опорный план, составленный по методу северо-западного угла
Таблица 7
|
I |
|
ai |
||||
|
B1 |
B2 |
B3 |
B4 |
|
||
|
A1 |
11 |
4 15 |
3 |
1 |
15 |
|
|
A2 |
6 5 |
8 5 |
9 |
7 |
10 |
|
|
A3 |
4 20 |
8 |
4 10 |
2 5 |
35 |
|
|
bj |
25 |
20 |
10 |
5 |
|
|
Решение транспортной задачи методом потенциалов
Итак, видно что в число занятых клеток следует ввести клетку (2,1).
Получим новый улучшенный план - таблица 8.
Таблица 8
|
I |
|
ai |
||||
|
B1 |
B2 |
B3 |
B4 |
|
||
|
A1 |
11 |
4 15 |
3 |
1 |
15 |
|
|
A2 |
6 5 |
8 5 |
9 |
7 |
10 |
|
|
A3 |
4 20 |
8 |
4 10 |
5 5 |
35 |
|
|
bj |
25 |
20 |
10 |
5 |
|
|
Введём в число занятых клетку (1,4) . Получим новый улучшенный план - Таблица 9.
Таблица 9
|
I |
|
ai |
||||
|
B1 |
B2 |
B3 |
B4 |
|
||
|
A1 |
11 |
4 10 |
3 5 |
1 |
15 |
|
|
A2 |
6 |
8 10 |
9 |
7 |
10 |
|
|
A3 |
4 25 |
8 |
4 5 |
2 5 |
35 |
|
|
bj |
25 |
20 |
10 |
5 |
|
|
Так как, - то данный план является оптимальным и значение себестоимости по данному плану.
x12=15; x-21=5; x22=5; x-31=20;x33=10; x-34=5.
Z=15*4+5*6+5*8+20*4+10*4+5*2=260.
Анализ оптимального плана
Данный оптимальный план показывает, как нужно распределить механизмы по участкам для получения минимальной себестоимости выполненной работы.
Задание 5
Решение транспортной задачи на ЭВМ
Цель задания: приобрести практические навыки решения транспортной задачи на ЭВМ с использованием прикладной программы TRAN2.
Индивидуальное задание:
Составить оптимальное распределение трех видов механизмов на четырех участках работ, обеспечивающих минимальную себестоимость выполнения всей работы. Количество единиц механизмов, потребности участков в механизмах и себестоимость выполнения единицы работы каждым механизмом на соответствующем участке приведены в таблице 6.
Таблица 10. 06 вариант транспортной задачи
|
Вид механизма |
Себестоимость выполнения единицы работы механизма ,гр. |
Количество единиц ai механизмов |
||||
|
B1 |
B2 |
B3 |
B4 |
|
||
|
A1 |
11 |
4 |
3 |
1 |
15 |
|
|
A2 |
6 |
8 |
9 |
7 |
10 |
|
|
A3 |
4 |
8 |
4 |
2 |
35 |
|
|
Потребности bj участков в механизмах |
25 |
20 |
10 |
5 |
||
Исходные массивы для решения транспортной задачи по программе TRAN2
Распечатка с ЭВМ с результатом решения
Оптимальный план транспортной задачи
x12=15; x-21=5; x22=5; x31=20;x33=10; x-34=5.
Z=15*4+5*6+5*8+20*4+10*4+5*2=260.
Анализ результатов и выводы
Решение транспортной задачи на ЭВМ автоматизирует работу по вычислению решений транспортных задач и на тестируемом входном условие получается за 3 итерации, как и при ручном вычислении.
Задание 6
Решение многоэтапных задач методом динамического программирования
Цель задания: приобрести практические навыки решения многоэтапных задач методом динамического программирования.
Индивидуальное задание.
В таблице 11 приведены значения gi(x) возможного прироста продукции на четырех предприятиях в зависимости от выделенной на реконструкцию и модернизацию производства суммы x.
Распределить между предприятиями имеющиеся 100 тыс. гр., чтобы общий прирост f4(100) выпуска продукции был максимальным. Для упрощения вычислений значения x принимать кратными 20 тыс. гр.
Таблица 11
|
Предприятие |
Прирост выпуска продукции, тыс. гр. |
Средства c, тыс. гр. |
Номер варианта |
|||||
|
20 |
40 |
60 |
80 |
100 |
||||
|
1 |
G1(x) |
11 |
21 |
40 |
54 |
62 |
6 |
|
|
2 |
G2(x) |
13 |
20 |
42 |
45 |
61 |
||
|
3 |
G3(x) |
12 |
22 |
34 |
55 |
60 |
||
|
4 |
G4(x) |
10 |
27 |
33 |
57 |
69 |
||
Функциональное уравнение Беллмана для рассматриваемой задачи
f1(x)=max[g1(x)]=g1(x) - для первого предприятия;
- для остальных предприятий.
Решение задачи оптимального распределения средств между предприятиями методом динамического программирования
Таблица 12
|
Средства с, тыс. гр. |
Предприятие |
||||
|
1 |
2 |
3 |
4 |
||
|
G1(x) |
G2(x) |
G3(x) |
G4(x) |
||
|
20 |
11 |
13 |
12 |
10 |
|
|
40 |
21 |
20 |
22 |
27 |
|
|
60 |
40 |
42 |
34 |
33 |
|
|
80 |
54 |
45 |
55 |
57 |
|
|
100 |
62 |
62 |
60 |
69 |
|
Таблица 13
|
X1*(c) |
20 |
40 |
60 |
80 |
100 |
|
|
F1(c) |
11 |
21 |
40 |
54 |
62 |
|
Таблица 14
|
x С |
0 |
20 |
40 |
60 |
80 |
100 |
F2(c) |
X2*(c) |
|
|
20 |
0+13 |
12+0 |
13 |
0 |
|||||
|
40 |
0+24 |
12+13 |
22+0 |
25 |
20 |
||||
|
60 |
0+42 |
12+24 |
22+13 |
34+0 |
42 |
0 |
|||
|
80 |
0+45 |
12+42 |
22+24 |
34+13 |
55+0 |
55 |
80 |
||
|
100 |
0+67 |
12+45 |
22+42 |
34+24 |
55+3 |
60+0 |
68 |
80 |
|
Таблица 15
|
x С |
0 |
20 |
40 |
60 |
80 |
100 |
F3(c) |
X3*(c) |
|
|
20 |
0+13 |
10+0 |
13 |
0 |
|||||
|
40 |
0+29 |
10+13 |
27+0 |
27 |
40 |
||||
|
60 |
0+42 |
10+25 |
27+13 |
33+0 |
42 |
0 |
|||
|
80 |
0+55 |
10+42 |
27+25 |
33+13 |
57+0 |
57 |
80 |
||
|
100 |
0+68 |
10+55 |
27+42 |
33+25 |
52+13 |
69+0 |
69 |
40 |
|
Таблица 16
|
С |
X1*(c) |
F1(c) |
X2*(c) |
F2(c) |
X3*(c) |
F3(c) |
X4*(c) |
F4(c) |
|
|
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
|
|
20 |
20 |
11 |
20 |
13 |
0 |
13 |
0 |
13 |
|
|
40 |
40 |
21 |
20 |
24 |
20 |
25 |
40 |
27 |
|
|
60 |
60 |
40 |
60 |
42 |
0 |
42 |
0 |
42 |
|
|
80 |
80 |
54 |
80 |
45 |
80 |
55 |
80 |
|
| Контрольная работа | Концепция информатизации Российской Федерации |
| Контрольная работа | Причины агрессивного поведения. Методы работы с агрессивными детьми |
| Контрольная работа | Алгоритм выбора и реализации предпринимательской идеи |
| Контрольная работа | Системы управления взаимоотношения с клиентами |
| Контрольная работа | Учет материальных затрат в бухгалтерском учете |
| Контрольная работа | Современные методы арт-терапии |
| Контрольная работа | Геополитическое положение России |
| Контрольная работа | Особенности вознаграждения работников в организации |
| Контрольная работа | Виды запасов |
| Контрольная работа | Психоанализ |
| Контрольная работа | Скифы. Материальная и духовная культура |
| Контрольная работа | Действия над числами в различных системах счисления |
| Контрольная работа | Контрольная работа по Безопасность жизнедеятельности |
| Контрольная работа | Цитология и клеточная теория |
| Контрольная работа | Определение миссии и целей стратегического управления |