Канонічна задача:
Знайти max функції f=3x1-4x2-2x3 на множині невід’ємних розв’язків системи рівнянь
5.Розв’яжемо симплекс-методом канонічну задачу.
Знаходимо будь-який базисний невід’ємний розв’язок системи лінійних рівнянь.
Ранг цієї системи r =4, отже,
Оскільки ранг системи дорівнює 4, то за вільні невідомі можна обрати x1, x6, x7, за основні базисні невідомі - x2, x3, x4, x5.
Нехай x1 = x6 = x7 = 0, тоді x2=3; x3=4; x4=3; x5=2 - невід’ємний розв’язок системи лінійних рівнянь. Виражаємо цільову функцію f через вільні невідомі x1, x6, x7, одержуємо 
Отже 
, і система лінійних рівнянь – обмежень рівносильна системі обмежень функції, виражаємо через вільні невідомі:
Складаємо симплекс – таблицю 1.
| Базисні невідомі | X1 | X2 | X3 | X4 | X5 | X6 | X7 | Вільні члени |
| -1 | |||||||
| -1 | |||||||
| ||||||||
| -1 | |||||||
| -3 | -20 |
Оптимального розв’язку немає; в рядку f є від’ємний коефіцієнт. Переходимо до таблиці 2.
| Базисні невідомі | X1 | X2 | X3 | X4 | X5 | X6 | X7 | Вільні члени |
| X2 | -1 | |||||||
| X3 | -1 | |||||||
| X1 | ||||||||
| X5 | ||||||||
| f | -11 |
Оскільки в рядку f таблиці 2 всі коефіцієнти додатні, то оптимальний розв’язок канонічної задачі одержано:
max f = -11 при додатньому розв’язку (3,3,4,0,5,0,0) системи.
Отже, отриманий розв’язок стандартної задачі є max f = -11 при значеннях невідомих системи обмежень (3,3,4).
Контрольна робота № 6
Дано множини відносно добутку
Задачі.
1. Довести, що D – група.
2. Довести, що К – група.
3. Побудувати таблицю Келі для D.
4. Побудувати таблицю Келі для К.
5. Знайти всі твірні елементи для групи D.
6. Знайти всі твірні елементи для групи К.
7. Знайти всі підгрупи і їх твірні в групі D.
8. Знайти всі підгрупи і їх твірні в групі К.
9. Розкласти групу D на класи спряжених елементів.
10. Розкласти групу К на класи спряжених елементів.
11. Розкласти групу D на ліві суміжні класи.
12. Розкласти групу К на ліві суміжні класи.
13. Довести, що в групі К кожна підгрупа – інваріантна.
14. Знайти нормальний дільник в групі D.
15. Побудувати фактор-групу групи К.
16. Побудувати фактор-групу групи D.
17. Довести, якщо | a | = n і ak = 1, то n ділить k.
18. Довести, якщо | g | = n, то " g Î G gk =1 тоді і тільки тоді, коли k ділиться на n.
19. Довести, якщо | G | = pq, p, q – різні прості числа і G – абелева, то в G існує елемент а, | a | = pq.
20. Довести, якщо | G | = pq, p ¹ q – прості числа, то в G існує інваріантна підгрупа.
21. Довести, якщо | G | = p 2, то вона або циклічна, або абелева.
22. Нехай C 1 – підкільце кільця C, I – ідеал кільця C. Довести, що C 1Ç I – ідеал кільця C 1.
23. Довести, що в кільці цілих чисел Z кожен його ідеал – головний.
24. Довести, що при гомоморфізмі j двох кілець K 1 і K 2 j(a – b)= j(a)–j(b).
25. Довести, що при гомоморфізмі j двох кілець K 1 і K 2 j(a –1) = [j(a)]–1 (якщо в K 1 для а існує обернений елемент a –1).
26. Довести, що будь-який ідеал I кільця С є ядром гомоморфізму при відображення кільця С на фактор-кільце C / I.
27. Довести, що підмножина I кільця С є ядром гомоморфізму цього кільця на деяке кільце тоді і тільки тоді, коли I є ідеалом кільця С.
28. Довести, що характеристика будь-якого числового кільця дорівнює нулю.
29. Довести, що найменше підполе будь-якого поля характеристики нуль ізоморфне полю раціональних чисел.
30. Довести, що в кільці Z [ i ] простими є такі елементи: 3; 2 + i.
31. Довести, що в кільці Z [ i ] простими є такі елементи: –3; 2 – i.
32. Довести, що в кільці 
порушується однозначність розкладу на прості множники.
33. Довести, що в кільці 
порушується однозначність розкладу на прості множники.
| Варіант | Задачі |
| № 1, 3, 5, 7, 9, 11, 14, 18, 22, 24, 26, 28, 31 | |
| № 2, 4, 6, 8, 10, 12, 15, 17, 21, 23, 25, 29, 30 | |
| № 1, 3, 7, 11, 13, 19, 22, 26, 29, 23, 32, 27 | |
| № 2, 4, 6, 8, 11, 13, 15, 19, 23, 24, 27, 31, 28 | |
| № 1, 3, 5, 7, 9, 14, 16, 23, 27, 30, 22, 29, 33 | |
| № 2, 4, 6, 8, 10, 12, 15, 17, 20, 24, 27, 28, 31 | |
| № 1, 3, 5, 7, 9, 14, 20, 22, 25, 26, 28, 30, 32 | |
| № 2, 4, 6, 8, 10, 12, 16, 18, 20, 22, 24, 26, 30 | |
| № 1, 3, 5, 7, 9, 11, 13, 15, 17, 19, 21, 23, 31 | |
| № 2, 4, 6, 8, 10, 13, 18, 15, 20, 24, 26, 28, 32 |
Зразки розв’язання задач контрольної роботи № 6
1. Довести, що множина
відносно множення підстановок є групою.
Розв‘язання.
Під множенням підстановок розуміють їх послідовне виконання. Необхідно показати, що множина G:
1) замкнена відносно операції (×);
2) виконується для елементів множини асоціативний закон множення;
3) існує нейтральний елемент відносно цієї операції;
4) кожний елемент множини має обернений.
Складаємо таблицю Келі для операції (×) на множині G.
| S 1 | S 2 | S 3 | S 4 | S 5 | S 6 | |
| S 1 | S 1 | S 2 | S 3 | S 4 | S 5 | S 6 |
| S 2 | S 2 | S 3 | S 1 | S 6 | S 4 | S 5 |
| S 3 | S 3 | S 1 | S 2 | S 5 | S 6 | S 4 |
| S 4 | S 4 | S 5 | S 6 | S 1 | S 2 | S 3 |
| S 5 | S 5 | S 6 | S 4 | S 3 | S 1 | S 2 |
| S 6 | S 6 | S 4 | S 5 | S 2 | S 3 | S 1 |
Операцію (×) задано так:
.
За таблицею видно, що всі групові властивості виконуються на множині відносно заданої на ній операції (×).
Отже, G – група. Вона називається симетричною групою третього степеня (S 3).
2) Знайти всі твірні елементи групи S 3.
Розв‘язання.
Група S 3 є групою 6-го порядку. Отже, всі її елементи мають скінчений порядок, який за теоремою Лагранжа є дільником порядку групи. Отже, в групі S 3 є елементи другого та третього порядків.
Елементи s 2, s 3 – елементи третього порядку, так як (s 2)3 = (s 3)3 = s 1.
Елементи s 4, s 5, s 6 – елементи другого порядку, так як (s 4)2 = (s 5)2 = (s 6)2 = s 1.
Отже, група S 3 – це неабелева група і породжується відповідно елементом порядку 3 і елементом порядку 2, тобто
S 3 = { s 2, s 4} = { s 2, s 5} = { s 2, s 6} = { s 3, s 5} = { s 3, s 4} = { s 3, s 6}.
3) Знайти всі підгрупи групи S 3.
Розв‘язання.
За теоремою Лагранжа порядок підгрупи є дільником порядку групи. Тому група S 3 може мати власні підгрупи порядків 3 та 2 і невласні підгрупи: E, S 3.
Підгрупою 3-го порядку є підмножина групи S 3, що складається із елементів < s 1, s 2, s 3> і підгрупами 2-ого порядку є підмножини групи S 3, що складаються із елементів < s 1, s 4>, < s 1, s 5>, < s 1, s 6>.
Підгрупа G 1 = < s 1, s 2, s 3> = { s 2} = { s 3}; G 2 = < s 1, s 3> = { s 3};
G 3 = < s 1, s 5> = { s 5}; G 4 = < s 1, s 6> = { s 6}.
Отже, будь-яка власна підгрупа групи S 3 – циклічна, тобто складається із степенів одного із своїх (твірного) елементів.
3. Розкласти групу S 3 на класи спряжених елементів.
Розв‘язання.
Оскільки s 1 утворює окремий клас спряжених елементів як одиниця групи S 3; елементи s 2, s 3 порядку 3 утворюють клас спряжених елементів, так як
si –1× s 3× si = s 2, si –1× s 2× si = s 3;
елементи s 4, s 5, s 6 порядку 2 спряжені, так як
s 5 s 4 s 5 = s 6, s 6 s 5 s 6 = s 4, s 4 s 5 s 4 = s 6,
а тому належать одному класу спряжених елементів. Отже,
S 3 = < s 1> + < s 2, s 3> + < s 4, s 5, s 6 >.
4. Розкласти групу S 3 на ліві суміжні класи за її підгрупою G 2 = < s 1, s 6>.
Розв‘язок.
Лівосторонній розклад групи S 3 за її підгрупою G 2 складається із класів: G 2, s 2 G 2 = s 4 G 2 = { s 2, s 4}, s 5 G 2 = s 6 G 2 = { s 4, s 6}.
S 3 = G 2 È{ s 2, s 4}È{ s 4, s 6}.
5. Знайти нормальний дільник в групі S 3.
Розв‘язання.
Для того, щоб підгрупа групи була її нормальним дільником необхідно і достатньо, щоб ліві і праві суміжні класи за цією підгрупою співпадали. Отже, в симетричній групі S 3 підгрупа G 1 = < s 1, s 2, s 3> є нормальним дільником групи, так як лівосторонні і правосторонні розклади групи S 3 за підгрупою G 1 співпадають: кожен з них складається з двох класів: G 1 i < s 4, s 5, s 6>,
S 3 = G 1È G 1 s 4 = s 4 G 1 = { s 4, s 5, s 6}.
6. Побудувати фактор-групу групи S 3 за підгрупою G 1.
Розв‘язання.
Сукупність суміжних класів групи S 3 за її нормальною підгрупою G 1 відносно операції множення класів утворює групу, яка називається фактор-групою групи S 3 за підгрупою G 1 (S 3/ G 1).
На множині класів введемо операцію множення siG 1× sjs 1 = si × sjs 1, si, sj Î S 3, s 1 – нормальна підгрупа.
Доведемо, що одержалася група.
7. Асоціативність множення класів випливає з асоціативності множення в групі S 3:
(siG 1× sjs 1)× skG 1= (sisj) s 1× skG 1 = (sisj)× skG 1= si (sj × sk) G 1 =
= siG 1×(sj × sk) G 1= siG 1×(sjG 1× skG 1)
8. Одиничним елементом є сама підгрупа G 1:
G 1× siG 1= s 1 G 1 ×siG 1 = s 1 siG 1 = siG 1,
siG 1 ×G 1 = siG 1 ×s 1 G 1 = sis 1 G 1 = siG 1.
9. Оберненим до класу siG 1 є клас si –1 G 1, так як
siG 1× si –1 G 1 = si × si –1 G 1 = eG 1 = G 1,
si –1 G 1× siG 1 = si –1× siG 1 = eG 1 = G 1.
Одержана група позначається через S 3/ G 1 і називається фактор-групою групи S 3 за нормальною підгрупою G 1.
S 3/ G 1 = < G 1, s 4 G 1>.
7. Довести, якщо | a | = n і ak = 1, то n ділить k.
Розв‘язання.
Нехай порядок елемента а групи G дорівнює n. Це означає, що n – мінімальне натуральне число таке, що an = 1. Якщо k – будь-яке ціле число, то поділимо k на n, одержуємо
k = nq + r, 0 £ r < n,
а тому ak = (an) q × ar = ar.
Звідси випливає, якщо елемент а має скінчений порядок n і ak = 1, то n ділить k.
8. Довести, якщо | G | = pq, p ¹ q – прості числа, то в G існує інваріантна підгрупа.
Розв‘язання.
Нехай p, q – прості числа,. Силовські p - і q -підгрупи групи G, будучи підгрупами простого порядку, є циклічними. Нехай { a }, { b }– відповідно силовські p - і q- підгрупи. за теоремою Силова кількість силовських підгруп в G дорівнює 1 + kq і ділить pq, тому силовська q -підгрупа { b } єдина. Зокрема, вона нормальна в групі G, що і треба було довести.
9. Нехай К 1 – підкільце кільця К, І – ідеал кільця К. Довести, що К 1Ç I – ідеал кільця К.
Розв‘язання.
Позначимо D = К 1Ç I. Покажемо, що ідеал І, як і будь-який ідеал, містить нуль-елемент кільця К. Оскільки І ¹0, то в І існує хоч один елемент а. Тоді за означенням ідеалу, елемент а – а = 0 теж належить ідеалу I. Оскільки 0Î К, 0Î І, то 0Î D, тому D ¹Æ.
Якщо а, b Î D, то а, b Î К і а, b Î І. Згідно з означенням ідеалу і критерієм підкільця 
, а тому 
.
Нехай а Î D, b Î К 1. Покажемо, що ab і ba належать D. Оскільки D Í І, а І – ідеал кільця К, то для будь-якого елемента а Î D Í І і будь-якого елемента b Î К 1 Í K маємо, що ab, ba Î І.
Отже, ab, ba Î К 1Ç I = D. Тому D = К 1Ç I – ідеал кільця К 1.
10. Довести, що при гомоморфізмі j двох кілець K 1 і K 2 j(a – b) = j(a) – j(b).
Розв‘язання.
Нехай j – гомоморфізм кільця K 1 на кільце K 2.
Тоді за означенням гомоморфізму виконується рівність " a, (– b)Î К 1
j(a + (– b) = j(a) + j(– b), j(– b) = – j(b).
Отже, j(a + (– b) = j(a – b) = j(a) – j(b), що і треба було довести.
11. Довести, що характеристикою області цілісності є або нуль, або просте число.
Розв‘язання.
Нехай К – область цілісності, а е – одиниця кільця К. Якщо для me ¹0 жодного натурального числа m, то характеристика кільця К дорівнює нулю.
Нехай me =0 і m – найменше натуральне число, що має цю властивість, тобто m – характеристика кільця К. Тоді m ¹1, оскільки е ¹0. Якщо m – просте число, то твердження задачі доведено.
Нехай m – складене число. Тоді існують натуральні числа s і t такі, що 1 < s, t < m і m = st. Так як кільце K комутативне, маємо
0 = me = (st) × e = (se) × (te).
Крім того, оскільки m – характеристика кільця К і s < m, t < m, то se ¹0, te ¹0, і тому (se) × (te) = me ¹0, бо К як область цілісності, є кільцем без дільників нуля. Отже, прийшли до протиріччя.
12. Довести, що число 4 в кільці 
неоднозначно розкладається в добуток простих множників.
Розв‘язання.
Знайдемо дільники одиниці в . Нехай 
, 
– дільники одиниці, a, b, c, d Î Z. Тоді
()() = 1.
Знайдемо норму обох частин цієї рівності
. (*)
Норма числа знаходиться за формулою Nr () = 
.
Рівність (*) виконується, якщо 
. (**) Рівність (**), в свою чергу, виконується при 
.
Отже, в кільці лише два дільники одиниці: 1, –1.
Доведемо, що для числа 4 в кільці є два різні розклади в добуток простих множників: 
.
Покажемо, що 2, 
є прості числа в , а пари чисел 2, 
та 2, 
не є асоційованими. Оскільки в кільці асоційовані числа відрізняються тільки знаком, то покажемо, що 2, є прості числа в . Якщо 
, то знайшовши норми від обох частин, дістанемо 
.
Число 4 розкладається в добуток натуральних чисел двома способами: 4=2×2 =1×4.
Якщо 
, то b 2 < 1, тобто b =0. Тоді a 2 = 2, що неможливо для цілого числа a. Отже, 
або 
.
Якщо , то – дільник одиниці.
Якщо , то 
і – дільник одиниці. Отже, 2 є просте число в кільці . Оскільки 
, то аналогічно доводять, що числа 
є простими. Отже, число 4 в кільці розкладається на прості множники двома різними способами.
13. Довести, якщо поле Р має характеристику р, то р – просте число.
Розв‘язання.
Нехай р – число складене і p = st, де s < p, t < p. Тоді одержуємо
тобто (se)×(te) = 0.
Оскільки в полі не існує дільників нуля, то із рівності (se)×(te) = 0 випливає, що або se = 0, або te = 0, а це суперечить умові, що поле Р має характеристику р. отже, припущення, що р – складене число, невірне.
