Модель задачи

X_ij от поставщика i к потребителю j

X₁₁ X₁₂ X₁₃ X₁₄

X₂₁ X₂₂ X₂₃ X₂₄

X₃₁ X₃₂ X₃₃ X₃₄

Минимум затрат minz= 2X₁₁ + 3X₁₂ + 1X₁₃ + 4Х₁₄+ X₂₁ X₂₂ X₂₃ X₂₄+ X₃₁ X₃₂ X₃₃ X₃₄

Условия по потребителям X₁₁+ X₂₁+ X₃₁ ≥40

Ограничения по запасам поставщиков

X₁₁ X₁₂ X₁₃ X₁₄ ≤100

X₂₁ X₂₂ X₂₃ X₂₄ ≤80

X₃₁ X₃₂ X₃₃ X₃₄ ≤120

Потребители просят не меньше, но в результате решения задачи получат ровно нижнюю границу (40, 160, 20 и 80), так как больше этих величин давать нет смысла ибо затраты возрастут, отсюда ограничения по поставщикам превратятся в равенства. В нашем случае, суммарное потребление, 300, но и у поставщиков 300. Следовательно, у поставщиков после транспортировки ничего не останется. И ограничения можно тоже напить равенства. Такая задача называется сбалансированной (замкнутой транспортной задачей). Существует 3 вида задач транспортных:

1. Когда суммарный запас равен суммарному спросу, задача на минимум, ограничение только равенство.

2. Суммарный запас больше суммарного спроса. Задачи этого типа легко сводятся к сбалансированной задаче путем введения фиктивного потребителя с потребностью (сумма запасов минус сумма спроса). Затраты к нему нулевые и все, что он получит, останется у поставщика.

3. Социалистическая – запасы меньше спроса. Такая задача не имеет никакого решения. Можно решить совершенно другую задачу: как развести то, что есть с недопоставками, так называемым буферным потребителям, для которых вводится коэффициент важности, умножаемый на затраты.

Транспортная задача – ЗЛП. Она обладает такими свойствами, что с её помощью можно решать:

1. Не классические транспортные задачи, т.е. задачи с промежуточным хранением, с перевозками между поставщиками и возвратом от потребителей.

2. Поиск кратчайшего пути в сети для задач календарного планирования и управления.

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

Задача математического программирования.

max

05.03.12

Геометрическая интерпретация поиска оптимальной точки.

Пример:

Max L=X1+3X2

6X1+5X2<=30

X1+2X2<=6

X1+X2=>1

X1=>0

X2=>0

AX1+bX2<=C

aX1+bX2=C – прямая, на этой прямой имеем строгие равенства, вопрос: какие точки удовлетворяют этому неравенству

6X1+5X2<=30

6X1+5X2=30

X1=0, X2=6

X2=0, X1=5

\

Область ограничения данной задачи – это все точки внутри и на границе многоугольника ABKDE.

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

Экономический смысл допустимой точки (все возможные допустимые варианты параметров экономической задачи), а оптимальная точка только один наилучший по функции цели или по критерию принятия решения.

Поиск оптимальной точки из допустимых

L=X1+3X2

Пусть L=4

X1+3X2=4

X2=0, X1=4

X1=0, X2=1

Если нарисовать семейство прямых L=Const, то они образуют так называемые линии равного уровня. Эти линии параллельны между собой и их легко построить, если взять вектор C= (вектор коэффициентов функции цели) этот вектор называется вектором Градиента, он перпендикулярен линиям равного уровняю.

Вектор С своим направлением показывает возрастание функции цели, поэтому если двигать перпендикуляры по стрелке вектора С, то крайняя (последняя) точка области допустимых значений – это максимум (в нашем случае точка К), если двигать против стрелки градиента, то это точка минимум (точка А).

Если первое ограничение равенства, то область допустимых значений отрезов DE.

Геометрическая интерпретация показывает, что возможно, что оптимальное решение задачи линейного программирования – это угловая точка области допустимых значений.

Виды областей допустимых значений в линейном программировании (ЗЛП):

1. Ограниченная выпуклая область

(1)

(2)

(3)

33(

ЗЛП дает только выпуклую область. Область называется выпуклой, если отрезок, соединяющий её точки принадлежит ей. Круг является выпуклой, но не окружность!!!

2. Неограниченный выпуклый многогранник

(4)

(5)

3. Отсутствие допустимых точек (нету точек, которые удовлетворяют решению).

В задачах экономики и управления могут встречаться только ситуации 1, 2 и тривиальная ситуация 3.

Ситуация 4 и 5 в экономике не встречается из-за ограниченности ресурсов (материалы, время, деньги).

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

Ситуации с поиском оптимального решения ЗЛП.

I. Единственное оптимальное решение – угловая точка вершины многогранника.

max

min

II. Бесконечное множество оптимальных точек (грань многогранника) альтернативный оптимум.

A

В

min А B

А и В max все допустимые точки оптимальны

Для принятия решения в альтернативном случае берется любая точка из оптимальных (наилучших данной задачи). Её выбирают из вне модельных соображений.

III. Отсутствие оптимального решения на множестве допустимых в экономике и управлении не встречается.

Мин и макс нет

IV. Нет допустимых точек.

Дата добавления: 2014-01-03