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

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

I:	6	0
	0	9

II:	0	-6
	6	0

III:	0	4
	4	0

Визначимо півплощини, що задовольняють нашим нерівностям.

Умовам невід'ємності та відповідає перша чверть.

Заштрихуємо спільну частину площини, що задовольняє всім нерівностям.

Побудуємо вектор нормалі .

Максимального значення функція набуває в точці перетину прямих I та II.

Знайдемо координати цієї точки.

Приведемо систему до канонічного вигляду

Відповідь:

Розв?язання симплекс-методом

Приведемо систему рівнянь до канонічного вигляду

x(0)=(0,0,18,6,0,4)

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

Побудуємо симплекс-таблицю

I	базис	Cб	P0	2	3	0	0	0	-M
				P1	P2	P3	P4	P5	P6
1	P3	0	18	3	2	1	0	0	0
2	P4	0	6	-1	1	0	1	0	0
3	P6	-M	4	1	1	0	0	-1	1
4			0	-2	-3	0	0	0	0
5			-4	-1	-1	0	0	1	0

Отриманий план не оптимальний

Обраний ключовий елемент (3,2)

I	базис	Cб	P0	2	3	0	0	0	-M
				P1	P2	P3	P4	P5	P6
1	P3	0	10	1	0	1	0	2	-2
2	P4	0	2	-2	0	0	1	1	-1
3	P2	3	4	1	1	0	0	-1	-1
4			12	1	0	0	0	-3	-3
5			0	0	0	0	0	0	-1

Отриманий план не оптимальний

Обраний ключовий елемент (2,5)

I	базис	Cб	P0	2	3	0	0	0	-M
				P1	P2	P3	P4	P5	P6
1	P3	0	6	5	0	1	-2	0	0
2	P5	0	2	-2	0	0	1	1	-1
3	P2	3	6	-1	1	0	1	0	0
4			18	-5	0	0	3	0	0
5			0	0	0	0	0	0	-1

Отриманий план не оптимальний

Обраний ключовий елемент (1,1)

I	базис	Cб	P0	2	3	0	0	0	-M
				P1	P2	P3	P4	P5	P6
1	P1	2	6/5	1	0	1/5	-2/5	0	0
2	P5	0	22/5	0	0	2/5	1/5	1	-1
3	P2	3	36/5	0	1	1/5	3/5	0	0
4			24	0	0	1	1	0	0
5			0	0	0	0	0	0	1

План оптимальний

Розв'язок: X*(,) F*=24;

Розв'язок двоїстої задач

Побудуємо двоїсту функцію

3. ,

Система обмежень

Скористаємось теоремою

Якщо задача лінійного програмування в канонічній формі (7)-(9) має оптимальний план , то є оптимальним планом двоїстої задачі

, ,

Розв'язок:

Fmin*= 9,6;

Завдання 2. Задача цілочислового програмування

Для задачі із завдання 1, як для задачі цілочислового програмування, знайти розв'язки геометричним методом і методом Гоморі.

Розв?язання геометричним методом

Відповідь:

Розв?язання методом Гоморі

Наведемо останню симплекс-таблицю

I	базис	Cб	P0	2	3	0	0	0	-M
				P1	P2	P3	P4	P5	P6
1	P1	2	6/5	1	0	1/5	-2/5	0	0
2	P5	0	22/5	0	0	2/5	1/5	1	-1
3	P2	3	36/5	0	1	1/5	3/5	0	0
4			24	0	0	1	1	0	0
5			0	0	0	0	0	0	1

Побудуємо нерівність Гоморі за першим аргументом.

I	базис	Cб	P0	2	3	0	0	0	0
				P1	P2	P3	P4	P5	P7
1	P1	2	6/5	1	0	1/5	-2/5	0	0
2	P5	0	22/5	0	0	2/5	1/5	1	0
3	P2	3	36/5	0	1	1/5	3/5	0	0
4	P7	0	-1/5	0	0	-1/5	-3/5	0	1
5			24	0	0	1	1	0	0

Обраний розв'язковий елемент (4,4)

I	базис	Cб	P0	2	3	0	0	0	0
				P1	P2	P3	P4	P5	P7
1	P1	2	1	1	0	0	-1	0	0
2	P5	0	4	0	0	0	11/5	1	0
3	P2	3	7	0	1	0	0	0	0
4	P4	0	2	0	0	1	3	0	1
5			14	0	0	0	2	0	0

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

Розв'язок: X*(1,7) Fmax*=23;

Відповідь: цілочисельною точкою максимуму даної задачі є точка (1,7)

Завдання 3. Задача дробово-лінійного програмування

Для задачі дробово-лінійного програмування знайти розв'язки геометричним методом і симплекс-методом:

Розв?язання геометричним методом

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

f(1;0) = 2/3 f(0;1) = 3/7

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

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

З графіка очевидно, що розв'язок лежить на перетині двох прямих. Для визначення точки перетину прямої І та ІІ розв?яжемо систему з двох рівнянь.

Відповідь: функція набуває максимального значення при x1=6/5, x2=36/5.

Розв?язання симплекс-методом

Перейдемо від задачі дробово-лінійного програмування до задачі лінійного програмування.

Вводим заміну:

Вводим ще одну заміну:

Після замін наша задача має такий вигляд:

Приведемо її до канонічної форми і доповнимо її базисами:

Повернемось до заміни:

x1=0 x2=6

Завдання 4. Транспортна задача

Для заданих транспортних задач скласти математичну модель і розв'язати їх методом потенціалів, використавши для визначення початкового плану метод мінімального елемента або північно-західного кута.

1. Запаси деякого однорідного продукту знаходяться на трьох пунктах постачання (базах) A1, A2, A3 і цей продукт потрiбно доставити в три пункти споживання (призначення) B1, B2, B3. Задача полягає в тому, щоб визначити, яку кiлькiсть продукту потрiбно перевезти з кожного пункту постачання (бази) до кожного пункту споживання (призначення) так, щоб забезпечити вивезення всього наявного продукту з пунктів постачання, задовільнити повністю потреби кожного пункту споживання і при цьому сумарна вартiсть перевезень була б мiнiмальною (зворотні перевезення виключаються). Вартість перевезень сij (у грн.) з бази Аi до пункту призначення Bj вказана в таблиці, де також наведені дані про запаси ai (у тонанх) продукту і його потреби (у тонах) bj.

Пункти	Пункти споживання	Запаси
постачання	B1	B2	B3
A1	3	5	7	270
A2	6	9	4	180
A3	11	8	10	300
Потреби	260	280	300

Для даної транспортної задачі не виконується умова балансу , тому введемо додатковий пункт постачання з запасами 840-750=90 і тарифами С4s=0 (i=1,2,3). Тоді одержимо замкнену транспортну задачу, яка має розв'язок. Її математична модель має вигляд:

хi,

j 0, 1 i 4, 1 j 3.

Пункти	Пункти споживання	Запаси
постачання	B1	B2	B3
A1	3	5	7	270
A2	6	9	4	180
A3	11	8	10	300
A4	0	0	0	90
Потреби	260	280	300	840 840

За методом північно-західного кута знайдемо опорний план

Пункти	Пункти споживання	Запаси
постачання	B1	B2	B3
A1	3 260	5 10	7	270
A2	6	9 180	4	180
A3	11	8 90	10 210	300
A4	0	0	0 90	90
Потреби	260	280	300	840 840

За методом північно-західного кута опорний план має вигляд:

F=3*260+5*10+9*180+8*90+10*210+0*90=5270

Перевіримо чи буде він оптимальним.

Знаходимо потенціали для пунктів постачання

Для тих клітинок, де, розв'яжемо систему рівнянь

Знаходимо з системи:

Для тих клітинок, де, знайдемо числа

Оскільки , то план Х1 не є оптимальним. Будуємо цикл перерахунку

Пункти	Пункти споживання	Запаси
постачання	B1	B2	B3
A1	3		5		7	0	270
		260		10
A2	6	1	9		4	7	180
			-	180	+
A3	11	-5	8		10		300
			+	90	-	210
A4	0	-4	0	-2	0		90
						90
Потреби	260	280	300	840 840

В результаті перерахунку отримаємо

Пункти	Пункти споживання	Запаси
постачання	B1	B2	B3
A1	3 260	5 10	7	270
A2	6	9	4 180	180
A3	11	8 270	10 30	300
A4	0	0	0 90	90
Потреби	260	280	300	840 840

Наступний опорний план

F=3*260+5*10+9*180+8*90+10*210+0*90=4010

Для тих клітинок, де, розв'яжемо систему рівнянь

Знаходимо з системи:

Для тих клітинок, де, знайдемо числа

Отже план є оптимальним F=4010

Завдання 5. Задача квадратичного програмування

Розв'язати задачу квадратичного програмування геометричним методом та аналітичним методом, використовуючи функцію Лагранжа і теорему Куна-Таккера:

Розв'язання графічним методом

Графік кола має центр в точці (-1, 4)

X* (0 , 4); F*(X*)=-16

Розв'язання аналітичним методом

Складемо функцію Лагранжа:

Система обмежень набуде вигляду:

Перенесемо вільні члени вправо, і при необхідності домножимо на -1

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

Введемо додаткові змінні для утворення штучного базису

Розв'яжемо задачу лінійного програмування на знаходження мінімуму.

Введемо додаткові прямі обмеження на змінні.

Вектори з коефіцієнтів при невідомих:

Розв'язуємо отриману задачу звичайним симплекс-методом

I	базис	Cб	P0	0	0	0	0	0	0	0	0	0	0	M	M
				Px1	Px2	Py1	Py2	Py3	Pu1	Pu2	Pv1	Pv2	Pv3	Pz1	Pz2
1	Pz1	M	2	-2	0	-3	1	1	-1	0	0	0	0	1	0
2	Pu2	0	8	0	2	2	1	-1	0	1	0	0	0	0	0
3	Pv1	0	18	-3	-2	0	0	0	0	0	1	0	0	0	0
4	Pv2	0	6	-1	1	0	0	0	0	0	0	1	0	0	0
5	Pz2	M	4	1	1	0	0	0	0	0	0	0	-1	0	1
5				-M	M	-3M	M	M	-M	0	0	0	-M	0	0

Обраний розв'язковий елемент (5,2)

I	базис	Cб	P0	0	0	0	0	0	0	0	0	0	0	M	M
				Px1	Px2	Py1	Py2	Py3	Pu1	Pu2	Pv1	Pv2	Pv3	Pz1	Pz2
1	Pz1	M	2	-2	0	-3	1	1	-1	0	0	0	0	1	0
2	Pu2	0	0	-2	0	2	1	-1	0	1	0	0	2	0	0
3	Pv1	0	26	-1	0	0	0	0	0	0	1	0	-2	0	0
4	Pv2	0	2	-2	0	0	0	0	0	0	0	1	1	0	0
5	Px2	0	4	1	1	0	0	0	0	0	0	0	-1	0	1
5			2М	-2М	0	-3М	М	M	-М	0	0	0	0	0	0

Обраний розв'язковий елемент (2,4)

I	базис	Cб	P0	0	0	0	0	0	0	0	0	0	0	M	M
				Px1	Px2	Py1	Py2	Py3	Pu1	Pu2	Pv1	Pv2	Pv3	Pz1	Pz2
1	Pz1	M	2	0	0	-5	0	2	-1	-1	0	0	-2	1
2	Py2	0	0	-2	0	2	1	-1	0	1	0	0	2	0
3	Pv1	0	26	-1	0	0	0	0	0	0	1	0	-2	0
4	Pv2	0	2	-2	0	0	0	0	0	0	0	1	1	0
5	Px2	0	4	1	1	0	0	0	0	0	0	0	-1	0
5			2M	0	0	-5M	0	2M	-M	-M	0	0	-2M	0

Обраний розв'язковий елемент (1,5)

I	базис	Cб	P0	0	0	0	0	0	0	0	0	0	0	M	M
				Px1	Px2	Py1	Py2	Py3	Pu1	Pu2	Pv1	Pv2	Pv3	Pz1	Pz2
1	Py3	0	1	0	0	-5/2	0	1	-1/2	-1/2	0	0	-1
2	Py2	0	1	-2	0	-1/2	1	0	-1/2	-1/2	0	0	1
3	Pv1	0	26	-1	0	0	0	0	0	0	1	0	-2
4	Pv2	0	2	-2	0	0	0	0	0	0	0	1	1
5	Px2	0	4	1	1	0	0	0	0	0	0	0	-1
5			0	0	0	0	0	0	0	0	0	0	0

План отриманий в результаті розв'язування задачі симплекс-методом, не є оптимальним так як він не задовольняє умови:

Отже перерахуємо симплекс-таблицю ще раз.

Обраний розв'язковий елемент (2,7)

I	базис	Cб	P0	0	0	0	0	0	0	0	0	0	0
				Px1	Px2	Py1	Py2	Py3	Pu1	Pu2	Pv1	Pv2	Pv3
1	Py3	0	10	0	2	-3	1	1	-1	0	0	0	-2
2	Pu2	0	18	0	4	-1	2	0	-1	1	0	0	-2
3	Pv1	0	30	0	1	0	0	0	0	0	1	0	-3
4	Pv2	0	10	0	2	0	0	0	0	0	0	1	-1
5	Px2	0	4	1	1	0	0	0	0	0	0	0	-1
5			0	0	0	0	0	0	0	0	0	0	0

Отриманий план оптимальний X* (0,4); F*(X*)=-16

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

1. Карманов В. Г. Математическое программирование: Учеб. пособие. -- 5-е издание., стереотип. -- М.: ФИЗМАТЛИТ, 2001. -- 264 с.

2. Моисеев Н. Н., Иванилов Ю. П., Столярова Е. М. Методы оптимизации --М.: Наука, 1978. -- 352 с.