Решение задач по высшей математике

Вариант №1 Составим систему ограничений х₁ + 2х₂ + 2х₃ 1100 3х₁ + 4х₂ + 2х₃  1500 x_j  0, (j = 1,3) Z₁ = 2x₁ + x₂ + 3x₃  max преобразуем ее к каноничному виду. Введем две дополнительные неотрицательные переменные х₄, х₅ и перейдем к функции Z_i =-Z. Модель примет вид Z₁ = -2x₁ — x₂ — 3x₃ – 0* х₄ – 0* х₅  min х₁ + 2х₂ + 2х₃ + х₄ = 1100 3х₁ + 4х₂ + 2х₃ + х₅= 1500 x_j  0, (j = 1,3) Записываем условия задачи в виде симплексной таблицы: Выпишем вектор r, компонентами которого являются коэффициенты при свободных переменных целевой функции r = (-2; -1; -3; ) Так как компоненты вектора отрицательны, то опорный план Х_оп¹ не является оптимальным. Выбираем максимальную по модулю отрицательную компоненту r: разрешающая строка будет первая, разрешающий элемент – a₁₃ Выполняя симплексное преобразование с разрешающим элементом a₁₃ придем к новой таблице Так как компоненты вектора отрицательны, то опорный план Х_оп¹ не является оптимальным. Разрешающим столбцом является (х₁), а разрешающей строкой (х₅), разрешающий элемент – a₂₂ Выполняя симплексное преобразование с разрешающим элементом a₂₂ придем к новой таблице Среди компонентов вектора нет отрицательных, опорный план Х_оп¹ является оптимальным. х₁ = 200 х₃ = 450 Z = 3 * 450 + 2*200 = 1750 Прибыль max = 1750 ; при выпуске А₁ = 200шт; А₂ = 0шт; А₃ = 450шт Найдем кол-во изделий при котором достигается max товарной продукции А₃ = 450 А₁ = 200 Z = 1 * 450 + 1*200 = 650 (кол-во изделий) 2. min (2x₁+5x₂) при следующих ограничениях: 2x₁+x₂3 8x₁+3x₂5 4x₁+x₂7 Приведем систему ограничений  к системе неравенств  , умножаем соответствующие строки на (-1) F(x) = 2x₁+5x₂ 2x₁+x₂3 -8x₁-3x₂-5 -4x₁-x₂-7 введя базисные переменные, перейдем к каноничной форме 2x₁+x₂+х₃3 -8x₁-3x₂+х₄-5 -4x₁-x₂+х₅-7 Х₁ =(0,0,3-5,-7) Среди отрицательных значений базисных переменных выберем наибольший по модулю. Ведущей будет 3-ая строка, а переменную х₅следует вывести из базиса Разрешающий элемент равный (-4) Выполняем преобразование симплексной таблицы методом Жордана-Гаусса Среди значений индексной строки нет положительных. Поэтому таблица определяет оптимальный план задачи Так как в полученном плане среди значений базисных переменных имеются отрицательные значения, функция цели F(x) не ограничена на множестве допустимых планов.F(x)  задача не имеет решения. 3.  Запишем условие в таблицу: поскольку в матрице существуют запрещенные к размещению клетки, то для отыскания оптимального плана достаточно заменить их на максимальные тарифы Проверим необходимое и достаточное условие разрешимости задачи = 30+50+120=200  = 40+30+20+10=100 суммарная потребность груза в пунктах менше запасов груза на базах . Модель транспортной задачи является открытой. Чтобы получить закрытую модель, введем фиктивную потребность равной 100. Тарифы перевозки единицы груза из базы во все магазины полагаем равны нулю. Выбираем в таблице наименьшую стоимость (это стоимость помещенная в клетке 2.1) так как 40  50, 40единиц груза помещаем в этой клетке, в оставшейся таблице стоимостей наименьшей является стоимость расположенная в клетках (2,2) заполнив ее аналогично продолжаем процесс до тех пор, пока все запасы не будут распределены, а потребности удовлетворены. Подсчитаем число занятых клеток таблицы, их 6, а должно быть m+n-1=8 Опорный план является вырожденным, строим новый план Значение целевой функции F(x)  = 4*20+2*10+2*40+0*10+2*30+0*90=240 Искомый элемент равен 2. Для этого элемента запасы равны 120, потребности 30. Поскольку min является 30,то вычитаем его. (3,2)=min(120,30)=30 аналогично продолжаем процесс до тех пор, пока все запасы не будут распределены, а потребности удовлетворены. число занятых клеток таблицы равно 6, а должно быть m+n-1= опорный план является вырожденным. Строим новый план Значение целевой функции F(x)  = 4*20+0*10+2*40+3*10+2*30+0*90=250 Искомый элемент равен 3 Значение целевой функции F(x)  = 4*20+2*10+2*40+0*10+2*30+0*90=240 Искомый элемент равен 5 число занятых клеток таблицы равно 5, а должно быть m+n-1= опорный план является вырожденным. Строим новый план Значение целевой функции F(x)  = 5*30+2*40+3*10+15*20+0*100=560 Искомый элемент равен 5 число занятых клеток таблицы равно 6, а должно быть m+n-1= опорный план является вырожденным. Строим новый план Значение целевой функции F(x)  = 4*20+2*10+2*20+5*30+3*20+0*100=350 Искомый элемент равен 5 Получен первый опорный план, который является допустимым опорный план является невырожденным. Значение целевой функции F(x)  = 4*20+0*10+2*40+2*30+5*10+0*80=270 Улучшение опорного плана Найдем предварительные потенциалы u_i , v_j по занятым клеткам таблицы, в которых u_i + v_j = с_ij , пологая что u₁ = 0 u₁ + v₃ = 4;0+ v₃=4; v₃=4 u₁ + v₅ = 0;0+ v₅=0; v₅=0 u₂ + v₅ = 0;0+ u₂ =0; u₂ =0 u₂+ v₁ = 2;0+ v₁=2; v₁=2 u₃ + v₅ = 0;0+ u₃=0; u₃=0 u₃ + v₂ = 2;0+ v₃=2; v₂=2 u₁ + v₃ = 5;0+ v₃=5; v₄=5 Опорный план не является оптимальным, так как существуют оценки свободных клеток, для которых u_i= v_jc_ij Выбираем максимальную оценку свободной клетки (1;4):2 Для этого в перспективную клетку (1,4) поставим знак «+», а в остальных вершинах многоугольника чередующиеся знаки «-», «+», «-» из грузов х_ij стоящих в минусовых клетках, выбираем наименьшее. Прибавляем 10 к объемам грузов, стоящих в плюсовых клетках и вычитаем 10 из х_ij , стоящих в минусовых клетках. Проверим оптимальность опорного плана u₁ + v₃ = 4;0+ v₃=4; v₃=4 u₁ + v₄ = 0;0+ v₄=0; v₄=2 u₃ + v₄ = 5;2+ u₃ =5; u₃ =3 u₃+ v₂ = 2;3+ v₂=2; v₂=-1 u₃ + v₅ = 0;3+ v₅=0; v₅=-3 u₂ + v₅ = 0;-3+ u₂=0; u ₂=3 u₂ + v₁= 2;3+ v₃=2; v₁=-1 из грузов х_ij стоящих в минусовых клетках, выбираем наименьшее. Прибавляем 0 к объемам грузов, стоящих в плюсовых клетках и вычитаем 0 из х_ij , стоящих в минусовых клетках. Получаем новый опорный план Проверим оптимальность опорного плана. u₁ + v₃ = 4;0+ v₃=4; v₃=4 u₁ + v₄ = 0;0+ v₄=0; v₄=2 u₂ + v₄ = 3;2+ u₃ =3; u₃ =1 u₂+ v₁ = 2;1+ v₁=2; v₁=1 u₂ + v₅ = 0;1+ v₅=0; v₅=-1 u₃ + v₅ = 0;-1+ u₃=0; u ₂=1 u₂ + v₂= 2;1+ v₂=2; v₁=1 Опорный план является оптимальным, так как все оценки свободных клеток удовлетворяют условию Минимальные затраты составят F(x) = 4*20+2*10+2*40+0*10+2*30+0*90=240 Из 1-го склада необходимо груз направить в 3-й магазин (20), в 4-й магазин (10) Из 2-го склада необходимо весь груз направить в 1-й магазин Из 3-го склада необходимо весь груз направить в 2-й магазин На 2-ом складе остался невостребованным груз в количестве 10 ед. Оптимальный план является вырожденным, так как базисная переменная x₂₅=0. На 3-ом складе остался невостребованным груз в количестве 90 ед. Оптимальный план является вырожденным, так как базисная переменная x₃₅=0. Задача имеет множество оптимальных планов, поскольку оценка для (2;4) равна 0. №4 Решите методом ветвей и границ следующую задачу коммивояжера: Сумма констант приведения определяет нижнюю границу Н Н  = _i + _i H = 8+7+16+5+5+3+0+19+3+0+0+0= 66 Определяем ребро ветвления и разобьем все множества маршрутов относительно этого ребра на два подмножества (i,j) и (i^*,j^*) Для всех клеток матрицы с нулевыми элементами заменяем поочередно нули на М () и определяем для них сумму образовавшихся констант приведения b(1,5) = 4+0 = 4; b(2,5)=0+12=12; b(3,6)=8+4=12; b(4,1)=4+9=13; b(5,2)=0+4=4; b(5,4)=0+0=0; b(6,3)=0+4=4; b(6,4)=0+0=0 наибольшая сумма констант равна (4+9) = 13дляребра (4,1), следовательно множество разбивается на два подмножества (4,1) и (4^*,1^*) исключение ребра (4,1) проводим путем замены элемента b₄₁ = 0 на М Нижняя граница гамильтоновых циклов этого подмножества Н(4^*,1^*) = 66+13=79 Нижняя граница подмножества (4,1) равна: Н(4,1) =66+0=66 поскольку нижняя граница этого подмножества (4,1) меньше чем подмножества (4^*,1^*) включаем в маршрут с новой границей Н=66 Определяем ребро ветвления b(1,5) = 4 + 0 = 4; b(2,5) = 12 + 0 = 12; b(3,6) = 8 + 9 = 17; b(5,2) = 0 + 4 = 4; b(5,4) = 0 + 0 = 0; b(6,3) = 0 + 4 = 4; b(6,4) = 0 + 0 = 0; Нижняя граница гамильтоновых циклов этого подмножества: Н(3^*;6^*) = 66+17=83 Включение ребра (3,6) Нижняя граница этого подмножества (3,6) равна Н(3,6) = 66+4 = 7083 ребро (3,6) включаем в маршрут с новой границей Н=70 Определяем ребро ветвления b(1.3)=0+8=8;b(1.5)=0+0=0;b(2.5)=8+0=8;b(5.2)=0+4=4;b(5.4)=0+0=0;b(6.4)=4+0=4 Н(1^*;3^*) = 70+78=78 Включение ребра Нижняя граница этого подмножества (1,3) равна Н(1,3) = 70+0 = 7078 ребро (1,3) включаем в маршрут с новой границей Н=70 Определяем ребро ветвления b(2.5)=24+29=53;b(5.2)=0+0=0;b(5.4)=0+24=24;b(6.2)=29+0=29 наибольшая сумма констант приведения равна (24+29) = 53 для ребра (2,5) Исключение ребра Нижняя граница гамильтоновых циклов Н(2^*;5^*) = 70+53=123 включение ребра (2,5) Сумма констант приведения сокращенной матрицы Нижняя граница подмножества (2,5)равна Н(2,5) = 70+0 = 70123 В результате по дереву ветвлений гамильтонов цикл образуют ребра: (4,1),(1,3),(3,6),(6,2),(2,5),(5,4) длина маршрута равна F(Mk)=74