Контрольная работа по "Экономико-математическому моделированию". 5

      Задание 5 

      Предприятие может работать по пяти технологическим  процессам (Т1, Т2, Т3, Т4, Т5), выпуская количество продукции за единицу времени  соответственно 60, 120, 25, 35, 30. Составить программу максимального выпуска продукции при условии, что известны количество сырья, расход электроэнергии, заработная плата и накладные расходы при изготовлении продукции в единицу времени по заданным технологиям.

 

      Решение.

      Составим  математическую модель задачи линейного  программирования.

      Необходимо  найти максимум функции

      

      при следующих ограничениях:

        

      Задание 15 

      Нужно распилить большое число бревен длиной 10 м. на бруски размерами 2, 3, 4 м., количество которых, в зависимости  от размеров, должны быть в отношении 5 : 6 : 3. Найти план распила с минимальным  числом отходов. 

      Решение.

      Определим все возможные способы распила  бревен, указав, сколько соответствующих  брусьев при этом получается.

 

      Составим  математическую модель задачи линейного  программирования, приняв, что всего поступает на распил а бревен:

      Введем  переменную х – число комплектов, тогда целевая функция будет иметь вид:

      

      при условиях, что все бревна должны быть распилены, т.е.

       ,

      число брусьев каждого размера должно удовлетворять условию комплектности

      

      Из  последнего равенства, определив  и исключив х из остальных выражений, придем к следующей задаче, состоящей в максимизации функции при ограничениях: 

      

        
 

      Задание 25

      Фирма имеет 3 шахты. Пусть ai – суточная добыча угля в i-й шахте; ti – затраты на добычу 1 тонны в i-й шахте в сутки. По контракту фирма должна поставлять bi тонн угля в сутки j-му потребителю, ; штраф за недопоставку составляет ki за тонну. Доставка угля производится в вагонах. Вместимость вагона 30 тонн, затраты на аренду вагона – 10 руб. на 1 км и не зависят от степени загруженности вагона. Расстояния между шахтами и потребителями cij даны в таблице. Составить план добычи и доставки угля, чтобы общие затраты были минимальными.

      а1 = 90; а2 = 120; а3 = 180;

      t1 = 600; t2 = 500; t3 = 400;

      b1 = 120; b2 = 180; b3 = 150;

      k1 = 100; k2 = 150; k3 = 150.

        

      Решение.

      Суточная  производительность трех шахт:

      

      Суточная потребность заказчиков:

      

       , т.е. потребности превышают возможности. 

      Недопоставка  составляет 60 тонн.

      Полные  затраты складываются из затрат на производство, затрат на перевозку  и штрафов.

      Определим затраты на перевозку 1 тонны угля из i-й шахты j-му потребителю:

       .

      Следовательно, затраты на перевозку всего угля будут равны

       , где xij – количество угля в поставке одной шахты одному потребителю.

      Затраты на производство 1 тонны угля , затраты на производство всего угля равны .

      Штраф за недопоставку одному потребителю  будет равен: , где - количество угля, фактически поставленное данному потребителю.

      Найдем  коэффициенты матрицы затрат:

      

      

      

      

      

      

      

      

      

      Построим транспортную модель, позволяющую найти программу производства и доставки с минимальными затратами:

 

     Задание 35

     Пользуясь методом Жордана-Гаусса, решить систему  линейных уравнений; провести проверку полученного решения:

     

     Первое  уравнение системы:

     умножаем  на 2 и складываем со вторым;

     умножаем  на (-2) и складываем с третьим;

     умножаем на (-3) и складываем с четвертым.

     Получаем:

     

     Второе  уравнение системы умножаем на (1).

     Затем:

     Складываем с первым;

     Умножаем  на (-1) и складываем с третьим;

     Умножаем  на 2 и складываем с четвертым.

     Получаем:

     

     Третье  уравнение системы:

     Умножаем  на (-2) и складываем с первым;

     Умножаем на (-1) и складываем со вторым;

     Умножаем  на (-2) и складываем с четвертым.

     Получим:

     

     Отсюда:

     х₁ = 2

     х₂ = 5

     х₃ = 3

     х₄ = -5

     Проверим  решение методом подстановки:

     

     Система уравнений решена верно. 

     Задание 55

     Построить на плоскости область решений  системы линейных неравенств и геометрически  найти наименьшее и наибольшее значения линейных функций:

     

       

     Решение.

     Сначала определим многоугольник решений. Для этого в неравенствах системы ограничений и условиях неотрицательности переменных знаки неравенств заменим на знаки точных равенств и найдем соответствующие прямые:

     

     Строим  эти прямые:

     

 
 
 

 

      Каждая  прямая делит плоскость на две  полуплоскости. Координаты точек одной  полуплоскости удовлетворяют исходному  неравенству, а другой – нет. Чтобы определить искомую полуплоскость, нужно взять какую-нибудь точку, принадлежащую одной из полуплоскостей, и проверить, удовлетворяют ли ее координаты данному неравенству. Если координаты точки удовлетворяют данному неравенству, то искомой является та полуплоскость, в которой лежит данная точка, в противном случае – другая полуплоскость.

      Подставляя  в наши неравенства точку с  координатами (0;0) мы обнаруживаем, что  она не удовлетворяет первому неравенству. Множество решений представлено на рисунке в виде треугольника АВС.

      Рассмотрим  случай, когда  .

      Строим  линию уровня (т.е. прямую целевой  функции таким образом, чтобы  она пересекала множество решений).

     Строим  вектор нормали  с координатами (3;-2). Будем перемещать линию уровня параллельно ее первоначальному положению в направлении вектора n, и последняя точка, в которой линия коснется ОДЗ, и будет точкой, в которой функция принимает минимальное значение при заданных ограничениях. Это точка В (см. рисунок), находящаяся на пересечении прямых, описанных уравнениями и .

     Отсюда  находим:

      ;

      .

     Подставим их в целевую функцию:

     

     Это наибольшее значение линейной функции  при заданных ограничениях.

     Аналогичным образом находим наименьшее значение функции, когда  .

     Размещаем линию уровня внутри области допустимых значений и двигаем в противоположную  сторону (т.е. в сторону начала координат). Последняя точка, в которой линия коснется ОДЗ, и будет точкой, в которой функция принимает минимальное значение при заданных ограничениях. Это точка С, находящаяся на пересечении прямых и . Находим ее координаты:

     

     

     Отсюда  координаты точки С:

     

     Подставим их в целевую функцию:

      .

     Это наименьшее значение линейной функции  при заданных ограничениях. 

     Задание 75

     Для приготовления различных изделий  А и В используется три вида сырья. На производство единицы изделия  А требуется затратить сырья первого вида а₁ кг, сырья второго вида а₂ кг, сырья третьего вида а₃ кг. На производство единицы изделия В требуется затратить сырья первого вида b₁ кг, сырья второго вида b₂ кг, сырья третьего вида b₃ кг.

     Производство  обеспечено сырьем первого вида в количестве р₁ кг, сырьем второго вида в количестве р₂ кг, сырьем третьего вида в количестве р₃ кг.

     Прибыль от реализации единицы готового изделия  А составляет a руб., а изделия В - b руб.

     Составить план производства изделий А и  В, обеспечивающий максимальную прибыль от их реализации. Решить задачу симплексным методом путем преобразования симплекс-таблиц.

 

      a = 3

      b = 8 

     Решение.

     Составим  математическую модель задачи. Искомый  выпуск изделий А обозначим через x₁, изделий В – через x₂. Поскольку имеются ограничения на выделенный предприятию фонд сырья каждого вида,  переменные x₁, x₂ должны удовлетворять следующей системе неравенств:

     

     Общая прибыль от произведенной предприятием продукции при условии выпуска x1 изделий А и х2 изделий В составляет

     

     По  своему экономическому содержанию переменные х₁, х₂ могут принимать только лишь неотрицательные значения:

     

     Таким образом, приходим к следующей математической задаче: среди всех неотрицательных решений системы неравенств требуется найти такое, при котором функция принимает максимальное значение.

     Запишем эту задачу в виде основной задачи линейного программирования. Для  этого перейдем от ограничений-неравенств к ограничениям-равенствам. Введем три дополнительные переменные, в результате чего ограничения запишутся в виде системы уравнений:

     

     Целевая функция будет иметь вид:

     

      Составляем  симплекс-таблицу.

 

     В третьей итерации найдено оптимальное  решение:

      , при этом значение целевой  функции

      , т.е. максимальная прибыль от реализации изделий при заданных ограничениях равна 52 руб. 

     Задание 95

     На  три базы А1, А2, А3 поступил однородный груз в количестве а1 тонн на базу А1, а2 тонн на базу А2, а3 тонн на базу А3. Полученный груз требуется перевезти в пять пунктов: b1 тонн в пункт В1, b2 тонн в пункт В2, b3 тонн в пункт В3, b4 тонн в пункт В4, b5 тонн в пункт В5.

     Расстояние  между пунктами отправления (базами) и пунктами назначения (потребителями) указаны в таблице (матрица расстояний D).

     Стоимость перевозки пропорциональна количеству груза и расстоянию, на которое этот груз перевозится. Спланировать перевозки так, чтобы их общая стоимость была наименьшей.

     a1 = 80  b1 = 190

     a2 = 100  b2 = 50

     a3 = 310  b3 = 50

     b4 = 70

     b5 = 130

       

     Решение.

     Проверяем, выполняется ли необходимое и достаточное условие разрешимости задачи. Находим суммарные запасы поставщиков и суммарные потребности потребителей.

      - возможности равны потребностям.

     Составим  начальный опорный план методом  минимальной стоимости.

 

     Получен опорный план Х1:

       

     Мы  получили 7 клеток с перевозками. В этой задаче опорный план определяется числами, стоящими в клетках.

     Согласно  данному плану перевозок, общая  стоимость перевозок всего груза  составляет

     

      Проверим  опорный план на оптимальность методом  потенциалов.

      Находим потенциалы в клетках с перевозками. В каждой клетке таблицы разность потенциалов равна стоимости  перевозки.

         

      Считаем в свободных клетках α_ij (проверка Х₁ на оптимальность).

      

     

     Среди α_ij есть положительные числа, поэтому опорный план не является оптимальным.

     Фиксируем клетку с наибольшим положительным  α_ij (α₁₅).

     Строим  замкнутую ломаную из горизонтальных и вертикальных звеньев с вершинами в занятых клетках и с одной в фиксированной клетке, т.е. строим цикл для клетки. Перераспределяем груз по циклу: в фиксированной клетке ставим (+), в остальных вершинах – чередование (+/-). Минимальную из отрицательных перевозок отнимаем от всех отрицательных перевозок и прибавляем ко всем положительным.

     Получаем  новый опорный план: