Экономико-математические методы

СОДЕРЖАНИЕ 

    

1. Симплексный метод в линейном программировании.                        3
2. Двойственность в линейном программировании.                               8
3. Транспортная задача.                                                                           9
4. Сетевое планирование и управление. Расчёт основных показателей.12

Библиографический список.                                                                    17 

 

 

1. СИМПЛЕКСНЫЙ МЕТОД В ЛИНЕЙНОМ ПРОГРАММИРОВАНИИ.

 

     Дано: Для производства двух видов продукции А и В можно используется сырьё трёх видов. При этом на изготовление единицы изделия А расходуется 2 ед. сырья первого вида, 4 – ед. 2-го и 3 – ед. 3-го вида. На изготовление единицы изделия В расходуется 3 ед. сырья 1-го вида, 2 – ед. 2-го вида, 5 – ед. 3-го вида сырья. На складе фабрики имеется сырья 1-го вида 35 ед., 2-го – 42, 3-го – 49 ед. От реализации единицы готовой продукции А фабрика имеет прибыль 3 тыс. руб., а от продукции В прибыль составляет 3 тыс. руб.

     Найти: Найти решение симплексным методом и графически.

     Решение: Данные о расходе сырья на производство единицы продукции, запасов сырья и прибыли от реализации единицы продукции вносим в таблицу. 

 

     Составим  математическую модель.

      Обозначим через х₁ и х₂ выпуск продукции А и В соответственно. Затраты не должны превышать запасы:

2x₁ + 3x₂ ≤ 35,

4x₁ + 2x₂ ≤ 42,

3x₁ + 5x₂ ≤ 49. 

     Прибыль от реализации х₁ единиц А и х₂ – В составит z = 3x₁+3x₂ ,

     Получили  модель задачи:

    2х₁ + 3х₂ 35,

   4х₁ + 2х₂

42,

   3х₁ + 5х₂

49,

   х₁

0; x₂ 0

              z = 3x₁ + 3x₂

  

  

     Вводим  балансовые переменные х₃, х₄, х₅.

     Получим модель в каноническом виде. 

          2x₁ + 3x₂ + x₃             = 35,

          4x₁ + 2x₂ +      x₄        = 42,                      

          3x₁ + 5x₂             + x₅ = 49.      

   x_j

0; (j=1,...,5);

   z = 3x₁ + 3x₂

. 

     Составим  симплексную таблицу: 

 

     Первые  три строки этой таблицы содержат в условной форме систему уравнений (ограничений) в канонической задаче. Последняя строка – оценочной, а элементы строки – оценками. Первый элемент а₀₀ оценочной строки представляет собой значение целевой функции z на начальном опорном плане:

= (0, 0, 35, 42, 49)

а₀₀ =

а₀₁ = 

а₀₂ = 

 

     Оценки  при всех базисных неизвестных всегда равны нулю.

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

     Составим  симплексную таблицу:

 

   Исходное  опорное решение:

    

x₁ = (0, 0, 35, 42, 49);

z₁ = 0. 

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

 

     Этот  минимум достигается для 2-й строки. В базис вводим х₁, выводим из базиса х₄. В результате первого шага получаем второе опорное решение: 

x₂ = ;

z₂ =

. 

     В оценочной строке одна отрицательная  оценка -7/2, соответствующая столбцу  x₂. Разрешающую строку выбираем по:

     

     Этот  минимум достигается для второй строки. В базис вводим x₂, вводим из базиса x₄.

     После выполнения 2-го шага получаем оптимальное  решение: 

 х_опт = (8, 5, 4, 0, 0);

z_max = 39. 

   Оптимальное решение исходной задачи получается отбрасыванием из компонент, связанных с балансовыми переменными х₃, х₄, х₅, т.е.

   

= (8,5).

     При этом значение z_max не изменится.

     Решим задачу геометрически. Рассмотрим систему неравенств, определяющих множество допустимых планов.

    2х₁ + 3х₂ 35,

   4x₁ + 2х₂

42,

   3х₁ + 5х₂

49

     х₁

0; x₂ 0. 

     Построим  граничащие прямые:

       

     2х₁ + 3х_{2 =} 35, 

       

     4x₁ + 2х_{2 =} 42, 

       

     3х₁ + 5х_{2 =} 49,               

        

     Поскольку х₁ 0 и x₂ 0, то допустимые планы принадлежат неотрицательному многоугольнику, при этом вся область лежит левее т.к. точка О(0;0) принадлежит области:

 

     Областью  решения системы является четырехугольник  ОАВС.

     Целевая функция z = 3x₁ + 3x₂. Линии уровня целевой функции z задаются уравнением:

   7х₁ + 5х₂ = const. 

     Это семейство параллельных прямых. Вектор N(3;3) является целевым, он перпендикулярен линиям уровня. Он указывает направление возрастания функции z. Вершина многоугольника, через которую проходит последняя линии уровня, дает максимальное значение целевой функции. На рисунке 1видно, что это точка В, которая лежит на пересечении прямых:

     

4x₁ + 2х₂

42, 

3х₁ + 5х₂

49. 

     Решив систему уравнений получим координаты точки В х₁ = 8, х₂ = 5. Подставив это значение в целевую функцию, получим .

     Ответ: Оптимальным планом выпуска продукции А и В является выпуск 8 ед. и 5 ед. продукции соответственно, при этом предприятие получает наибольшую прибыль, которая составляет 39 тыс. рублей. Остатки ресурсов равны нулю.

 

2. ДВОЙСТВЕННОСТЬ  В ЛИНЕЙНОМ ПРОГРАММИРОВАНИИ.