Методологический базис тпр (стр. 13 из 14)

4 Решение задачи линейного программирования.

4.1 Условие задачи линейного программирования.

Условия задачи

Имеются две бетономешалки {А, В} и три стройки {1,2,3} (потребители бетона). В сутки стройкам требуется 700 т бетона, соответственно: 200т, 280т, 220т. Производительность источников А И В равна 320 т и 380 т. Удельная стоимость доставки за тонну определена матрицей

,

в условных единицах.

Требуется. Определить неизбежные суточные затраты на операцию доставки грузов.

4.1.1 Граф-схема решения задачи линейного программирования.

Первая модель решения: на полном двудольном графе отношений.

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

По дуге графа (А,2) при СА1 = 1 транспортировать 280 тонн и платить 1*280=280 усл.ед. стоимости.

Остаток бетона 320-280=40 отправляется на строку 5 при затратах на транспортировку 5*40=200 усл.ед. На стройку 1 по 8 усл.ед. за тонну его отправлять не выгодно.

Аналогично имеем дугу (В,1) с минимальными затратами 3*200=600 усл.ед. Остаток по дуге (В,3) с неизбежными затратами 7*180=1260 усл.ед.

Общая стоимость суточных затрат составит 2340 усл.ед. из единственности приведённого решения вытекает и его оптимальность.

W=CX=1*280+3*200+5*40+7*180=280+600+200+1260=2340 усл.ед.

Рис.6. Решение задачи на графе К2,3 :

осуществляется последовательность в соответствии с разметкой

графа: (А,2)-280; (A,3)-40; (B,1)-200;(В,3)-180

4.1.2 Алгебраическая модель решения задачи линейного программирования.

Вторая модель. Алгебраический уровень описания задачи. В общем случае задачи размерности 2х3, где |{A,B}| и 3=|{1,2,3}|- обозначение мощности множества, т.е. числа элементов в множествах, имеет вид:

Дано:

Найти:

Однако не все переменные множества Х является независимыми.

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

х1=х11 и х2=х12 имеем:

x13=х3=320-(х1+х2)

0

x21=x4=200-x1

0

x22=x5=280-x2

0

x23=x6=220-x3=x1+x2-100

0

x1

0 и x2 0.

Подстановка системы уравнений-ограничений (знак

0 ) в W даёт:

Wmin=3460+7x1-4x2=> min.

Таблица 17

Для поиска зависимых переменных

1	2	3	4
А	х11	х12	Х13	320
В	х21	х22	X23	380
bj	200	230	220	700

В итоге была получена следующая задача линейного программирования в неравенствах (Табл 17).

Таблица 18

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

х1 0 и х2 0
320-(х1+х2) 0	х3=f3(x1;x2)
200-х1 0	х4=f4(x1)
280-х2 0	х5=f5(x2)
х1+х2-100 0	х6=f6(x1;x2)
Wmin=3880+4х1-2х2	W=fw(x1;x2)

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

Третья модель. Геометрическое решение задачи.

В случае двух независимых переменных поиск точки решения, соответствующей Wmin, нагляднее произвести методами алгебраической геометрии в топологии Евклида.

С этой целью воспользуемся декартовой системой координат (х1;х2).

На рис.7 приведена область допустимых решений, определённая неравенствами уравнений-ограничений.

Выделена точка х

, соответствующая Wmin . Определено значение Wmin (х )=2340 усл.ед. Решение, полученное на модели 3, совпадает с решением, полученным на модели 1.

Рис.7. Задача «Бетон»: топология на графе и в проекции

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

4.1.4 Свойства задач линейного программирования.

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

Уравнения – ограничения определяют область допустимых решений(ОДР).

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

Из линейности граней и выпуклости ОДР, линейности w вытекает следующие свойства ЗЛП [2]:

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

· Решение отсутствует, если ОДР не ограничена в направлении перемещения опорной поверхности.

· В невырожденном случае в вершине ОДР все свободные переменные равны нулю, число свободных переменных определяется мерностью пространства представления ОДР.

· В вырожденном случае число равных нулю переменных в вершине ОДР больше числа свободных переменных.

· Множество переменных естественно разбивается на два подмножества: свободные и базовые. Поисковые методы решения в случае многомерных пространств ориентированы на невырожденный случай ЗЛП и процесс поэтапной замены свободных переменных на базовые.

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

Симплекс-метод представляет собой организацию процедуры поиска решения путем перемещения от опорной вершины, принадлежащей ОДР, к соседствующей с ней вершиной в сторону оптимальной вершины путём одношаговых замен одной из свободных переменных на одну из базовых вплоть до выполнения критерия эффективности [2].

4.2.1 Иллюстрация процесса поиска решения.

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

Дано: ЗЛП в виде алгебраической модели системы уравнений ОДР:

- общее условие допустимости решений, где при х1=х2=0 имеем: х1=х2=0; х3=320;х4=200;х5=280;х6=-100;

W=3460.

Согласно условиям, т.к. х<0 (равно -100), то решение в точке (0,0) – начало координат на рис.8 - не является допустимым. Точка (0,0) не принадлежит области допустимых решений:

{(x1;x2)=(0,0)}

.

Рис.8. Схема ЗЛП

Далее рассуждения ведутся согласно принятой разметке ОДР в симплексах ОДР.

Итак, чтобы получить допустимое решение необходимо из точки «0» прейти в одну из точек симплекса {Ai;Bi; или Ci}, где

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

А1:х2=х6=0;

А2:х1=х6=0

В1:х2=х4=0

В2:х1=х5=0

С1:х3=х4=0

С2:х3=х5=0

Переходим из точки «0», где х1=х2=0 в любую из точек {A1;A2;B1;B2} соответствует правилу замены одной свободной переменной на одну базовую[2].

На Рис.9 показаны возможные пути перехода при решении задачи ЛП, соответствующие замене одной свободной переменной на одну базовую.

Рис.9. Смежность точек по свойству «замена только одной

свободной переменной»

Очевидно, имеются 4 допустимых маршрута перехода из точки «0» в оптимальную точку (симплекс-вершину)

:

2……6 6…..5

1) 0 А2

2…..5

2) 0