Математическое программирование

271 Построить на плоскости область решений системы линейных неравенств и геометрически найти наименьшее и наибольшее значения линейной функции.
281 Предположим, что для производства двух видов продукции А и В можно использовать материалы только трех сортов. При этом на изготовление единицы изделия вида А расходуется а1 кг материала первого сорта, а2 кг материала второго сорта и а3 кг материала третьего сорта. На изготовление единицы изделия вида В расходуется b1 кг материала первого сорта, b2 кг материала второго сорта, b3 кг материала третьего сорта. На складе фабрики имеется всего материала первого сорта с1 кг, материала второго сорта с2 кг, материала третьего сорта с3 кг. От реализации единицы готовой продукции вида А фабрика имеет прибыль α рублей. А от продукции вида В прибыль составл ...

Решение:
Необходимо найти минимальное и максимальное значения целевой функции F = 7x1-x2 → min/ max, при системе ограничений

Математическое программирование.

Обозначим границы области многоугольника решений.Построим прямую, отвечающую значению функции F = 0: F = 10x1+2x2 = 0..Решение:Занесем исходные данные в распределительную таблицу. 12345Запасы1574252002713110175323687225Потребности10013080190100Математическая модель транспортной задачи: F = ∑∑cijxij, (1) при условиях: ∑xij = ai, i = 1,2,…, m, (2) ∑xij = bj, j = 1,2,…, n, (3) Проверим необходимое и достаточное условие разрешимости задачи. ∑a = 200 + 175 + 225 = 600 ∑b = 100 + 130 + 80 + 190 + 100 = 600 Условие баланса соблюдается. Запасы равны потребностям. Следовательно, модель транспортной задачи является закрытой. Используя метод северо-западного угла, построим первый опорный план транспортной задачи. План начинается заполняться с верхнего левого угла. Для искомого элемента равного 5 запасы равны 200, потребности 100. Поскольку минимальным является 100, то вычитаем его. x11 = min(200,100) = 100. 57425200 - 100 = 100x13110175x3687225100 - 100 = 0130801901000 Для искомого элемента равного 7 запасы равны 100, потребности 130. Поскольку минимальным является 100, то вычитаем его. x12 = min(100,130) = 100. 57xxx100 - 100 = 0x13110175x36872250130 - 100 = 30801901000 И так далее, получаем первый опорный план.12345Запасы15[100]7[100]425200271[30]3[80]1[65]1017532368[125]7[100]225Потребности10013080190100В результате получен первый опорный план, который является допустимым, так как все грузы из баз вывезены, потребность магазинов удовлетворена, а план соответствует системе ограничений транспортной задачи. Подсчитаем число занятых клеток таблицы, их 7, а должно быть m + n - 1 = 7. Следовательно, опорный план является невырожденным. Значение целевой функции для этого опорного плана равно: F(x) = 5*100 + 7*100 + 1*30 + 3*80 + 1*65 + 8*125 + 7*100 = 3235 Улучшаем опорный план. Проверим оптимальность опорного плана. Найдем предварительные потенциалы ui, vi. по занятым клеткам таблицы, в которых ui + vi = cij, полагая, что u1 = 0. u1 + v1 = 5; 0 + v1 = 5; v1 = 5 u1 + v2 = 7; 0 + v2 = 7; v2 = 7 u2 + v2 = 1; 7 + u2 = 1; u2 = -6 u2 + v3 = 3; -6 + v3 = 3; v3 = 9 u2 + v4 = 1; -6 + v4 = 1; v4 = 7 u3 + v4 = 8; 7 + u3 = 8; u3 = 1 u3 + v5 = 7; 1 + v5 = 7; v5 = 6 v1=5v2=7v3=9v4=7v5=6u1=05[100]7[100]425u2=-671[30]3[80]1[65]10u3=12368[125]7[100]Опорный план не является оптимальным, так как существуют оценки свободных клеток, для которых ui + vi > cij (1;3): 0 + 9 > 4; ∆13 = 0 + 9 - 4 = 5 (1;4): 0 + 7 > 2; ∆14 = 0 + 7 - 2 = 5 (1;5): 0 + 6 > 5; ∆15 = 0 + 6 - 5 = 1 (3;1): 1 + 5 > 2; ∆31 = 1 + 5 - 2 = 4 (3;2): 1 + 7 > 3; ∆32 = 1 + 7 - 3 = 5 (3;3): 1 + 9 > 6; ∆33 = 1 + 9 - 6 = 4 max(5,5,1,4,5,4) = 5 Выбираем максимальную оценку свободной клетки (1;3): 4 Для этого в перспективную клетку (1;3) поставим знак «+», а в остальных вершинах многоугольника чередующиеся знаки «-», «+», «-». 12345Запасы15[100]7[100][-]4[+]25200271[30][+]3[80][-]1[65]1017532368[125]7[100]225Потребности10013080190100Цикл приведен в таблице (1,3; 1,2; 2,2; 2,3; ). Из грузов хij стоящих в минусовых клетках, выбираем наименьшее, т.е. у = min (2, 3) = 80. Прибавляем 80 к объемам грузов, стоящих в плюсовых клетках и вычитаем 80 из Хij, стоящих в минусовых клетках. В результате получим новый опорный план. 12345Запасы15[100]7[20]4[80]25200271[110]31[65]1017532368[125]7[100]225Потребности10013080190100Проверим оптимальность опорного плана. Найдем предварительные потенциалы ui, vi. по занятым клеткам таблицы, в которых ui + vi = cij, полагая, что u1 = 0. u1 + v1 = 5; 0 + v1 = 5; v1 = 5 u1 + v2 = 7; 0 + v2 = 7; v2 = 7 u2 + v2 = 1; 7 + u2 = 1; u2 = -6 u2 + v4 = 1; -6 + v4 = 1; v4 = 7 u3 + v4 = 8; 7 + u3 = 8; u3 = 1 u3 + v5 = 7; 1 + v5 = 7; v5 = 6 u1 + v3 = 4; 0 + v3 = 4; v3 = 4 v1=5v2=7v3=4v4=7v5=6u1=05[100]7[20]4[80]25u2=-671[110]31[65]10u3=12368[125]7[100]Опорный план не является оптимальным, так как существуют оценки свободных клеток, для которых ui + vi > cij (1;4): 0 + 7 > 2; ∆14 = 0 + 7 - 2 = 5 (1;5): 0 + 6 > 5; ∆15 = 0 + 6 - 5 = 1 (3;1): 1 + 5 > 2; ∆31 = 1 + 5 - 2 = 4 (3;2): 1 + 7 > 3; ∆32 = 1 + 7 - 3 = 5 max(5,1,4,5) = 5 Выбираем максимальную оценку свободной клетки (1;4): 2 Для этого в перспективную клетку (1;4) поставим знак «+», а в остальных вершинах многоугольника чередующиеся знаки «-», «+», «-». 12345Запасы15[100]7[20][-]4[80]2[+]5200271[110][+]31[65][-]1017532368[125]7[100]225Потребности10013080190100Цикл приведен в таблице (1,4; 1,2; 2,2; 2,4; ). Из грузов хij стоящих в минусовых клетках, выбираем наименьшее, т.е. у = min (1, 2) = 20. Прибавляем 20 к объемам грузов, стоящих в плюсовых клетках и вычитаем 20 из Хij, стоящих в минусовых клетках. В результате получим новый опорный план. 12345Запасы15[100]74[80]2[20]5200271[130]31[45]1017532368[125]7[100]225Потребности10013080190100Проверим оптимальность опорного плана. Найдем предварительные потенциалы ui, vi. по занятым клеткам таблицы, в которых ui + vi = cij, полагая, что u1 = 0.