Графическое решение задачи

Это решение рассмотрим на примере расчета использования грузоподъемности и грузовместимости судна. Сущность этой задачи состоит в определении такого количества груза q₁ и q₂, которое позволяет использовать чистую грузоподъемность Д(чистая) и грузоподъемность судна W.

В зависимости от цели и ограничений постановка задач может иметь различный вид.

Определение количества грузов для полного использования грузоподъемности – грузовместимости без учета фрахта за их перевозку, ведется путем совместного решения 2-х уравнений:

                                                                         (2.2.1.)

u₁ и u₂ – удельный погрузочный объем, объем занимаемый 1 т. груза

Пример:

D=1000т

W=1500 м³

q₁=1000-q₂

0,5(1000-q₂)+2q₂=1500

500-0,5q₂+2q₂=1500

500+1,5q₂=1500

1,5q₂=1000

q₂=667т

q₁=1000-667=333 т

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

Расчет оптимального использования грузоподъемности и грузовместимости осуществляется методом линейного программирования. При этом математическая модель задачи для двух грузов будет иметь вид:

1) q₁+q₂ £D_ч– ограничения по грузоподъемности                            (2.2.2.)

2) u₁q₁+u₂q₂£W – ограничения по грузовместимости (по объему) (2.2.3.)

ограничение по количеству отдельных грузов (2.2.4.)

или

ограничение по объему отдельных грузов (2.2.5.)

7) L=C₁q₁+C₂q₂Þmax (min)                                                                   (2.2.6.)

C₁ и C₂ – затраты по перевозке 1 т. груза при решении задачи на min;

C₁ и C₂ – оценка фрахта тонны перевозимого груза при решении задач на max.

Для графического решения задачи выбираем масштаб построения и в прямоугольной системе координат q₁ и q₂ производятся следующие построения.

Заменяют во всех ограничениях знаки неравенства на знаки равенства и в заданном масштабе строят линии соответствующие этим равенствам. Первых два неравенства дают наклонение линии 1 и 2 (рис.2).

 

 

Рис. 2.2 Определение области допустимых решений (ОДР)

 

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

Любая точка в пределах этой области или на ее границах имеет такое значение q₁ и q₂ , которые удовлетворяют исходным условиям задачи.

Для отыскания точки в ОДР для которой целевая функция L будет max(min) первоначальной величине L предписывают положительное число. Используя это число по уравнению L строят предварительную линию, чтобы получить направление целевой функции в системе координат q₁ и q₂: на рис.2. это линия L¢. Оптимальное решение задачи находят перемещая параллелью самой себе линию целевой функции до самой удаленной от начала координат точки ОДР, если L®max, или наоборот.

Координаты найденной точки и есть оптимальное решение задачи, т.е. найденные величины q ₀₁ и q ₀₂ показывают то количество грузов при котором не нарушаются требования исходных ограничений, а целевая функция достигает max или min. На рис. 2. это линии L= max и L= min соответственно.

Значение q ₀₁ и q ₀₂ показывает количество грузов при перевозке которых выполняются все условия заложенные в модель задачи и судно будет давать наилучшие показатели работы при данных условиях.

Наглядность графического решения позволяет проанализировать при каких изменениях условий работы возможно получение лучших результатов, чем допустимых по данным условиям. При этом ограничения, участвующие в формировании ОДР называются существенными. Поэтому при данных значениях коэффициентов L в первую очередь следует рассмотреть влияние тех линий (ограничений), которые пересекаются в точке – оптимального решения. Поскольку наклон линии целевой функции L зависит от коэффициентов С₁ и С₂, то отклонение этой линии от границ ОДР показывает, что при некотором изменении С₁ и С₂ оптимальное решение не изменится.

 

Пример использования графического метода решения

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

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

Рассмотрим применение этого метода на примере расчета оптимальной загрузки судна двумя видами груза.

Введем следующие обозначения:

q₁,q₂ - количество принимаемых к перевозке грузов, в тоннах.

u₁,u₂ - удельная грузовместимость, в м³/тонну.

Dч- чистая грузоподъемность судна, в тоннах.

W- объем грузового помещения судна (грузовместимость), в м³ .

C₁,C₂ - стоимость фрахта за перевозку одного груза, в [у. е.].

Математическая модель задачи:

 

L=S Ci*Xi ® max                                    (2.3.1.)

Ограничения:

по грузовместимости судна: q₁ + q₂ £ Dч                             (2.3.2.)

по грузоподъемности судна: q₁ u₁ + q₂ u₂ £ W                        (2.3.3.)

 

по массе отдельных грузов: Q_1min   £ q₁ £ Q_1max                               (2.3.4.)

Q_2min £ q₂ £ Q_2max

 

по объему отдельного вида груза:

W_1min £ u₁ q₁ £ W_1max                                                                (2.3.5.)

W_2min £ u₂ q₂  £ W_2max

 

Задача решается следующим образом. В декартовой системе координат q₁ , q₂ , выбирается масштаб построения. На положительной части q₁, q₂ , обозначаются линии, соответствующие границам неравенств, для чего неравенство превращаем в равенство (т. е. q₁ + q₂ £ Dч ® q₁ + q₂ = Dч , и так со всеми остальными неравенствами). На линиях границ обозначим область, удовлетворяющую соответствующим неравенствам. Определим область допустимых решений. Любая точка в ОДР имеет координаты удовлетворяющие условиям задачи.

Для определения оптимальных значений q₁ и q₂ строят направление целевой функции L, и приравнивают её к любому положительному числу. Построя направление L, перемещаем её параллельно самой себе до соприкосновения с самой отдаленной от начала построения точкой ОДР. Координаты этой точки дают оптимальное решение q_o1, q_o2. После определения q_o1, q_o2 анализируется полученный результат.

Рассмотрим конкретный пример оптимальной загрузки судна двумя видами груза.

Dч =1000тонн

W =1500м³

u₁ = 0,8 м³/тонн                u₂ = 2,5 м³/тонн

Q_1min=200 тонн                 Q_2min= 300 тонн

Q_!max=500 тонн                 Q_2max= 800 тонн

W_1min=---- м³                      W_2max=----- м³

W_1min=---- м³                                        W_2max-=---- м³

C₁= 10 у.е./т                      C₂= 20 у.е./т

где / ---- / - означает "нет ограничения".

 

q_o1+ q_o2 <1000                                                                            (2.3.6.)

0,8q_o1+2,5q_o2 <1500                                                                   (2.3.7.)

200£ q_o1 £ 500                                                                          (23.8.)

300 £ q_o2 £ 800                                                                     (2.3.9.)

 

Математическая модель полной загрузки судна представлена уравнениями (2.3.6.) и (2.3.7.). Решая эти уравнения совместно, найдем количество груза обоих видов, обеспечивающих полную загрузку:

 

 

                       

 

                      

 

Таким образом, для полного использования и грузовместимости судна, на борт необходимо погрузить 588,235 тонн первого груза q_o1 и 411,765 тонн второго груза q_o2. То есть:

q_o1 = 588,235 т

q_o2 = 411,765 т

При этом значение целевой функции будет следующим:

 

L₁ = S Ci*Xi = C₁ * q₁+ C₂ * q₂ = 10*588,235+20*411,765 = 14117,65 у.е.

Далее производим следующее: наносим оси q₁ и q₂  в декартовой системе координат; выбираем масштаб построения одинаковый для обеих осей; превращаем неравенства 2.3.6.-2.3.9. в равенства, которые представляют собой уравнения прямых:

 

    q_o1+ q_o2 =1000                                                                  (2.3.10.)

    0,8q_o1+2,5q_o2 =1500                                                         (2.3.11.)

    200 = q_o1 = 500                                                                (2.3.12.)

    300 = q_o2 = 800                                                                 (2.3.13.)

Затем строим эти прямые в декартовой системе и находим область, удовлетворяющую соответствующим неравенствам 2.2.6.-2.2.9. Эта область и является Областью Допустимых Решений (ОДР), любая точка которой удовлетворяет условиям задачи.

Целевую функцию L = S Ci*Xi = C₁ * q₁+ C₂ * q₂ приравниваем к любому положительному числу – в нашем случае:

Lопт_х = 10 * q₁+ 20 * q₂ = 1000,

и строим эту прямую. Потом перемещаем ее параллельно самой себе до прикосновения с самой отдаленной от начало построения точкой – в нашем случае это точка "А". Координаты этой точки "А" дают оптимальное решение q_o1, q_o2. Сняв значения q_o1, q_o2 , анализируем полученный результат. Для этого находим значение целевой функции при полученных q_o1, q_o2:

q_o1 = 500 т

q_o2  = 440 т

L опт = S Ci*Xi = C₁ * q₁+ C₂ * q₂ = 10*500 + 20*440 =13800 у.е.

Как видно из полученного решения, L₁ , равное 14117,65 у.е., больше чем Lопт , равное 13800 у.е., на 317,65 у.е. Это означает, что загрузка судна по Lопт менее выгодна, так как грузовместимость используется полностью, а грузоподъемность еще остается в запасе, что и отражается на величине дохода.

Определяющим ограничением в нашем случае является Q_1max = 500 т. Если его исключить, то можно подобрать такое решение, при котором можно принять на борт такое сочетание груза q₁ и q₂ , чтобы добиться оптимального использования грузовместимости и грузоподъемности.

Максимально возможное значение целевой функции без ограничений находится в точке В, при q₁=588,235т и q₂=411,465т, то есть в том случае когда мы оптимально используем и грузовместимость и грузоподъемность судна. Значение целевой функции в точке В:

L=14117,65 у.е.

При увеличении или уменьшении стоимости С₁ и С₂ в 10-ть раз (С₁ = 100 у.е. и 1 у.е., С₂ = 200 у.е. и 2 у.е.) наклон прямой Lопт заметно не изменится, следовательно, найвыгоднейшие условия загрузки будут описываться прежней точкой ОДР и величины q_o1 и q_o2 останутся прежними, изменится лишь значение Lопт.

При С₁ = 100 у.е. и С₂ = 200 у.е.: Lопт_увел. = 100*500 + 200*440 = 138000 у.е.

При С₁ = 1 у.е. и С₂ = 2 у.е.:      Lопт_умен. = 1*500 + 2*440 = 1380 у.е.

При перемене стоимости С₁ и С₂ наоборот, то есть С₁ = 20 у.е. и С₂ =10 у.е. наклон прямой Lопт изменится и значение целевой функции возрастет до

Lопт = C₁ *q_o1 + C₂ *q_o2 = 20*500 + 10*440 = 14400 у.е.

Графическое решение задачи представлено на рис.3.

 

 

⇐ Предыдущая9101112131415161718Следующая ⇒

Поделиться: