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

МАТЕМАТИЧНЕ ПРОГРАМУВАННЯ В MAPLE

Частина ІІ

Двоїсті та цілочислові задачі лінійного програмування

 

 

Міністерство освіти і науки, молоді та спорту України

Вінницький національний технічний університет

 

 

В. М. Михалевич, О. І. Тютюнник

 

МАТЕМАТИЧНЕ ПРОГРАМУВАННЯ В MAPLE

Частина ІІ

ДВОЇСТІ ТА ЦІЛОЧИСЛОВІ ЗАДАЧІ ЛІНІЙНОГО ПРОГРАМУВАННЯ

 

Навчальний посібник

 

Вінниця

ВНТУ

УДК 519.85+681.3.05(075)

ББК 22.18+32.973.26-018.2я73

М69

 

Рекомендовано до друку Вченою радою Вінницького національного технічного університету Міністерства освіти і науки, молоді та спорту України (протокол №10 від 30.05.2012 р.)

 

 

Рецензенти:

Ф. М. Сохацький, доктор фізико-математичних наук, професор

В. І. Клочко, доктор педагогічних наук, професор

О. М. Роїк, доктор технічних наук, професор

О. В. Мороз, доктор економічних наук, професор

 

Михалевич, В. М.

М69 Вища математика. Математичне програмування в Maple. Частина IІ. Двоїсті та цілочислові задачі лінійного програмування: навчальний посібник. – Вінниця: ВНТУ, 2012. – 79 с.

Подано теоретичні відомості з окремих тем: двоїстісті задачі лінійного програмування, двоїстий симплекс-метод, цілочислове програмування. Особливість посібника полягає в широкому використанні системи комп’ютерної математики Maple для висвітлення основних понять, ідей та методів, що розглядаються. Дано стислий опис пакетів розширення Maple для розв'язування задач лінійного програмування.

Розрахований на студентів технічних та економічних ВНЗ усіх форм навчання та спеціальностей.

УДК 519.85+681.3.05(075)

ББК 22.18+32.973.26-018.2я73

 

 

© В. Михалевич, О.Тютюнник, 2012

ЗМІСТ

ЗМІСТ. 3

ПЕРЕДМОВА.. 4

1 ЗАГАЛЬНА ПОСТАНОВКА ТА ФОРМИ ЗАПИСУ ЗАДАЧ ЛІНІЙНОГО ПРОГРАМУВАННЯ.. 6

2 ДВОЇСТІСТЬ У ЗАДАЧАХ ЛІНІЙНОГО ПРОГРАМУВАННЯ.. 11

2.1 Двоїсті задачі в симетричній формі 13

2.2 Загальні правила складання двоїстих задач. 15

2.3 Основні властивості та теореми двоїстості 18

2.4 Геометрична інтерпретація двоїстих задач. 20

2.5 Зв’язок між розв’язками прямої і двоїстої задач лінійного програмування 22

3 ДВОЇСТИЙ СИМПЛЕКС-МЕТОД.. 29

4 ЦІЛОЧИСЛОВІ ЗАДАЧІ ЛІНІЙНОГО ПРОГРАМУВАННЯ.. 39

4.1 Змістова та геометрична інтерпретація задачі цілочислового програмування. 39

4.2 Графічний метод розв’язання задач цілочислового програмування 42

4.3 Метод Гоморі розв’язування задач цілочислового програмування 47

5 СТИСЛИЙ ОПИС ПАКЕТІВ РОЗШИРЕННЯ СИСТЕМИ MAPLE ДЛЯ РОЗВ’ЯЗУВАННЯ ЗАДАЧ ЛІНІЙНОГО ПРОГРАМУВАННЯ.. 68

ЛІТЕРАТУРА.. 73

 

 

ПЕРЕДМОВА

Навчальний посібник складено за програмою курсу “Вища математика” для студентів усіх форм навчання та спеціальностей вищих технічних та економічних навчальних закладів освіти на основі багаторічного досвіду викладання у Вінницькому національному технічному університеті.

Головна особливість посібника полягає у викладенні математичного програмування із застосуванням інформаційних технологій. Для цього пропонується використовувати середовище математичного пакету Maple. Авторами розроблено свій оригінальний підхід, в якому система Maple використовується для розкриття основних ідей, що містяться в теоремах двоїстості та покладені в основу двоїстого симплекс-методу розв’язання задач лінійного програмування, а також цілочислових задач лінійного програмування. В посібнику зроблено спробу висвітлення ключових етапів двоїстого симплекс-методу з наочною геометричною інтерпретацією. Цим посібник відрізняється як від багатьох відомих підручників, в яких пропонується формалізований перелік інструкцій для реалізації двоїстого симплекс-алгоритму, так і від інших відомих спроб викладення математичного програмування, в яких застосування інформаційних технологій зводиться до переліку інструкцій для одержання в певному додатку або остаточної відповіді, або, в кращому разі, послідовності симплекс-подібних таблиць.

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

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

Всі задачі пропонується розв’язувати в середовищі математичного пакета Maple. Причому мова йде не про елементарні рецепти для отримання відповіді за допомогою однієї стандартної команди, а про свідоме відтворення студентом за допомогою Maple-команд всіх етапів двоїстого симплекс-алгоритму та методу Гоморі.

Даний посібник, який є продовженням “Математичного програмування разом з Maple. Частина I. Методи розв’язування задач лінійного програмування”, містить у собі відомості з тем: “Загальна постановка та форми запису задач лінійного програмування”, “Двоїстість у задачах лінійного програмування”, “Двоїстий симплекс-метод”, “Цілочислові задачі лінійного програмування” та стислий опис пакетів розширення системи Maple для розв’язування задач лінійного програмування. Висвітлені в посібнику теоретичні відомості можна вважати скороченим курсом лекцій. Ці відомості демонструються прикладами.

Автори намагалися навести основні відомості, що стосуються як специфіки роботи в середовищі додатка Maple, так і особливостей використовуваних команд і операторів. В той же час для кращого розуміння та більш ефективного використання наведених у посібнику Maple-програм бажано мати уяву про мови програмування у відповідності з об’ємом курсу інформатики середньої школи. В крайньому разі, “механічний” підхід до використання програм теж може виявитися цілком придатним.

Посібник розрахований на студентів економічних та технічних ВНЗ усіх форм навчання та спеціальностей.

 

ДВОЇСТИЙ СИМПЛЕКС-МЕТОД

 

Викладемо двоїстий симплекс-метод, не зупиняючись на його детальному обґрунтуванні.

Розглянемо задачу лінійного програмування в канонічній формі

(3.1)

, (3.2)

. (3.3)

Розглянемо наступну задачу (розділ 2)

, (3.4)

(3.5)

для (3.6)

та її графічне зображення, що показано на рис. 3.1.

Введенням додаткових невідомих перетворимо нерівності системи обмежень (3.5) на строгі рівності

(3.7)

Рівняння кожної з прямих, що відповідають обмеженням задачі та зображені на рис. 3.1, наведені в таблиці 3.1.

 

 

Таблиця 3.1

Позначення прямої	Відповідне рівняння прямої	Змінна, яка дорівнює нулю в будь-якій точці прямої
FQ		x 3
DL		x 4
HQ		x 5
DH		x 6
OL		x 2
OF		x 1

Згідно із симплекс-методом спочатку знаходиться початковий опорний план – базисний допустимий розв’язок. Якщо початковий опорний план шукається методом вибору вільних змінних, то потрібно так вибрати вільні змінні, щоб отриманий базисний розв’язок виявився допустимим. Так, вибравши за вільні, наприклад, змінні дістанемо базисний розв’язок, що відповідає точці перетину двох прямих, вздовж одної з яких , а вздовж іншої . Згідно з даними таблиці 3.1 це буде точка перетину прямих OL та OF, тобто т. О(0, 0). Після знаходження початкового опорного плану вже немає необхідності продовжувати навмання перевибирати вільні змінні, щоб дістати оптимальний план, який відповідає точці В(2, 4). Згідно з ідеями, покладеними в основу симплекс-алгоритму, перехід від неоптимального опорного плану, що відповідає т. О(0, 0), до оптимального опорного плану, що відповідає т. В(2, 4), може бути здійснений одним із цілеспрямованих шляхів – через т. А(4, 0) або через т. С(0, 6).

Всі точки, що позначені буквами на рис. 3.1. відповідають базисним розв’язкам. Причому т. O, A, B, C відповідають опорним планам - базисним допустимим розв’язкам, а решта точок – базисним недопустимим розв’язкам. Тобто, в розв’язках, що відповідають т. D, E, F,… – серед базисних змінних обов’язково знайдеться принаймні одна від’ємна. Для прикладу знайдемо розв’язки, що відповідають т. H і Q. Перша точка є перетином прямих DH і QH, друга точка – перетином прямих FQ і HQ. Отже, в одному випадку за вільні, згідно з таблицею 3.1, потрібно взяти змінні , , в іншому – змінні , _.

Рисунок 3.1 – Графічне зображення задачі (3.4) – (3.6): OABC – многокутник допустимих значень; D(-1, 7), E(0, 7), F(0, 8), G(1/2, 7), H(5, 7), K(5, 1), L(6,0), P(5, 0), Q(5, -2) – точки, що відповідають базисним недопустимим розв’язкам; - - - опорна лінія в крайньому положенні. Згідно з двоїстим симплекс-методом початковим розв’язком також повинен бути базисний розв’язок. Але такий базисний розв’язок, для якого умови допустимості не виконуються, але обов’язково повинні виконуватися умови оптимальності. Базисний розв’язок, для якого виконуються умови оптимальності, але не виконуються умови допустимості називається псевдопланом

 

Знайдемо відповідні розв’язки за допомогою Maple.

> eq1:=2*x[1]+x[2]+x[3]=8:

eq2:=1*x[1]+x[2]+x[4]=6:

eq3:=1*x[1]+x[5]=5:

eq4:=1*x[2]+x[6]=7:

Vilni:=x[5], x[6];

sols1:=solve({seq(eq||kk, kk=1..4)}, {seq(x[kk], kk=1..6)} minus {Vilni});

map(zz->zz=0, {Vilni});

subs(%, sols1);

.

Як видно, в розв’язку, що відповідає т. H() дві базисні змінні , – від’ємні.

> Vilni:=x[3], x[5];

sols2:=solve({seq(eq||kk, kk=1..4)},{seq(x[kk], kk=1..6)} minus {Vilni});

map(zz->zz=0,{Vilni});

subs(%, sols2);

 

.

В розв’язку, що відповідає т. Q(x ₁=5, x ₂=-2) від’ємною є базисна змінна .

Опорна лінія (на рис. 3.1 показана штрих-пунктирною лінією), що проходить через т. В(2, 4), ділить площину Ox ₁ x ₂ на дві півплощини. Одній з півплощин належить область допустимих значень. В іншій півплощині немає жодної точки допустимих значень, якщо не враховувати т. В(2, 4), яка належить межі півплощин. Саме в цій півплощині розташовані всі точки перетину прямих, які відповідають псевдопланам задачі. Базисні недопустимі розв’язки, що відповідають точкам, які розташовані в тій самій півплощині, що й область допустимих значень, не є псевдопланами, оскільки для цих розв’язків не виконується умова оптимальності. Перевіримо сказане для т. H і Q:

> z:=7*x[1]+6*x[2]:

‘z’[H]=subs(sols1, z);

‘z’[Q]=subs(sols2, z);

 

,

.

Очевидно, що для т. H(x ₁ = 5, x ₂ = 7), яка належить півплощині з жодною допустимою точкою, умови оптимальності виконуються – цільова функція не може бути покращена збільшенням вільних змінних. Для т. Q(x ₁ = 5, x ₂ = -2), яка належить тій самій півплощині, що і область допустимих значень, умови оптимальності не виконуються, оскільки цільова функція може бути покращена збільшенням вільної змінної x ₅.

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

Алгоритм двоїстого симплекс-методу складається з двох етапів.

Етап І. Знаходимо початковий псевдоплан.

Етап ІІ.

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

Крок 2. Переходимо до наступного псевдоплану не покращуючи цільову функцію. Якщо такий перехід здійснити неможливо, то задача розв’язку не має.

 

Крок 1 та крок 2 етапу ІІ повторюються аж поки не дістанемо розв’язок задачі лінійного програмування або буде виявлено, що задача не має розв’язку.

Виконання етапу І, тобто знаходження початкового псевдоплану, можна робити так само, як і знаходження початкового опорного плану в симплекс-методі – методом вибору вільних змінних. На практиці двоїстий метод застосовують саме в тих випадках, коли початковий псевдоплан відомий. Таку ситуацію спостерігатимемо при розв’язанні цілочислових задач лінійного програмування.

Розглянемо більш детально здійснення кроку 2.

Запишемо загальний розв’язок системи (3.2)

, (3.8)

та вираз цільової функції через вільні змінні

, (3.9)

де припускається, що – базисні змінні, а – вільні змінні.

Вважатимемо, що , тобто виконуються умови оптимальності для базисного розв’язку, який може бути отриманий з (3.8) прирівнюванням до нуля всіх вільних змінних: .

Отже, розв’язок є псевдопланом. Перехід від даного псевдоплану до наступного визначається двома теоремами.

 

Теорема 1. Якщо в псевдоплані є принаймні одне від’ємне число таке, що в (3.8) всі , то задача (3.1) – (3.3) взагалі не має допустимих розв’язків.

 

Дійсно, в такому випадку із рівняння

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

Теорема 2. Якщо в псевдоплані є від’ємні числа такі, що для будь-якого з них існують в (3.8) числа , то можна перейти до нового псевдоплану, при якому значення цільової функції задачі (3.1) – (3.3) не збільшиться.

 

Тут слід зауважити, що в надзвичайно популярному посібнику [2] в даній теоремі (теорема 1.14, с. 108) допущено помилку: замість «увеличится» написано «уменьшится».

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

(3.10)

та вибрати серед них найменше. Якщо таких найменших чисел виявиться більше ніж одне, то можна вибрати будь-яке з них.

Вибір вільної змінної саме за таким правилом забезпечує виконання умов оптимальності в новому базисному розв’язку. Тому вибрати вільну змінну, яка повинна бути переведена в базисні, можна й простим перебором: на кожній ітерації базисна змінна по черзі вводиться замість однієї із вільних змінних і отриманий базисний розв’язок перевіряється на оптимальність. Як тільки буде отримано базисний розв’язок, що задовольняє умови оптимальності, це і означатиме, що здійснений перехід до нового псевдоплану. Якщо заміна для будь-якої вільної невідомої не дозволяє отримати псевдоплан, то задача (3.1) – (3.3) розв’язку не має. Очевидно, що простий перебір є абсолютно неефективним через великий обсяг обчислень. Але дозволяє краще зрозуміти сутність ідей, покладених в основу двоїстого симплекс-методу.

Зауваження. Якщо в задачі (3.1) – (3.3) потрібно знаходити не max а min, то ознакою оптимальності є умови і замість (3.10) потрібно користуватися співвідношенням, що має протилежний знак

. (3.11)

Приклад 2. Знайти двоїстим симплекс-методом розв’язок задачі (3.4), (3.5), (3.6).

Розв’язання. Згідно з етапом І алгоритму двоїстого симплекс-методу шукаємо початковий псевдоплан. Для цього потрібно вибрати вільні змінні та знайти загальний та відповідний базисний розв’язки системи (3.7). Оскільки ми ознайомилися з геометричною інтерпретацією даної задачі, і з’ясували, що псевдоплану відповідає, зокрема, т. H(5, 7), то за вільні візьмемо змінні , :

> z:=7*x[1]+6*x[2]:

eq1:=2*x[1]+x[2]+x[3]=8:

eq2:=1*x[1]+x[2]+x[4]=6:

eq3:=1*x[1]+x[5]=5:

eq4:=1*x[2]+x[6]=7:

Vilni:=x[5], x[6]:

Знаходимо загальний розв’язок системи (3.7)

> sols1:=solve({seq(eq||kk, kk=1..4)},{seq(x[kk], kk=1..6)} minus {Vilni}):

For i in sols1 do

print(i);

od:

,

,

,

.

Значення базисних змінних в базисному розв’язку дорівнюють

> map(zz->zz=0,{Vilni}):

X1=subs(%, sols1);

 

.

Виражаємо цільову функцію через вільні змінні

> ‘z’=subs(sols1, z);

 

.

Умови оптимальності виконуються, причому серед базисних змінних є від’ємні: , .Отже, маємо початковий псевдоплан. Для переходу до наступного псевдоплану нам потрібно одну з від’ємних змінних поміняти місцями з одною із вільних змінних. Вибираємо серед від’ємних ту, абсолютна величина якої найбільша, тобто (вибір також не був би помилкою). Тепер потрібно визначити, яка з вільних невідомих або повинна замінити змінну серед базисних. Найпростіший спосіб, яким це можна зробити, – простий перебір. Спробуємо змінити місцями , тобто, вільними будуть , :

> Vilni:=x[3], x[5]:

sols2_1:=solve({seq(eq||kk, kk=1..4)},{seq(x[kk], kk=1..6)} minus {Vilni}):

‘z’=subs(sols2_1, z);

 

.

Перед змінною стоїть коефіцієнт 5 > 0, тобто умови оптимальності не виконуються, що очевидно, також, із геометричної інтерпретації: значенням вільних невідомих , на рис. 3.1 відповідає т. Q, яка не належить півплощині, що містить всі точки, які відповідають псевдопланам задачі.

Отже, з вільних невідомих потрібно виводити не x ₆, а x ₅, тобто, вільними будуть x ₃, x ₆:

> Vilni:=x[3], x[6]:

sols2_2:=solve({seq(eq||kk, kk=1..4)},{seq(x[kk], kk=1..6)} minus {Vilni}):

‘z’=subs(sols2_2, z); (3.12)

 

 

Умови оптимальності виконуються. Знайдемо значення базисних змінних

> map(zz->zz=0,{Vilni});

X2=subs(%, sols2_2);

 

,

.

Базисна змінна . Отже, маємо псевдоплан, що відповідає т. G(). Звернемо увагу на те, що в т. H(5, 7) значення цільової функції дорівнює 77, а в т. G(0,5, 7) дорівнює 45,5. Тобто, в задачі на max перехід від одного псевдоплану до іншого відбувається за умови незбільшення цільової функції (в задачі на min – за умови її незменшення).

Повернемося до початкового псевдоплану та визначимо вільну змінну, яку потрібно виводити з вільних за допомогою сформульованих правил. В нашому прикладі , а співвідношення (3.8) та (3.9) мають вигляд відповідно

та .

Відмінність нашого прикладу від загальних співвідношень полягає тільки в тому, що індекси базисних та вільних змінних розташовані не за порядком. Визначаємо величини : для вільної змінної маємо , для вільної змінної x ₆ - . Отже, оскільки , то з вільних потрібно виводити змінну x ₅. Цей же результат ми дістали і простим перебором. За формальними правилами результат здобувається простіше. Простий перебір був наведений для висвітлення геометричної інтерпретації механізму переходу від одного псевдоплану до іншого.

Дістанемо вирази для базисних змінних останнього псевдоплану

for i in sols2_2 do

print(i);

od:

,

,

,

.

Єдина від’ємна змінна серед базисних – , її і будемо виводити із базисних змінних. Для вибору вільної змінної, замість якої вводитимемо , знайдемо величини , j =3, 6 (див. (3.12)): x ₃→ , x ₆→ . Оскільки , то з вільних потрібно виводити змінну х₆. Отже, вибираємо за вільні змінні х₃, х₄,знаходимо загальний розв’язок та виражаємо цільову функцію через вільні змінні:

> Vilni:=x[3], x[4]:

sols3:=solve({seq(eq||kk, kk=1..4)},{seq(x[kk], kk=1..6)} minus {Vilni}):

‘z’=subs(sols3, z);

 

.

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

> map(zz->zz=0,{Vilni});

X3=subs(%, sols3);

 

,

.

Серед базисних змінних від’ємні значення відсутні, отже, отриманий розв’язок є допустимим, а з урахуванням виконання умов оптимальності маємо оптимальний розв’язок. Цей розв’язок відповідає т. В(x ₁ = 2, x ₂ = 4) на рис. 3.1.

При розв’язанні конкретної задачі лінійного програмування виникає питання вибору методу, що використовується: симплекс-методу або двоїстого симплекс-методу. Двоїстий симплекс-методу зручно використовувати у випадках, коли в ході розв’язання задачі лінійного програмування необхідно додавати нові обмеження. Така ситуація виникає, наприклад, при розв’язанні цілочислових задач лінійного програмування методом Гоморі, що буде розглянуто в підрозділі 4.3. В подібних випадках при застосуванні симплекс-методу після додавання кожного нового обмеження задачу потрібно розв’язувати з самого початку. Застосування в таких випадках двоїстого симплекс-методу зумовлено тим, що відомим є початковий псевдоплан. При розв’язанні звичайних задач лінійного програмування вибір на користь того або іншого методу може бути зроблений в залежності від того, що легше знайти: початковий опорний план чи початковий псевдоплан.

Приклад 4

Знайти найбільше значення функції

> restart:

z:= 41*x[1] + 33*x[2]:

‘z’=z,`->`*max;

 

за умови, що її аргументи пов’язані співвідношеннями

> linear_constraints:=map(y->subs(x1=x[1], x2=x[2], y),

[133835*x1-4529360*x2<=-561587, -55167*x1-2182400*x2<=-1084571,

-103761*x1-378664*x2<=-515601, -917135*x1-340041*x2<=-2475628,

55775*x1+557469*x2<=2655572, x1>=0, x2>=0]):

for i from 1 to nops(linear_constraints) do op(i,linear_constraints) od;

,

,

,

,

,

,

.

Невідомі можуть приймати тільки цілі значення: – цілі числа.

Розв’язання. Так само, як це ми робили і для нецілочислової задачі, будуємо область допустимих розв’язків – за допомогою команди plots[inequal] (цей графік присвоєно змінній Maple під ім’ям g10), градієнт – за допомогою команди my_arw та опорну лінію MN (g20):

> x1:=-5:x2:=40:

y1:=-1.0:y2:=6:

g10:=plots[inequal]({op(linear_constraints)}, x[1]=x1..x2, x[2]=y1..y2, optionsfeasible=(color=red), optionsopen=(color=blue, thickness=2), optionsclosed=(color=black, thickness=2), optionsexcluded=(color=cyan)):

my_arw:=(x, y, l, w)->if add(type(args[k], numeric), k=1..nargs)=4*true then[[0, 0], [x, y]], [[x-x*l-y*l*w,

-(-y^2+y^2*l-x^2+x^2*l+x*(x-x*l-y*l*w))/y], [x, y]], [[x-x*l+y*l*w,

-(-y^2+y^2*l-x^2+x^2*l+x*(x-x*l+y*l*w))/y], [x, y]] fi:

c1:=3*4.1: c2:=3*3.3: x1_d:=10: y1_d:=2:

g20:=plot([my_arw(c1, c2, 0.15, 0.2), y1_d-(c1/c2)*(x[1]-x1_d)], x[1]=x1..15, x[2]=y1..12, color=[blue$3, black], thickness=[4$3, 2], scaling=CONSTRAINED):

g30:=PLOT(TEXT([35, 3], ’C’, ALIGNLEFT, FONT(TIMES, ITALIC, 14)), TEXT([7, 9],’M’, ALIGNLEFT, FONT(TIMES, ITALIC, 14)), TEXT([14, -1],’N’, ALIGNLEFT, FONT(TIMES, ITALIC, 14))):

plots[display]([g10, g20, g30], scaling=CONSTRAINED,

view=[ 4..37, 0.5..10]);

Координати градієнта помножили на 0.3: c1:=3*4.1:c2:=3*3.3: – для того, щоб вектор помістився на графіку. В рівнянні опорної лінії точку допустимої області взято т. (10;2). Графічна структура g30 містить буквені позначення M, N, C.

Із отриманого графіка видно, що оптимальним планом нецілочислової задачі є координати т. С, точні значення яких в даному випадку нам не потрібні. Для того, щоб визначити оптимальний план цілочислової задачі, потрібно збільшити частину області допустимих значень навколо т. С. Крім того потрібно якимось чином виділити на графіку точки з цілочисловими координатами. Це можна зробити за допомогою сітки, утвореної горизонтальними та вертикальними прямими з цілочисловими координатами. Для побудови такої сітки автором створена допоміжна процедура my_drid(Xn, Ym), яка формує команду побудови горизонтальних та вертикальних прямих, координати яких задані списками Xn, Ym. Для регулювання області відображення графіка користуватимемося опцією view=[25..37, 0..4] команди plots[display].

> x1_d:=35.43:y1_d:=1.24:

my_drid:=(xn::list, yn::list)->plot([yn[‘i’] $ ‘i’ = 1..nops(yn),[xn[‘i’], t, t=yn[1]..yn[nops(yn)]] $ ‘i’ = 1..nops(xn)], xn[1]..xn[nops(xn)], yn[1]..yn[nops(yn)], color=black, linestyle= [3$nops(yn), 4$nops(xn)], scaling=CONSTRAINED):

g40:=plot([[[x1_d, y1_d]], y1_d-(c1/c2)*(x[1]-x1_d)], x[1]=x1..x2, x[2]=y1..y2, color=black, style=[point,line], symbol=circle, symbolsize=25, linestyle=3, thickness=2, scaling=CONSTRAINED):

plots[display]([g10, g20, g40,my_drid([$ 25..37],

[$ 0..4])], view=[25..37,0..4], scaling=CONSTRAINED);

Зменшуємо діапазон виведення графіка (view=[27..33, 0..3]) та зсуваємо у відповідну область опорну лінію (x1_d:=31:y1_d:=1.5:)

> x1_d:=31:y1_d:=1.5:

g60:=plot([y1_d-(c1/c2)*(x[1]-x1_d)], x[1]=x1..x2, x[2]=y1..y2, color=black, style=[line], symbol=circle,

symbolsize=25, linestyle=3, thickness=2, scaling=CONSTRAINED):

plots[display]([g10, g20, g60, my_drid([$ 25..37], [$ 0..4])],

view=[27..33, 0..3], scaling=CONSTRAINED);

Із отриманого графіка видно, що області допустимих значень не належать точки з цілочисловими координатами, абсциси яких дорівнюють 32 і більше, а ординати 3 і більше. Добре видно, що області допустимих значень належить т. (28; 1). Отже, знову зменшуємо діапазон виведення графіка (view=[28..31, 0.7..2.2])

Із графіка видно, що оптимальним планом є координати т. (30; 1), якщо ця точка належить області допустимих значень, або координати т. (29; 1) – в протилежному випадку. Перевіримо належність т. (30; 1) до області допустимих значень:

> plots[display]([g10, g20, g60, my_drid([$ 25..37],

[$ 0..4])], view=[29.9..30.9, 0.97..1.1], scaling=CONSTRAINED);

Очевидно, що т. (30, 1) знаходиться поза областю допустимих значень. Отже,

> x1_d:=29:y1_d:=1:

g50:=plot([[[x1_d, y1_d]], y1_d-(c1/c2)*(x[1]-x1_d)], x[1]=x1..x2, x[2]=y1..y2, color=black, style=[point, line], symbol=circle, symbolsize=25, linestyle=3, thickness=2, scaling=CONSTRAINED):

plots[display] ([g10, g20, g50, my_drid([$25..37], [$0..4])], view=[28.8..30.05, 0.8..2.01], scaling=CONSTRAINED);

 

Оптимальний план , оптимальне значення цільової функції

>‘z[max]’=subs(x[1]=29, x[2]=1, z);

 

.

Для того, щоб наведені в цьому прикладі програми були доступні в DEMO-Maple, потрібно тільки вилучити опцію symbolsize=25 команди plot.

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

Навчальне видання

 

Тютюнник Оксана Іванівна

ЧАСТИНА ІI

МАТЕМАТИЧНЕ ПРОГРАМУВАННЯ В MAPLE

Частина ІІ