Методы и модели в экономике

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

1. В  решении каких производственно-экономических проблем используются методы линейного программирования

1. рационального использования сырья и материалов;
2. задачи оптимального раскроя;
3. оптимизации производственной программы предприятий;
4. оптимального размещения и концентрации производства;
5. составления оптимального плана перевозок, работы транспорта (транспортные задачи);
6. управления производственными запасами;
7. и т. д.

2. На  чем основан графический метод  решения задач линейного программирования (ЛП)

     Графический метод основан на геометрической интерпретации задачи линейного  программирования и применяется  в основном при решении задач  двумерного пространства.        

3. Каким  образом осуществляется графическая  интерпретация системы ограничений  задачи ЛП. Как определить область  допустимых значений.

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

5. В  каком случае задача имеет  множество решений (привести графический  пример)

   Задача  имеет множество решений, если функция цели не ограничена, например, сверху на множестве допустимых решений 

      4  6  10

Задачи  линейного программирования

Решение задач линейного программирования симплекс-методом

      Задание

      Допустим  предприятие выпускает три вида изделий (И1, И2, И3), используя три вида ресурсов (Р1, Р2, Р3). Запасы ресурсов (З) ограничены. Прибыль от реализации (П) единицы изделия и нормы расхода ресурсов представлены в таблицах. Определить ассортимент и объемы выпуска продукции, получаемую прибыль, величину остатков ресурсов. Найти решение задачи симплексным методом с представлением  всех симплексных таблиц (промежуточных шагов решения) и проанализировать полученные результаты. Составить двойственную задачу. Определить двойственные оценки из последней симплексной таблицы и провести анализ последней симплексной таблицы. 

      Вариант 3                               

      

	И1	И2	И3	З
Р1	6	7	2	57
Р2	6	6	1	97
Р3	3	7	8	63
П	5	6	8

 

Решение.

   Симплекс-метод  применяется к задаче, записанной в канонической форме:

Приводим  систему ограничений к каноническому  виду:

      6Х1 +7Х2 +2 Х3 + Х4 = 57

      6Х1 +6Х2 + Х3 + Х5 = 97

      3Х1 + 7Х2 + 8Х3 + Х6 = 63 

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

     

   В первом столбце вписаны базисные неизвестные, второй содержит коэффициенты при базисных неизвестных в целевой  функции, в третьем – правые части  уравнений системы ограничений. Далее записана матрица из коэффициентов  левой части системы ограничений  , изменяющаяся в процессе пересчета. В верхней строке над неизвестными записаны соответствующие им коэффициенты в целевой функции. В последней строке записывается значение целевой функции при данном опорном плане, которое вычисляется по формуле f(x) = , и далее – оценки неизвестных, найденные по формуле D_j = - C_j.

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

   Для определения ключевой строки находим  отношения правых частей уравнений  к положительным элементам ключевого столбца а^/_is. Полученные значения q записываются в последний столбец симплексной таблицы. Из них выбирается наименьшая величина, которая указывает на ключевую строку.

   Пересчет  таблицы производится по следующему правилу: элементы ключевой строки делятся  на ключевой элемент (в нашем случае на 8). Далее, с помощью метода Жордана - Гаусса проводят пересчет таблицы таким образом, чтобы элементы ключевого столбца имели единицу на месте ключевого элемента и нули на месте всех остальных элементов. Для этого вычтем из элементов третьей строки соответствующие элементы первой строки поделённые на 2, а элементы второй строки умножим на -1 складываем с элементами третьей строки.

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

   Для каждого шага итерации строится своя симплексная таблица.

     
 

 

   

Транспортная  задача

решить задачу распределительным методом или  методом потенциалов

      Допустим  имеется три поставщика продукции  с соответствующими предложениями  а₁, а₂ и а₃ и три потребителя, спрос которых составляет в₁, в₂ и в₃ соответственно. Стоимость перевозки единицы груза из каждого пункта отправления до каждого пункта назначения задается матрицей С.

                          Вариант 3

а₁ = 80, а₂ = 70, а₃ = 50               6   4   3

в₁ = 45, в₂ = 27, в₃ = 88   С =     1   5   2

      3   1   5

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

	1	2	3	Запасы
1	6	4	3	80
2	1	5	2	70
3	3	1	5	50
Потребности	45	27	88

 

      Проверим  необходимое и достаточное условие  разрешимости задачи.

      ∑a = 80 + 70 + 50 = 200

      ∑в = 45 + 27 + 88 = 160

      Как видно, суммарная потребность груза  в пунктах назначения превышает  запасы груза на базах. Следовательно, модель исходной транспортной задачи является открытой. Чтобы получить закрытую модель, введем дополнительную (фиктивную) базу с запасом груза, равным 40 (200—160). Тарифы перевозки единицы  груза из базы во все магазины полагаем равны нулю.

      Занесем исходные данные в распределительную  таблицу.

	1	2	3	4	Запасы
1	6	4	3	0	80
2	1	5	2	0	70
3	3	1	5	0	50
Потребности	45	27	88	40

   

      Этап I. Поиск первого опорного плана.

      1. Используя метод наименьшей стоимости,  построим первый опорный план  транспортной задачи.

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

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

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

      Искомый элемент равен 1

      Для этого элемента запасы равны 70, потребности 45. Поскольку минимальным является 45, то вычитаем его.

      x21 = min(70,45) = 45.

x	4	3	0	80
1	5	2	0	70 - 45 = 25
x	1	5	0	50
45 - 45 = 0	27	88	40	0

 

      Искомый элемент равен 1

      Для этого элемента запасы равны 50, потребности 27. Поскольку минимальным является 27, то вычитаем его.

      x32 = min(50,27) = 27.

x	x	3	0	80
1	x	2	0	25
x	1	5	0	50 - 27 = 23
0	27 - 27 = 0	88	40	0

      Искомый элемент равен 2

      Для этого элемента запасы равны 25, потребности 88. Поскольку минимальным является 25, то вычитаем его.

      x23 = min(25,88) = 25.

x	x	3	0	80
1	x	2	x	25 - 25 = 0
x	1	5	0	23
0	0	88 - 25 = 63	40	0