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

 
 
 

 

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

      Подставляя  в наши неравенства точку с  координатами (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 (α₁₅).

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

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