Математическое программирование

 

 

 

 

 

 

 

 

 

 

 

Контрольна робота з дисципліни

 

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

Варіант 2

 

 

 

 

 

 

Перевірив:     ____________________

Виконав: студент ___  групи   Зал. книжка № _________

 

 

 

 

 

 

 

 

 

Київ 2013

 

 

 

Зміст

 

 

 

Завдання 1 3

Завдання 2 4

Завдання 3 5

Завдання 4 8

Список використаної літератури 10

 

Завдання 1

 

1) Побудувати  математичну модель задачі лінійного програмування.

2) Звести дану задачу до канонічного вигляду.

Два вироби В₁ і В₂ обробляються послідовно на трьох верстатах. Кожен виріб типу В₁ потребує 1 год. для обробки на I-му верстаті, 2 год. - на II-му і 2,6 год. - на ІІІ-му. Кожен виріб типу В₂, потребує для обробки 2 год., 2,6 год. і 3 год. відповідно на I-му, II-му і ІІІ-му верстатах. Час роботи па І-му верстаті не повинен перевищувати 70 год., на ІІ-му – 105 год. на ІІІ-му - 50 год. Скласти план виробництва при максимальному прибутку, якщо відомо, то продаж одного виробу типу В₁ приносить прибуток 5 грн., а типу В₂ - 3 грн. N=7; А=√N=√7 ≈2,6

 

Розв’язання.

Нехай Х₁ та Х₂ – кількості виробів видів В₁ та В₂, які будуть виготовлені.

Тоді  економіко-математична модель задачі має вигляд:

Цільова функція :

Z = 5x₁+3x₂ → max

Обмеження :

x₁ + 2x₂ ≤ 70

2x₁ + 2,6x₂ ≤ 105

  2,6x₁ + 3x₂ ≤ 50

x₁  ≥ 0, x₂ ≥ 0

Зведемо систему  обмежень до канонічного вигляду:

x₁ + 2x₂ + x₃ = 70

2x₁ + 2,6x₂  + x₄ = 105

  2,6x₁ + 3x₂ + x₅ = 50

x₁  ≥ 0, x₂ ≥ 0, x₃ ≥ 0, x₄ ≥ 0, x₅ ≥ 0

Z = 5x₁+3x₂ +0x₃ +0x₄ +0x₅ → max

Завдання 2

 

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

 

1. Z = 6x₁ + 4x₂ → max

Розв’язання.

Розв'яжемо  дану задачу лінійного програмування  графічним методом. 
Побудуємо багатокутник рішень (Рис. 1).    

Для цього в системі координат  х₁Ох₂ на площині зобразимо граничні прямі:

3х₁+5x₂ = 15 (L1)

4х₁+3x₂ = 12 (L2)

x₁ = 0   (L3)

x₂ = 0   (L4)

Для (L1): при х₁ = 0, х₂ = 3, при х₂ = 0, х₁ = 5.

Для (L2): при х₁ = 0, х₂ = 4, при х₂ = 0, х₁ = 3.

Встановимо, яку напівплощину визначає відповідна нерівність з системи обмжень. На перетині цих напівплощин отримаємо багатокутник рішень  даної  задачі: чотирикутник ОАВС.

Для побудови прямої (Z): 6x₁ + 4x₂ будуємо радіус-вектор N = (6;4) і через точку O проводимо пряму (Z), перпендикулярну йому. Побудовану пряму (Z) = 0 переміщуємо паралельно  самої собі в напрямку вектора N. З мал.1 випливає, що пряма 6x₁ + 4x₂ = const, пересуваючись в напрямку вектора N, перетинає трикутник рішень в крайній точці А. У цьому випадку лінійна функція Z приймає максимальне у точці А.

Мал. 1

В точці А(3;0): Z = 6x₁ + 4x₂ = 6∙3+4∙0=18, тобто

Z_max = 18.

Завдання 3

Розв’язати систему лінійних рівнянь методом повного виключення змінних (методом Гаусса) з використанням розрахункових таблиць.

х₁ + 2х₂ + 3х₃  = 5

2х₁ - х₂ - х₃ = 1

х₁ + 3х₂ + 4х₃ = 6

 

Розв'язання

Для знаходження розв'язку системи застосуємо метод Гаусса (точніше, Жордана-Гаусса). Розрахунки за цим методом подамо у вигляді таблиці 1, в яку заносимо розширену матрицю системи.

 

Таблиця 1.

N ітерації	x1	x2	x3	ai0
0	1	2	3	5
	2	-1	-1	1
	1	3	4	6
1	1	2	3	5
	0	-5	-7	-9
	0	1	1	1
2	1	0	1	3
	0	0	-2	-4
	0	1	1	1
3	1	0	0	1
	0	0	1	2
	0	1	0	-1

 

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

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

1 ітерація. Вибираємо перший ведучий стовпчик та перший ведучий рядок (відповідний елемент у таблиці 1 виділено жирним шрифтом та підкреслено).  На їх перетині стоїть ведучий елемент a₁₁. Тут і надалі через a_qp позначатимемо елемент, який стоїть на перетині рядка з номером q та стовпчика з номером р.

Далі  перераховуємо елементи ведучого рядка  за формулою:

 (1)

де k = 0,1,2, …; q – номер ведучого рядка, p – номер ведучого стовпчика, - елементи нової матриці, яка відповідає першій ітерації. Оскільки для даного прикладу  , то згідно з формулою (1), всі елементи ведучого рядка необхідно поділити на 1 , а отже переписати без зміни.

Елементи  інших рядків обчислюються за формулою (правило прямокутника):

 (2)

або (враховуючи (1)) за формулою:

де i = 1,2,…; (i ≠ q);  k = 0,1,2, …; q – номер ведучого рядка, (q=3);  p – номер ведучого стовпчика,  (p = 1).

Для елементів  2-го рядка одержимо:

 і так далі.

Елементи  3-го рядка обчислюються аналогічно.

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

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

2 ітерація. За ведучий вибираємо елемент (ведучий рядок – третій. Ведучий стовпчик – другий). Проводимо обчислення, аналогічні тім, що пророблені при першій ітерації.

3 ітерація. - ведучий елемент.

В останній таблиці жоден рядок не може бути вибраний за ведучий, отже, розрахунки закінчені.

Ми одержали три лінійно незалежних одиничних стовпчика при трьох змінних. Тому дана система рівнянь визначена.

Оскільки  остання таблиця відповідає системі

то це і є загальний розв’язок вихідної системи.

Перевіримо цей розв’язок підстановкою у вихідну систему:

х₁ + 2х₂ + 3х₃  = 5

2х₁ - х₂ - х₃ = 1

х₁ + 3х₂ + 4х₃ = 6

 

Отже, розв’язок знайдено правильно.

Завдання 4

1) Розв’язати  симплекс-методом задачу лінійного  програмування, яка представлена  у завданні 2.

2) Побудувати  двоїсту задачу до заданої  задачі лінійного програмування.

Z = 6x₁ + 4x₂ → max

 

Розв'язання

Розв’яжемо  початкову задачу симплексним методом.

Зведемо систему  обмежень до канонічного вигляду:

3x₁ + 5x₂ + x₃ = 15

4x₁ + 3x₂  + x₄ = 12

x₁  ≥ 0, x₂ ≥ 0, x₃ ≥ 0, x₄ ≥ 0

Z = 6x₁ + 4x₂ +0x₃ +0x₄  → max

Опорний план : x₁ = 0 x₂ =0; x₃ = 15; x₄ =12.  Z=0.

Побудуємо першу  симплексну таблицю.

 Таблиця  1

Базисні змінні	Вільні члени	Cj	6	4	0	0	Симпл. відношен-  ня, Qi
			X1	X2	X3	X4
X3	15	0	3	5	1	0
X4	12	0	4	3	0	1
Zj-Cj	0		-6	-4	0	0

 

У (Zj-Cj)-рядку  обираємо стовпець з від'ємним елементом  = -6 (з х₁)  і цей стовпець вважаємо розв'язувальним. Знаходимо симплексні відношення Qi = b_i/a_ik – елементів стовпчика вільних членів до елементів розв'язувального стовпчика, крім тих, які від'ємні та дорівнюють нулю.

Найменшому  відношенню відповідає розв'язувальний рядок, який вказує, яку змінну треба  вивести з базису. У нас це змінна x₄ .  До базису вводиться змінна x₁. На перетині  розв'язувальних стовпчика та рядка стоїть головний елемент R =  4.

Будуємо наступну симплексну таблицю: елементи розв'язувального рядка ділимо на головний елемент R, а решту елементів  таблиці перераховуємо за формулою Жордана-Гаусса:

a'_ij = (a_ijR - a_iRj·a_ijR) / R.

Таблиця 2

Базисні змінні	Вільні члени	Cj	6	4	0	0	Симпл. відношен-  ня, Qi
			X1	X2	X3	X4
X3	15	0	0	11/4	1	-3/4
X1	3	6	1	¾	0	¼
Zj-Cj	18		0	½	0	3/2

 

Отримуємо Таблицю 2, в якій всі елементи в (Zj-Cj)-рядку - невід'ємні, тому отриманий розв'язок є оптимальним:

x₁ = 3;  x₂ = 0; Zmax = 18.

2) Побудуємо двоїсту задачу до даної.

Згідно теорії:

Початкова задача:	Двоїста задача:
Max Z =  CX AX £ B X ³ 0	Mіn F = YB AтY ³ C Y ³ 0

 

У нас:

Z = 6x₁ + 4x₂ → max

_{Тоді двоїста  задача запишеться так:}

F =15y₁+12y₂ → min

3y₁+4y₂ ³ 6

5y₁+3y₂ ³ 4

y₁ ³ 0; y₂ ³ 0.

Список використаної літератури

 

 

1. Бугір М.К. Математика для економістів. Лінійна алгебра, лінійні моделі. – К., 1998. – 272 с.
2. Ляшенко И.Н., Карагодова Е.А., Черникова Н.В., Шор Н.З. Линейное и нелинейное программирование. – К.: Вища школа, 1975. – 372 с.
3. Наконечний С.І., Савіна С.С. Математичне програмування: Навч. посіб. – К.:КНЕУ, 2003.
4. Ржевський С.В. Елементи теорії дослідження операцій. – К.: ЄУФІМБ, 1999. – 120 с.