Розв’язок. 1. Складемо математичні моделі вихідної та двоїстої задач, позначивши через план випуску j-го виду продукції

1. Складемо математичні моделі вихідної та двоїстої задач, позначивши через план випуску j-го виду продукції, а через вартість одиниці i-го ресурсу. Тоді за формулами [2;3;5] математичні моделі вихідної та двоїстої задач мають вигляд:

вихідна задача двоїста задача

max=46X₁+12X₂+10X₃+8X₄ min f =3000У₁+5000У₂+8000У₃

3X₁+4X₂+4X₃+5X₄≤3000 3У₁+2У₂+10У₃≥46

2X₁+3X₃+4X₄≤5000 4У₁+12У₃≥12

10X₁+12X₂+10X₃+8X₄≤8000 4У₁+3У₂+10У₃≥10

5У₁+4У₂+8У₃≥8

X_j³0 Y_i³0

Для розв´язання симплекс-методом перейдемо в обмеженнях до рівностей шляхом уведення додаткових змінних

вихідна задача двоїста задача

max=46X₁+12X₂+10X₃+8X₄+0(X₅+X₆+X₇) min f =3000У₁+5000У₂+8000У₃

3X₁+4X₂+4X₃+5X₄+X₅ =4000 3У₁+2У₂+10У₃-У4 =46

2X₁+3X₃+4X₄+X₆ =5000 4У₁+12У₃ -У5 =12

10X₁+12X₂+10X₃+8X₄+X₇=8000 4У₁+3У₂+10У₃-У6 =10 X_j³0 5У₁+4У₂+8У₃-У7 =8

Y_i³0

У вихідній задачі 7 змінних і 3 обмеження, причому додаткові змінні є базисними. Тому цю задачу відразу можна розв´язувати симплекс-методом.

У двоїстій задачі 7 змінних і 4 обмеження, причому для розв´язування симплекс-методом треба вводити штучний базис, а це ще плюс 4 змінні. Тому вихідну задачу розв´язувати простіше. Запишемо її дані в симплекс-таблицю 10 і виконаємо розв´язування за алгоритмом симплексного методу. У результаті після однієї ітерації перерахування таблиці одержали в оцінному рядку всі ∆j≥0. Виходить, отриманий опорний план вихідної задачі X₁=800; X₂=X₃=X₄=0; X₅=600; X₆=3400; X₇=0, оптимальний.

Цей план випуску продукції =(800;0;0;0;600;3400;0) забезпечує її максимальну сумарну вартість max Z = 36800 грош. од.

2. Для того, щоб знайти оптимальний план двоїстої задачі, визначимо взаємозв'язок змінних двоїстих задач і економічний зміст їх додаткових змінних. Для вихідної задачі i- а додаткова змінна

залишок i-го ресурсу для опорного плану вихідної задачі, ,

Таблиця 12 – Симплекс-таблиця для задачі розподілу ресурсів

Базис. змін.	Cb	Xb								Θo
X1	X2	X3	X4	X5	X6	X7
X5
X6
X7
Z =		-46	-12	-10	-8
X5				0.4		2.6			-0.3
X6				-2.4		2.4			-0.2
X1				1.2		0.8			0.1
Z =			43.2		28.8			4.6
			У4	У5	У6	У7	У1	У2	У3

i-а змінна двоїстої задачі означає ціну за одиницю цього ресурсу.

Для двоїстої задачі j-а додаткова змінна,

,

різниця між сумарною вартістю витрат усіх ресурсів y_m+jна одиницю j-го виду продукції та вартістю за одиницю цієї продукції. Тому y_m+j(j=1,…,n)можна трактувати як характеристику рентабельності випуску j-го виду продукції. Якщо y_m+j>0, тоді випуск j-го виду продукції не рентабельний (витрати більші за ціну), якщо y_m+j=0, тоді випуск j-го виду продукції рентабельний. У зв´язку з вищевикладеним, основним змінним однієї задачі відповідають додаткові змінні іншої, тобто:

Xn+i Yi ,

Ym+i Xi .

Причому для оптимальних планів цих задач випливає, що

, (25)

. (26)

З огляду на те, що всі змінні від´ємні, з (25) і (26) одержимо для оптимальних планів:

X⁰_n+i=0 y⁰_i>0 чи X⁰_n+i>0 Y⁰_i=0, (27)

Y⁰_m+j=0 X⁰_j>0 чи Y⁰_m+j>0 X⁰_j=0.

З (27) випливає: для оптимальних планів двоїстих задач:

1) якщо i-й ресурс цілком використовується, (X⁰n+i=0), тоді його ціна Y⁰i>0, якщо ні, (X⁰n+i>0), тоді його ціна y⁰_i=0, (j=1,…, m);

2) якщо витрати на випуск одиниці j-го виду продукції більші за її ціну, Y⁰_m+j>0, то ця продукція не випускається, X⁰_j=0, якщо Y⁰_m+j=0, тоді випуск j-го виду продукції рентабельний і X⁰_j>0, (j=1,…, n).

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

Одержимо =(0;0;4,6;0;43,2;36;28,8)

З симплекс-таблиці з оптимальним планом випливає, що min f = max Z =

=36800 грош.од..

З огляду на економічний зміст змінних двоїстих задач проведемо економічний аналіз результатів.

Рентабельний тільки випуск продукції першого виду (y⁰₄=0) у кількості X⁰₁=800од. Випуск інших видів продукції не рентабельний, при випуску один. продукції цих видів збитки складуть, відповідно, 43,2(У⁰₅), 36(У⁰₆),

28,8(У⁰₇) грош. одиниць. Тому X⁰₂=X⁰₃=X⁰₄=0. При такому плані випуску максимальна вартість випущеної продукції складе 36800 грош.од.. При цьому верстатні ресурси цілком витратяться, їхній залишок X⁰₇=0, вони дефіцитні, їхня ціна за один. складе В⁰₃=4,6 грош.од.. Трудові та матеріальні ресурси витрачаються не цілком, вони не дефіцитні. Тому їхня ціна за одиницю. У⁰₁=У⁰₂=0, залишки, відповідно, X⁰₅=600 і X⁰₆=3400 од.

З огляду на вищевикладене, для збільшення сумарної вартості випущеної продукції необхідно збільшувати запаси дефіцитного ресурсу–верстатного.

З [2;3;5] випливає, що:

.

Тому збільшення запасу верстатного ресурсу b₃ на один. призведе до збільшення максимальної сумарної вартості випущеної продукції на В⁰₃ =

4,6 грош. од..

3) досліджуємо допустимі межі зміни дефіцитного ресурсу, усередині яких змінні, що входять в оптимальний базис, не змінюються, тобто не змінюється асортимент продукції, що випускається, а змінюється тільки її обсяг залежно від збільшення чи зменшення ресурсу на ∆ b. Якщо дефіцитним є i-й ресурс, то, з огляду на лінійність матричних перетворень, можна показати [2;3;5], що новий оптимальний план при зміні i-го ресурсу на ∆ b_i буде:

(28)

причому:

(29)

З (28) і (29) знайдемо ∆ b₃, m=4

Тоді b₃ + ∆b₃буде змінюватися

8000-8000≤b₃≤8000+2000

0≤b₃≤10000

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

2000 од. верстатних ресурсів. Це призведе до збільшення випуску продукції першого виду до X⁰₁ = 800+0,1·2000 = 1000 од. і вартості випущеної продукції до 46·1000 = 46000 грош. од., тобто на 4,6·2000 = 9200 грош. од..

Якщо на ринку немає конкурентів з реалізації продукції першого виду, тобто підприємство − монополіст, то збільшення вартості продукції можна досягти іншим шляхом – за рахунок збільшення її ціни. Досліджуємо допустимі межі її зміни ∆C. При цьому будемо використовувати оптимальне розв´язання двоїстої задачі В₀, що знаходиться в оцінному рядку останньої таблиці. Формули, аналогічні (28), (29) мають вигляд:

,

причому

,

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

У нашій таблиці це третій рядок. Тоді:

∆С₁≥0∆С₁≥0

43,2+1,2∆С₁≥0 ∆С₁≥-36

36+∆С₁≥0 => ∆С₁≥-36 => ∆С₁≥0

28,8+0,8∆С₁≥0 ∆С₁≥-36

4,6+0,1∆С₁≥0 ∆С₁≥-46

Тоді 46≤C₁<∞.

Одержали, що теоретично ціну на продукцію першого виду можна збільшувати необмежено.

4) проаналізуємо доцільність розширення асортименту за рахунок випуску продукції П-5. Для цього порахуємо для отриманих оптимальних цін на ресурси їхні сумарні витрати на одиницю П-5. Одержимо 5·У⁰₁+6·У⁰₂+9·У⁰₃=5·0 + 6·0 + 9·4,6 = 41,4 грош. од. оскільки витрати менші за заплановану ціну один. продукції (41,4 < 50), то випуск продукції П-5 рентабельний і прибуток від випуску одиниці П-5 складе 8,6 грош. од.

Завдання 3 Розв´язання транспортної задачі

Є три постачальники і чотири споживачі однорідного продукту. Потужності постачальників і попити споживачів, а також витрати на перевезення одиниці вантажу для кожної пари «постачальник-споживач» зведені до таблиці 13 постачань.

Задача полягає у наступному: знайти обсяги перевезень для кожної пари «постачальник - споживач» так, щоб:

1) потужності всіх постачальників були реалізовані;

2) попити всіх споживачів були задоволені;

3) сумарні витрати на перевезення були мінімальні.

Розв´язок

Поставлено збалансовану транспортну задачу, оскільки сумарний попит дорівнює сумарній потужності постачальників ® 280.

Для отримання начального опорного плану перевезень скористаємось методом мінімального елемента.

Таблиця 13 – Потужності постачальників і попити споживачів, витрати на перевезення одиниці вантажу

	Споживачі	Потужність постачальників ai
B1	B2	B3	B4
Постачальники	A1
A2
A3
Попит bj

Для покращення будемо використовувати таблицю 14, у правому верхньому кутку якої стоїть тариф відповідного перевезення, а у лівому нижньому кутку – плановий обсяг перевезення.

Знаходимо в таблиці клітинки з найменшим тарифом. Таких клітин дві- (1;1) і (2;1) із тарифом, що дорівнює 1. Порівнюємо максимально можливі постачання для цих клітинок: для клітинки (1;1) x₁₁=min{60,20}=20, для клітинки (2;1) x₂₁=min{120,20}=20. Оскільки їх значення збігаються, то максимально можливе постачання записуємо в будь-яку з них. Наприклад, записуємо постачання, що дорівнює 20 од. у клітинку (2;1). У результаті попит першого споживача задоволений і перший стовпець таблиці постачань випадає

з наступного розгляду, а виробничу потужність для другого рядка зменшуємо на 20 од. Аналогічним способом продовжуємо заповнювати невикреслені клітинки таблиці. У останній клітинці попит і пропозиція повинні збігтися, оскільки розглядається збалансована задача. Слід зазначити, що в таблиці повинна бути заповнена n+m-1 клітинка перевезень (де n – число постачальників, m – число споживачів).

Наприклад, для розглянутої задачі повинно бути заповнено 3+4-1=6 клітин. Остаточно одержуємо початковий опорний план перевезень.

Таблиця 14 – Отримання начального опорного плану перевезень

	В1	В2	В3	В4	ai
А1
		60
А2
						100
А3
		50		40		10
bj

Тепер скористаємося методом потенціалів, усі розрахунки виконаємо у таблиці 15. Для цього кожному стовпцю припишемо потенціал v_j, а кожному рядку – потенціал u_i. Для кожної заповненої клітини складемо лінійне рівняння за правилом u_i+v_j=c_ij, де c_ij - тариф відповідного перевезення. Потім розв’яжемо систему 6-ти рівнянь.

Оскільки в рівняннях буде 7 невідомих (3 потенціали u і 4 потенціали v), то довільний потенціал можна дорівняти до нуля.

Тепер для кожної незаповненої клітинки необхідно знайти оцінку D_ij= u_i+v_j-c_ij. Якщо всі оцінки будуть негативними або нульовими, то початковий опорний план є оптимальним.

Таблиця 15– Розрахунки методом потенціалів

					ai
V1=3	V2=3	V3=7	V4=4
	U1=-1					-1
	U2=-2			-5
	U3=0	-3
bj

D₁₁=-1+3-1=1; D₁₃=-1+7-5=1; D₁₄=-1+4-3=0; D₂₂=-2+3-6=-5; D₂₃=-2+7-5=0; D₃₁=0+3-6= -3. Оцінки D₁₁ і D₁₃ позитивні, отже, отримане початкове опорне розв’язання не оптимальне. З оцінок вибираємо найбільшу – D₁₁, отже, у клітинку (1;1) будемо заносити ненульове перевезення. Заносимо в клітинку (1;1) знак «+» і будуємо ланцюг потенціалів, що може проходити тільки по заповнених клітинках, із чергуванням знаків «+» і «-» і повертається у вихідну незаповнену клітину, таблиця 16.

Cеред клітинок, позначених мінусом, вибираємо ту, що містить найменше перевезення. Це клітинка (3;4) з К=Х₃₄ =10. У подальших обчисленнях ця клітинка буде вважатися незаповненою, тому що далі вміст вибраної клітинки,10, додаємо до вмісту клітинок, що позначені «+», і віднімаємо з клітинок, що позначені «-».У таблиці 15 повинна виявитися, як і раніше, n+m-1

заповнена клітинка. Перевіряємо отриманий опорний план на оптимальність.

D₁₃=1; D₁₄=-1; D₂₂= -4; D₂₃=1; D₃₁= -4; D₃₄= -1.

Тому що є дві клітини (1;3) і (2;3) з позитивними оцінками, то отриманий опорний план, таблиця 17, не оптимальний. Знайдемо новий опорний план з

використанням ланцюга потенціалів, таблиця 17.

Таблиця 16 – Перехід до іньшого опорного плану з використанням ланцюга потенціалів

					ai
V1	V2	V3	V4
	U1
+		-
	U2
-						+ 100
	U3
		+				-
bj

Оскільки дві позитивні оцінки набувають однакових позитивних значень, D₁₃=D₂₃=1, то можна занести ненульове перевезення або в клітинку (1;3), або в клітинку (2;3). Якщо у ланцюг будє включено клітинку (1;3),таблиця 17, то це перевезення буде дорівнювати 40 од.. Таким чіном одержано новий опорний план, таблиця 18.

Таблиця 17 – Отриманий опорний план

			3	4	ai
V1=2	V2=3	V3=7	V4=3
	U1=-1							-1
		-		+
	U2=-1			-4
	U3=0	-4						-1
		+		-
bj

Таблиця 18 – Оптимальний опорний план

					ai
V1=1	V2=2	V3=5	V4=2
	U1=0							-1
	U2=0			-4
	U3=1	-4				-1		-1
bj

Перевіряємо отриманий опорний план на оптимальність.

D₁₄= -1; D₂₂= -4; D₂₃= 0; D₃₁= -4; D₃₃= -1; D₃₄= -1.

Оскільки серед оцінок немає позитивних, можна сказати, що отриманий опорний план є оптимальним, але не єдиним (D₂₃= 0).

У підсумку підприємствам можна запропонувати наступний план перевезень:

При такому розподілі перевезень потужності всіх постачальників будуть реалізовані, попит усіх споживачів задоволений, сумарні витрати складуть:

грош. од.

Завдання 4 Розв´язання задачі про призначення

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

Розв´язок

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

.

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

2. Якщо після першого кроку можливий вибір чотирьох незалежних нулів, тоді можна стверджувати, що задача розв’язана. Незалежні нулі для зручності будемо позначати (*). При розставленні позначок найкраще вибирати рядок або стовпець, що містять найменшу кількість нулів. У цьому рядку (стовпці) вибираємо нуль, позначаємо його і викреслюємо інші нулі в рядку чи стовпці, на перетині яких знаходиться вибраний (або незалежний) нуль. Позначки ставимо доти, доки в матриці існують вільні (непозначені або невикреслені) нулі.

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

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

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

2. Позначаємо всі стовпці, що містять нуль хоча б в одному позначеному рядку.

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

Кроки 2 і 3 виконуємо доти, доки можливо ставити позначки. Далі викреслюємо непозначені рядки і позначені стовпці.

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

4. Серед елементів, через які не пройшла жодна з ліній, обираємо найменший. Віднімаємо це число від усіх елементів, через які не пройшла жодна лінія, і додаємо його до всіх елементів, через які проведені дві лінії.

5.

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

1-ше завдання ® 1-й ресурс;

2-ге завдання ® 2-й ресурс (або 4-й ресурс);

3-тє завдання ® 3-й ресурс;

4-те завдання ® 4-й ресурс (або 2-й ресурс).

У результаті такого призначення система виконає всі завдання за 17 умовних одиниць часу.

Зауваження. У тому випадку, якщо необхідно розв’язати задачу отримання максимального значення функції мети, можна скористатися наступною формулою переходу, що слушна для будь-якої задачі лінійного і нелінійного програмування: min (L) = - max (-L)(тобто елементи матриці С помножити на (-1)).

Завдання 5 Розв’язати задачу цілочислового програмування

Дата добавления: 2015-05-23