Автор работы: Пользователь скрыл имя, 19 Октября 2014 в 21:03, контрольная работа
1. Дана задача линейного программирования при ограничениях:
Графическим методом найти оптимальные решения при стремлении целевой функции к максимальному и минимальному значениям.
Значения коэффициентов целевой функции и системы ограничений.
2. Фирма изготовляет два вида красок для внутренних (В) и наружных (Н) работ. Для их производства используют исходные продукты: пигмент и олифу. Расходы исходных продуктов и максимальные суточные запасы указаны в таблице.
Расходы и суточные запасы исходных продуктов
Исходный продукт Расход исходных продуктов на 1 т краски Суточный запас, т
Краска Н Краска В
Пигмент
Олифа
Изучение рынка сбыта показало, что суточный спрос на краску для наружных (внутренних) работ никогда не превышает т в сутки. Цена продажи 1 т краски для наружных работ ден. ед.
Какое количество краски каждого вида должна производить фирма, чтобы доход от реализации продукции был максимален?
1 |
2 |
3 |
Запасы | |
1 |
3 |
9 |
8[20] |
20 |
2 |
4 |
6[14] |
7 |
14 |
3 |
2[9] |
4[3] |
5 |
12 |
4 |
0 |
0[14] |
0 |
14 |
Потребности |
9 |
31 |
20 |
2. Подсчитаем число занятых клеток таблицы, их 5, а должно быть m + n - 1 = 6. Следовательно, опорный план является вырожденным.
Строим новый план.
Значение целевой функции для этого опорного плана равно:
F(x) = 8*20 + 6*14 + 2*9 + 4*3 + 0*14 = 274
Искомый элемент равен 3
Для этого элемента запасы равны 20, потребности 9. Поскольку минимальным является 9, то вычитаем его.
x11 = min(20,9) = 9.
3 |
9 |
8 |
20 - 9 = 11 |
x |
6 |
7 |
14 |
x |
4 |
5 |
12 |
0 |
0 |
0 |
14 |
9 - 9 = 0 |
31 |
20 |
0 |
Искомый элемент равен 4
Для этого элемента запасы равны 12, потребности 31. Поскольку минимальным является 12, то вычитаем его.
x32 = min(12,31) = 12.
3 |
9 |
8 |
11 |
x |
6 |
7 |
14 |
x |
4 |
x |
12 - 12 = 0 |
0 |
0 |
0 |
14 |
0 |
31 - 12 = 19 |
20 |
0 |
Искомый элемент равен 6
Для этого элемента запасы равны 14, потребности 19. Поскольку минимальным является 14, то вычитаем его.
x22 = min(14,19) = 14.
3 |
9 |
8 |
11 |
x |
6 |
x |
14 - 14 = 0 |
x |
4 |
x |
0 |
0 |
0 |
0 |
14 |
0 |
19 - 14 = 5 |
20 |
0 |
Искомый элемент равен 8
Для этого элемента запасы равны 11, потребности 20. Поскольку минимальным является 11, то вычитаем его.
x13 = min(11,20) = 11.
3 |
x |
8 |
11 - 11 = 0 |
x |
6 |
x |
0 |
x |
4 |
x |
0 |
0 |
0 |
0 |
14 |
0 |
5 |
20 - 11 = 9 |
0 |
Искомый элемент равен 0
Для этого элемента запасы равны 14, потребности 5. Поскольку минимальным является 5, то вычитаем его.
x42 = min(14,5) = 5.
3 |
x |
8 |
0 |
x |
6 |
x |
0 |
x |
4 |
x |
0 |
0 |
0 |
0 |
14 - 5 = 9 |
0 |
5 - 5 = 0 |
9 |
0 |
Искомый элемент равен 0
Для этого элемента запасы равны 9, потребности 9. Поскольку минимальным является 9, то вычитаем его.
x43 = min(9,9) = 9.
3 |
x |
8 |
0 |
x |
6 |
x |
0 |
x |
4 |
x |
0 |
0 |
0 |
0 |
9 - 9 = 0 |
0 |
0 |
9 - 9 = 0 |
0 |
1 |
2 |
3 |
Запасы | |
1 |
3[9] |
9 |
8[11] |
20 |
2 |
4 |
6[14] |
7 |
14 |
3 |
2 |
4[12] |
5 |
12 |
4 |
0 |
0[5] |
0[9] |
14 |
Потребности |
9 |
31 |
20 |
В результате получен первый опорный план, который является допустимым, так как все грузы из баз вывезены, потребность магазинов удовлетворена, а план соответствует системе ограничений транспортной задачи.
2. Подсчитаем число занятых клеток таблицы, их 6, а должно быть m + n - 1 = 6. Следовательно, опорный план является невырожденным.
Значение целевой функции для этого опорного плана равно:
F(x) = 3*9 + 8*11 + 6*14 + 4*12 + 0*5 + 0*9 = 247
Этап II. Улучшение опорного плана.
Проверим оптимальность опорного плана. Найдем предварительные потенциалы ui, vj. по занятым клеткам таблицы, в которых ui + vj = cij, полагая, что u1 = 0.
u1 + v1 = 3; 0 + v1 = 3; v1 = 3
u1 + v3 = 8; 0 + v3 = 8; v3 = 8
u4 + v3 = 0; 8 + u4 = 0; u4 = -8
u4 + v2 = 0; -8 + v2 = 0; v2 = 8
u2 + v2 = 6; 8 + u2 = 6; u2 = -2
u3 + v2 = 4; 8 + u3 = 4; u3 = -4
v1=3 |
v2=8 |
v3=8 | |
u1=0 |
3[9] |
9 |
8[11] |
u2=-2 |
4 |
6[14] |
7 |
u3=-4 |
2 |
4[12] |
5 |
u4=-8 |
0 |
0[5] |
0[9] |
Опорный план является оптимальным, так все оценки свободных клеток удовлетворяют условию ui + vj ≤ cij.
Минимальные затраты составят:
F(x) = 3*9 + 8*11 + 6*14 + 4*12 + 0*5 + 0*9 = 247
Проверим оптимальность найденного плана по первой теореме двойственности (в оптимальном решении значения целевых функций прямой и двойственных задач совпадают: F = G).
G = 0•20 -2•14 -4•12 -8•14 + 3•9 + 8•31 + 8•20 = 247
Анализ оптимального плана.
Из 1-го склада необходимо груз направить в 1-й магазин (9), в 3-й магазин (11)
Из 2-го склада необходимо весь груз направить в 2-й магазин
Из 3-го склада необходимо весь груз направить в 2-й магазин
Потребность 2-го магазина остается неудовлетворенной на 5 ед.
Оптимальный план является вырожденным, так как базисная переменная x42=0.
Потребность 3-го магазина остается неудовлетворенной на 9 ед.
Оптимальный план является вырожденным, так как базисная переменная x43=0.