3. Математические методы в экономике

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

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

Матричные игры.

Сетевое планирование.

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

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

В этой задаче требуется найти наибольшее значение функции на множестве решений данной системы.

Так как задача содержит две переменные, то её можно решить графически.

Множество решений системы представляет собой многоугольник. Для того, чтобы его построить сначала проведём прямые:

,

,

,

.

Каждая прямая разбивает плоскость на две полуплоскости. Одна из полуплоскостей определяет множество решений соответствующего неравенства системы. Полуплоскость определяется с помощью контрольной точки, например (0;0).

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

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

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

Координаты точки находят из системы уравнений:

Система имеет решение , .

Следовательно, - наибольшее значение.

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

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

Транспортная задача - задача о наиболее экономном плане перевозок однородного груза из пунктов отправления в пункты назначения.

Предположим, что в пунктах отправления находится однородный груз в количестве 200, 205, 225 единиц. Груз требуется перевезти в пункты потребления , потребности которых составляют 190, 130, 80, 100, 130 единиц. Стоимости перевозки единицы груза из каждого пункта отправления в каждый пункт назначения известны и записаны в транспортной таблице:

B A

В транспортной таблице - количество груза, перевозимое из пункта в пункт .

Требуется найти такие , чтобы суммарная стоимость перевозок была бы минимальная.

Транспортная задача называется закрытой, если . В противном случае открытой. От открытой задачи всегда можно перейти к закрытой.

Если , то вводят фиктивный пункт потребления с потребностью с нулевыми стоимостями перевозок.

Если , то вводят фиктивный пункт отправления с запасами с нулевыми стоимостями перевозок.

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

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

Первый план перевозок можно найти методом наименьшей стоимости:

в клетке (2,3) наименьшая стоимость 3 и туда отправляем весь необходимый груз 80. Далее наименьшая стоимость 4 в клетках (2,4) и (2,2). В клетку (2,4) направляем все 100 единиц необходимого груза, а в клетку (2,2) – оставшиеся в пункте 25 единиц груза. Теперь наименьшая стоимость 5 в клетках (1,1) и (1,5). В клетку (1,1) направляем 190 единиц необходимого груза, а в клетку (1,5) – 10 единиц груза оставшегося а пункте . Затем направляем 120 единиц груза в клетку (3,5) и 105 единиц груза в клетку (3,2). Получим первый план перевозок:

	190	130	80	100	130
200	5 190	7	4	9	5 10
205	7	4 25	3 80	4 100	7
225	9	10 105	6	8	7 120

Проверим оптимальность полученного плана перевозок методом потенциалов.

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

для занятых клеток и

для свободных клеток.

Числа называются потенциалами соответственно поставщиков и потребителей.

Найдём потенциалы:

	190 5	130 8	80 7	100 8	130 5
200 0	5 190	7	4	9	5 10
205 -4	7	4 25	3 80	4 100	7
225 2	9	10 105	6	8	7 120

Так как для клетки (3,3) не выполняется условие оптимальности, то перейдём к следующему плану. В клетку (3,3) направим единиц груза и перераспределим груз в занятых клетках:

	190	130	80	100	130
200	5 190	7	4	9	5 10
205	7	4 25+t	3 80-t	4 100	7
225	9	10 105-t	6 t	8	7 120

Перераспределение производим так, чтобы в строке было бы только два и в столбце – два .

Подберём такое, чтобы одна из занятых клеток стала свободной. Это возможно при .

Новый план имеет вид:

	190	130	80	100	130
200	5 190	7	4	9	5 10
205	7	4 105	3	4 100	7
225	9	10 25	6 80	8	7 120

Найдём потенциалы:

	190 5	130 8	80 4	100 8	130 5
200 0	5 190	7	4	9	5 10
205 -4	7	4 105	3	4 100	7
225 2	9	10 25	6 80	8	7 120

Для клетки (3,4) условие оптимальности не выполняется. В эту клетку направим единиц груза и перераспределим груз в занятых клетках.

	190	130	80	100	130
200	5 190	7	4	9	5 10
205	7	4 105+t	3	4 100-t	7
225	9	10 25-t	6 80	8 t	7 120

Возьмём . Новый план имеет вид:

	190	130	80	100	130
200	5 190	7	4	9	5 10
205	7	4 130	3	4 75	7
225	9	10	6 80	8 25	7 120

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

	190 5	130 6	80 4	100 6	130 5
200 0	5 190	7	4	9	5 10
205 -2	7	4 130	3	4 75	7
225 2	9	10	6 80	8 25	7 120

Полученный план является оптимальным.

Транспортные расходы при этом будут минимальными:

.