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

СОДЕРЖАНИЕ 

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х₂

   3х₁ + 5х₂

   х₁

              z = 3x₁ + 3x₂

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

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

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

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

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

   x_j

   z = 3x₁ + 3x₂

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

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

а₀₀ =

а₀₁ = 

а₀₂ = 

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

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

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

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

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. 

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

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

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

    2х₁ + 3х₂ 35,

   4x₁ + 2х₂

   3х₁ + 5х₂

     х₁

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

     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х₂

3х₁ + 5х₂

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

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

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

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

     Решение: Экономической сутью переменных двойственной задачи является определение оценок на ресурсы.

     Для данной задачи составим двойственную.

z = 3x₁ + 3x₂

    2х₁ + 3х₂ 35,   y₁

   4х₁ + 2х₂

   3х₁ + 5х₂

   х₁

     Получим:           

     w = 35y₁ +42y₂ +49y₃

    2y₁ + 4y₂ +3y₃ 3   x₁

   3y₁ + 2y₂ + 5y₃

   y_i

     Соответствие  между переменными исходной и  двойственной задачами:

      x₃   x₄   x₅

     y₁   y₂   y₃ 

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

                               при      

Проверка. .

   Ответ: Наиболее дефицитным являются сырье 2 и 3 вида. Наименее дефицитным является сырье 1.

3. ТРАНСПОРТНАЯ  ЗАДАЧА.

      Дано: Из пунктов A_i, i= нужно перевезти a_i, i= единиц груза соответственно, в пункты B_j, j= в количествах b_j, j= соответственно. Затраты на перевозку 1 единицы груза из пункта A_i в B_j заданы в виде матрицы С=((с_ij)).

     Найти: Найти план перевозок, при котором суммарные транспортные затраты будут наименьшими.

     Решение: По методу «северо – западного» угла оптимальный план имеет вид:

     Число базисных клеток m+n – 1=4+5 – 1=8. Затраты на данный план:

     По  методу наименьшего элемента оптимальный  план приобретет вид:

     Число заполненных клеток  m+n – 1=8. Затраты:

     С помощью метода потенциалов проверим, оптимален ли план перевозок. Определим потенциалы строк – U_i и столбцов – V_j удовлетворяющие условию: U_i + V_j = C_ij для базисных переменных (для занятых клеток). Зададим U₁=0.

    U₁+V₄=3               U₁=0                  V₁=-1

   U₁+V₅=2               U₂=4                  V₂=-1

   U₂+V₂=3               U₃=3                  V₃=4

   U₂+V₃=8               U₄=3                  V₄=3

   U₂+V₄=7                                          V₅=2

   U₃+V₁=2

   U₃+V₂=2

   U₄+V₁=2 

     Определим характеристики для свободных неизвестных (пустых клеток) по формуле E_ij = C_ij – (U_i + V_j) и запишем в левом нижнем углу свободных клеток. План оптимален, если все E_ij 0.

   E₁₁=7-(0-1) > 0,

   E₁₂=5-(0-1) > 0,

   E₁₃=4-(0-4) = 0,

   E₂₁=4-(4-1) > 0,

   E₂₅=6-(4+2) = 0,

   E₃₃=5-(3+4) = - 2,

   E₃₄=6-(3+3) = 0,

   E₃₅=9-(3+2) > 0,

   E₄₂=5-(3-1) > 0,

   E₄₃=6-(3+4) = - 1,

   E₄₄=6-(3+3) = 0,

   E₄₅=7-(4+2) > 0. 

     Имеем две клетки с отрицательными оценками, выбираем с наименьшей оценкой E₃₃. Строим контур для клетки А₃В₃:

 А₃₃

     Вершинам  присваиваем чередующиеся знаки  плюс – минус, выбираем наименьшую поставку Количество груза в ''положительных'' вершинах увеличивается на 35, а в ''отрицательных'' уменьшается на 35. Θmin(35;125)=35 ,Δz=-2*35=-70 Получаем следующий план перевозок: