Реферат Математичне програмування

Страница 1 из 2 | Следующая страница

>Завдання 1

При продаж двохвидівтоварів (А й У)торговепідприємствовикористовуєчотиривидиресурсів.Норми витратресурсів на 1 од. товару,об’ємресурсівнаведені втаблиці.Дохід відреалізації 1 од. товару Аскладає 2 грн., товару У – 3 грн.

>Ресурси Нормавитратресурсів на 1 од. тов. Запасресурсів
А У
1 2 2 12
2 1 2 8
3 4 0 16
0 0 4 12
>Дохід, грн. од. 2 3

>Визначитиоптимальний планреалізаціїтоварів, щозабезпечує для торгового підприємствамаксимальнийприбуток.

>Розв’язок

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

=2х1+3х2.

>Витратиресурсів при продажтакоїкількостітоварівскладаютьвідповідно:

CI =>2х1 +2х2,

>CII =1х1 +2х2,

>CIII =>4х1 +0х2,

>CIV =>0х1 +4х2,

Ос-кількизапасиресурсівобмежені, топовиннівиконуватисьнерівності:

>2х1 +2х2 12

1х1 +2х2 8

>4х1 16

>4х2 12

Ос-кільки,кількістьтоварівє величинаневід'ємна, тододатковоповиннівиконуватисьщенерівності:х1> 0,х2> 0.

Таким чином,приходимо доматематичноїмоделі (>задачілінійногопрограмування):

>Знайтих1 ,х2такі, щофункція =2х1+3х2досягає максимуму присистеміобмежень:

>Вирішимопряму завданнялінійногопрограмуваннясимплексним методом, ізвикористаннямсимплексноїтаблиці.

>Визначимомаксимальнезначенняцільовоїфункції F (X) =2x1 +3x2 за такихумов-обмежень.

>2x1 +2x212

>x1 +2x28

>4x116

>4x212

Дляпобудови Першого опорного плану системунерівностейприведемо досистемирівнянь шляхомвведеннядодатковихзмінних (>перехід доканонічноїформи). Ос-кільки маємозмішаніумови-обмеження, товведемоштучнізмінні x.

>2x1 +2x2 +1x3 +0x4 +0x5 +0x6 = 12

>1x1 +2x2 +0x3 +1x4 +0x5 +0x6 = 8

>4x1 +0x2 +0x3 +0x4 +1x5 +0x6 = 16

>0x1 +4x2 +0x3 +0x4 +0x5 +1x6 = 12

>Матрицякоефіцієнтів A =a(ij)цієїсистемирівняньмаєвигляд:

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

 >Вирішимо системурівняньвідноснобазиснихзмінних:

>x3,x4,x5,x6,

 >Вважаючи, щовільнізміннірівні 0,отримаємо Першіопорний план:

>X1 = (0,0,12,8,16,12)

План  >Базис  B  >x1  >x2  >x3  >x4  >x5  >x6
 0  >x3  12  2  2  1  0  0  0
   >x4  8  1  2  0  1  0  0
   >x5  16  4  0  0  0  1  0
 >x6  12  0  4  0  0  0  1
>Індексний ряд  >F(X0)  0  -2  -3  0  0  0  0

>Переходимо до основного алгоритмусимплекс-методу.

План >Базис B  >x1  >x2  >x3  >x4  >x5  >x6  >min
 1  >x3  12  2  2  1  0  0  0  6
   >x4  8  1  2  0  1  0  0  4
 >x5  16  4  0  0  0  1  0  -
 >x6  12  0  4  0  0  0  1  3
>Індексний ряд  >F(X1)  0  -2  -3  0  0  0  0  0

>Поточнийопорний планнеоптимальний, бо віндексному рядкузнаходятьсянегативнікоефіцієнти.

Уякостіведучоговиберемостовпець,відповідноїзмінноїx2, боценайбільшийкоефіцієнт по модулю.

>ОбчислимозначенняDi порядках якчастку відділення:

й із нихвиберемонайменше:

>min (12 : 2 , 8 : 2 , - , 12 : 4 ) = 3

Отже,4-ий рядєпровідним.

>Дозвільнийелементдорівнює (4) йстоїть наперетиніведучогостовпця й головного рядка.

>Формуємонаступнучастинусимплексноїтаблиці.

>Замістьзмінної x до плану 1Замістьзмінноїx2 .

>Рядок,відповідноїзмінноїx2 впланi 1,отриманий врезультатіподілу всіхелементів рядкаx6 плану 0 надозвільнийелементДE=4

Намісцідозвільногоелемента одинотримуємо 1.

Уіншихклітинахстовпцяx2 плану 1записуємонулі.

Таким чином, у новомуплані 1заповнені рядx2 йстовпецьx2 .

>Всііншіелементи нового плану 1,включаючиелементиіндексного рядка,визначаються за правиломпрямокутника.

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

>НE =СE - (>А*В)/ДE

>СДE -елемент старого плану, ДЕ -дозволяєелемент (4), А і У -елементи старого плану, щоутворюютьпрямокутник ізелементамиСДЕ йДE.

План >Базис B  >x1  >x2  >x3  >x4  >x5  >x6  >min
 2  >x3  6  2  0  1  0  0  -1/2  3
   >x4  2  1  0  0  1  0  -1/2  2
   >x5  16  4  0  0  0  1  0  4
   >x2  3  0  1  0  0  0  1/4  -
 >Індексний ряд  >F(X2)  9  -2  0  0  0  0  3/4  0

>Поточнийопорний планнеоптимальний, бо віндексному рядкузнаходятьсянегативнікоефіцієнти.

Уякостіведучоговиберемостовпець,відповідноїзмінноїx1, Так якценайбільшийкоефіцієнт по модулю.

>ОбчислимозначенняDi порядках якчастка відділення:

й із нихвиберемонайменше:

 >min (6 : 2 , 2 : 1 , 16 : 4 , - ) = 2

 Отже,2-ий рядєпровідним.

>Дозвільнийелементдорівнює (1) йстоїть наперетиніведучогостовпця йголовною рядка.

>Формуємонаступнучастинусимплексноїтаблиці.

>Замістьзмінної x до плану 2Замістьзмінноїx1 .

>Рядок,відповідноїзмінноїx1 впланi 2,отриманий врезультатіподілу всіхелементів рядкаx4 плану 1 надозвільнийелементДE=1

Намісцідозвільногоелемента у дваотримуємо 1.

Уіншихклітинахстовпцяx1 плану 2записуємонулі.

Таким чином, у новомуплані 2заповнені рядx1 йстовпецьx1 .

>Всііншіелементи нового плану 2,включаючиелементиіндексного рядка,визначаються за правиломпрямокутника.

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

>НE =СE - (>А*В)/ДE

>СДE -елемент старого плану, ДЕ -дозвільнийелемент (1), А і У -елементи старого плану, щоутворюютьпрямокутник ізелементамиСДЕ йДE.

Ос-кільки востанньомустовпціприсутнікількамінімальнихелементів 4, то номер рядкавибираємо за правиломКрек.

МетодКрекполягає внаступному.Елементирядків, щомаютьоднаковінайменшізначенняmin=4,діляться напередбачуванідозвільніелементи, арезультатизаносяться вдодаткові рядки. Запровідний рядвибирається тієї, вякомуранішезустрінетьсянайменшеприватне причитаннітаблицізліва направо постовпцях.

План >Базис  B  >x1  >x2  >x3  >x4  >x5  >x6  >min
 3  >x3  2  0  0  1  -2  0  1/2  4
   >x1  2  1  0  0  1  0  -1/2  -
   >x5  8  0  0  0  -4  1  2  4
   >x2  3  0  1  0  0  0  1/4  12
 >Індексний ряд  >F(X3)  13  0  0  0  2  0  -1/4  0

>Поточнийопорний планнеоптимальний, бо віндексному рядкузнаходятьсянегативнікоефіцієнти.

Уякостіведучоговиберемостовпець,відповіднийзмінноїx6, боценайбільшийкоефіцієнт по модулю.

>ОбчислимозначенняDi порядках якчастку відділення:

й із нихвиберемонайменше:

 >min (2 : 1/2 , - , 8 : 2 , 3 : 1/4 ) = 4

Отже,1-ий рядєпровідним.

>Дозвільнийелементдорівнює (1/2) йстоїть наперетиніведучогостовпця йголовною рядка.

>Формуємонаступнучастинусимплексноїтаблиці.

>Замістьзмінної x до плану 3Замістьзмінноїx6 .

>Рядок,відповідноїзмінноїx6 вплані 3,отриманий врезультатіподілу всіхелементів рядкаx3 плану 2 надозвільнийелементДE=1/2

Намісцідозволяєелемента вплані 3отримуємо 1.

Уіншихклітинахстовпцяx6 плану 3записуємонулі.

Таким чином, у новомуплані 3заповнені рядx6 йстовпецьx6 .

>Всііншіелементи нового плану 3,включаючиелементиіндексного рядка,визначаються за правиломпрямокутника.

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

>НE =СE - (>А*В)/ДE

>СДE -елемент старого плану, ДЕ -дозвільнийелемент (1/2), А і У -елементи старого плану, щоутворюютьпрямокутник ізелементамиСДЕ йДE.

Ос-кільки,індексний ряд неміститьнегативнихелементів -знайденийоптимальний план.

>Остаточнийваріантсимплекс-таблиці:

План >Базис  B  >x1  >x2  >x3  >x4  >x5  >x6
 4  >x6  4  0  0  2  -4  0  1
   >x1  4  1  0  1  -1  0  0
   >x5  0  0  0  -4  4  1  0
   >x2  2  0  1  -1/2  1  0  0
>Індексний ряд  >F(X4)  14  0  0  1/2  1  0  0

>Оптимальний план можназаписати так:

>x6 = 4

>x1 = 4

>x5 = 0

>x2 = 2

>F(X) = 2•4 + 3•2 = 14


>Завдання 2

>Розв’язатизадачі:

а)графічним методом;

б) методомсимплекснихтаблиць;

в)скластидвоїсту завдання йрозв’язатиїї.

>Розв’язок

>Розв’язокграфічним методом.

>Побудуємо областьдопустимихрішень,тобтовирішимографічно системунерівностей. Для цогопобудуємокожнупряму йвизначимопівплощини,заданінерівностями (>півплощинипозначені штрихом).


>Межіобласті

>ЦільовафункціяF(x) =>min

>Розглянемоцільовуфункцію заподіяння F =7X1+5X2 =>min.

>Побудуємопряму, щовідповідаєзначеннюфункції F = 0: F =7X1+5X2 = 0.Будеморухатицюпрямупаралельним чином. Ос-кільки насцікавитьмінімальнерішення, томурухався прямо до Першоготорканняпозначеноїобласті. Награфікуця прямапозначенапунктирноюлінією.

>Рівний масштаб


>Перетиномпівплощини якщо область, Якапредставляє собоюбагатокутник,координатиточокякогозадовольняютьумовінерівностейсистемиобмеженьзадачі.

ПрямаF(x) =constперетинає область уточці A. Ос-кільки точка Aотримана врезультатіперетинупрямих 4 і 3, тоїїкоординатизадовольняютьрівняннямцихпрямих:

>x2=0

>3x1-5x211

>Вирішивши системурівнянь, одержимо:x1 = 3.6667,x2 = 0

>Звідкизнайдемомінімальнезначенняцільовоїфункції:

>F(X) = 7*3.6667 + 5*0 = 25.67

>Розв’язок методомсимплекснихтаблиць.

>Вирішимопряму завданнялінійногопрограмуваннясимплексним методом, ізвикористаннямсимплексноїтаблиці.

>ВизначимомінімальнезначенняцільовоїфункціїF(X) =7x1+5x2 за такихумов-обмежень.

>2x1+4x21

>5x1-x242

>3x1-5x211

Дляпобудови Першого опорного плану системунерівностейприведемо досистемирівнянь шляхомвведеннядодатковихзмінних (>перехід доканонічноїформи).

>2x1 +4x2-1x3 +0x4 +0x5 = 1

>5x1-1x2 +0x3 +1x4 +0x5 = 42

>3x1-5x2 +0x3 +0x4-1x5 = 11

>Введемоштучнізмінні x.

>2x1 +4x2-1x3 +0x4 +0x5 +1x6 +0x7 = 1

>5x1-1x2 +0x3 +1x4 +0x5 +0x6 +0x7 = 42

>3x1-5x2 +0x3 +0x4-1x5 +0x6 +1x7 = 11

Для постановки заподіяння намінімумцільовуфункціюзапишемо так:

>F(X) =7x1+5x2+Mx6+Mx7 =>min

>Отриманий базисназиваєтьсяштучним, а методрішенняназивається методом штучного базису.

>Причомуштучнізмінні немають ставлення дозміступоставленого заподіяння,однак смердотідозволяютьпобудуватистартову точку, а процесоптимізаціїзмушуєцізмінніприйматинульовізначення та забезпечитидопустимість оптимальногорішення.

Зрівняньвисловлюємоштучнізмінні:

>x6 =1-2x1-4x2+x3

>x7 =11-3x1+5x2+x5

котріпідставимо вцільовуфункцію:

>F(X) =7x1 +5x2 +M(1-2x1-4x2+x3) +M(11-3x1+5x2+x5) =>min

чи

>математичний модельлінійнийпрограмування

>F(X) = (>7-5M)x1+(5+1M)x2+(1M)x3+(1M)x5+(12M) =>min

>Матрицякоефіцієнтів A =a(ij)цієїсистемирівняньмаєвигляд:

 2  4  -1  0  0  1  0
 5  -1  0  1  0  0  0
 3  -5  0  0  -1  0  1

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

>Вирішимо системурівняньвідноснобазиснихзмінних:

>x6,x4,x7,

>Вважаючи, щовільнізміннірівні 0,отримаємопершийопорний план:

>X1 = (0,0,0,42,0,1,11)

План >Базис У >x1 >x2 >x3 >x4 >x5 >x6 >x7
 0  >x6  1  2  4  -1  0  0  1  0
   >x4  42  5  -1  0  1  0  0  0
   >x7  11  3  -5  0  0  -1  0  1
 >Індексний ряд  >F(X0)  >12M  ->7+5M  ->5-1M  ->1M  0  ->1M  0  0

>Переходимо до основного алгоритмусимплекс-методу.

План >Базис  У  >x1  >x2  >x3  >x4  >x5  >x6  >x7  >min
 1  >x6  1  2  4  -1  0  0  1  0  0.5
 >x4  42  5  -1  0  1  0  0  0  8.4
   >x7  11  3  -5  0  0  -1  0  1  3.67
>Індексний ряд  >F(X1)  >12M  ->7+5M  ->5-1M  ->1M  0  ->1M  0  0  0

>Поточнийопорний планнеоптимальний, бо віндексному рядкузнаходятьсяпозитивнікоефіцієнти

Уякостіведучоговиберемостовпець,відповідноїзмінноїx1, так якценайбільшийкоефіцієнт .

>ОбчислимозначенняDi порядках якчастку відділення

й із нихвиберемонайменше:

Отже,1-ий рядєведучим

>Дозвільнийелементдорівнює 2 йзнаходиться наперетиніведучогостовпця йголовною рядка

>Формуємонаступнучастинусимплексноїтаблиці.

>Замістьзмінноїx6 до плану 1увійдезміннаx1

>Рядок,відповідноїзмінноїx1 один,отриманий врезультатіподілу всіхелементів рядкаx6 плану 0 надозвільнийелементДЕ=2

Намісцідозвільногоелемента одинотримуємо 1.

Уіншихклітинахстовпцяx1 плану 1записуємонулі.

Таким чином, у новомуплані 1заповнені рядx1 йстовпецьx1 .

>Всііншіелементи нового плану 1,включаючиелементиіндексного рядка,визначаються за правиломпрямокутника.

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

>НE =СE - (>А*В)/ДE

>СДЕ -елемент старого плану, ДЕ -дозвільнийелемент (2), А й У -елементи старого плану, щоутворюютьпрямокутник ізелементамиСДЕ й ДЕ.

План  >Базис  У  >x1  >x2  >x3  >x4  >x5  >x6  >x7  >min
 2  >x1  0.5  1  2  -0.5  0  0  0.5  0  0
   >x4  39.5  0  -11  2.5  1  0  -2.5  0  15.8
   >x7  9.5  0  -11  1.5  0  -1  -1.5  1  6.33
>Індексний ряд  >F(X2)  >3.5+9.5M  0  >9-11M  ->3.5+1.5M  0  ->1M  >3.5-2.5M  0  0

>Поточнийопорний планнеоптимальний, бо віндексному рядкузнаходятьсяпозитивнікоефіцієнти

Уякостіведучоговиберемостовпець,відповідноїзмінноїx3, так якценайбільшийкоефіцієнт .

>ОбчислимозначенняDi порядках якчастку відділення

й із нихвиберемонайменше:


Отже,3-ий рядєведучим

>Дозвільнийелементдорівнює 1.5 йзнаходиться наперетиніведучогостовпця йголовною рядка

>Формуємонаступнучастинусимплексноїтаблиці.

>Замістьзмінноїx7 до плану 2увійдезміннаx3

>Рядок,відповідноїзмінноїx3 у два,отримана врезультатіподілу всіхелементів рядкаx7 плану 1 надозвільнийелементДЕ=1.5

Намісцідозвільногоелемента у дваотримуємо 1.

Уіншихклітинахстовпцяx3 плану 2записуємонулі.

Таким чином, у новомуплані 2заповнені рядx3 йстовпецьx3 .

>Всііншіелементи нового плану 2,включаючиелементиіндексного рядка,визначаються за правиломпрямокутника.

>Кінецьітерацій:індексний ряд неміститьнегативнихелементів -знайденийоптимальний план

>Остаточнийваріантсимплекс-таблиці:

План >Базис У  >x1  >x2  >x3  >x4  >x5  >x6  >x7
 3  >x1  3.67  1  -1.67  0  0  -0.3333  0  0.3333
   >x4  23.67  0  7.33  0  1  1.67  0  -1.67
 >x3  6.33  0  -7.33  1  0  -0.6667  -1  0.6667
 >Індексний ряд  >F(X3)  25.67  0  -16.67  0  0  -2.33  ->1M  >2.33-1M

>Оптимальний план можназаписати так:

>x1 = 3.67

>x4 = 23.67

>x3 = 6.33

>F(X) = 7*3.67 = 25.67

>Складемодвоїсту завдання допрямоїзадачі.

>2y1+5y2+3y37

>4y1-y2-5y35

>y1+42y2+11y3 =>max

>y1 0

>y2

Страница 1 из 2 | Следующая страница

Схожі реферати:

Нові надходження

Замовлення реферату

Реклама

Навігація