Лiнiйне програмування

ЛАБОРАТОРНА РОБОТА 2

ЛІНІЙНЕ ПРОГРАМУВАННЯ

Студентки групи ОФПД 2-1

варвлепаовр

Умова задачі. Для виробництва двох видів продукції (П1 і П2) використовується три види сировини (С1, С2, С3), щодо кожної з яких підприємство має відповідні запаси. Їх величина, як і обсяг витрат сировини на виробництво одиниці продукції кожного виду, наведені в табл. 1. При реалізації одиниці продукції П1 підприємство отримує прибуток в розмірі Р1 умовних грошових одиниць, а продукції П2 – Р2 умовних грошових одиниць.

Необхідно оптимізувати план виробництва продукції таким чином, щоб підприємство отримало максимальний прибуток від її реалізації; побудувати відповідну економіко-математичну модель та розв’язати задачу лінійного програмування графічним методом.

Постановка задачі лінійного програмування та побудова економіко-математичної моделі. Припустимо, що х1 і х2 – це обсяг виробництва двох видів продукції П1 і П2, який, логічно, не можу бути від’ємним.

1). Цільову функцію – максимізацію прибутку від реалізації продукції – математично записуємо як:

Z= 12х1 + 9х2        max[pic 1]

2) В задачі існує один тип обмежень – запас сировини на виготовлення двох видів продукції:

Запас сировини  С1:

 х1  +  х2 ≤ 37

Запас сировини  С2:

1х1  + 4х2  ≤ 360

Запас сировини  С3:

х1  + 4х2  ≤ 100

Крім обмежень, висувається умова невід’ємності змінних (обсягів виробництва полиць):

х1 ≥ 0

х2 ≥ 0

Таким чином, економіко-математична модель задачі лінійного програмування в даному випадку матиме вигляд:

Z= 12х1 + 9х2        max[pic 2]

   х1  +  х2 ≤ 37[pic 3]

 12х1  + 5х2  ≤ 360

    х1  + 4х2  ≤ 100

    х1 ≥ 0  , х2 ≥ 0

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

 Перше обмеження   х1  +  х2 ≤ 37перетворюємо на рівняння виду:  х1  +  х2 = 37  (гранична пряма L1). Прирівнюємо х1 до нуля, тоді 1*0 + 1*х2 = 37, звідки х2 = 54. Маємо координати однієї точки прямої L1, а саме: (0;54). Потім приймаємо за нуль х2 і визначаємо х1: 11·х1 + 6·0 = 324, звідки х1 = 29,5. Отже, координати другої точки прямої L1 – (29,5;0).

Друге  обмеження   12х1  + 5х2  ≤ 360 перетворюємо на рівняння виду:   12х1  + 5х2  ≤ 360 (гранична пряма L2). Прирівнюємо х1 до нуля, тоді 12·0 + 5·х2 = 360, звідки х2 = 72. Маємо координати однієї точки прямої L2, а саме: (0;72). Потім приймаємо за нуль х2 і визначаємо 12х1  + 5х2  ≤ 360, звідки х1 = 0. Отже, координати другої точки прямої L2 – (72;0).

Третє   обмеження       х1  + 4х2  ≤ 100 перетворюємо на рівняння виду:   х1  + 4х2  = 100 (гранична пряма L3). Прирівнюємо х1 до нуля, тоді 1·0 + 4·х2 = 100, звідки х2 = 25. Маємо координати однієї точки прямої L3, а саме: (0;25). Потім приймаємо за нуль х2 і визначаємо х1: 1·х1 + 4·0 = 100, звідки х1 = 60 Отже, координати другої точки прямої L3 – (60;0).

Прямі  L4 та L5  відповідають осям координат, а саме : L4  (х1), а L5   (х2 ).

Графіки відповідних прямих зображено на рис. 1.

Знаходимо півплощини розв’язків, що відповідають нерівностям системи обмежень. Умови невід’ємності змінних х1 ≥ 0 і х2 ≥ 0 автоматично обмежують область допустимих значень правим верхнім квадрантом системи координат (рис. 1).