- •2.Умножение вектора на число.Свойства операций сложения и умножения.
- •4. Декартова система координат. Действия с векторами в этой системе
- •7. Угол между n-мерными векторами. Условие ортогональности вектора.
- •8. Матрицы. Действия с матрицами и их свойства.
- •12. Частные случаи разложения векторов
- •16. Свойства линейно зависимых и линейно независимых систем векторов
- •17, 18. Базис системы векторов. Алгоритм построения базиса системы векторов. Основные теоремы о базисах системы векторов.
- •22. Свойства определителей
- •23.Алгебраическое дополнение
- •24. Вычисление определителей
- •25. Линейные уравнения. Виды линейных уравнений.
- •26. Системы линейных уравнений. Формы записи систем уравнений.
- •27. Теорема о совместности системы линейных уравнений.
- •28. Теорема об определенности системы уравнений
- •29. Теорема Крамера
- •30. Метод Гаусса
- •31. Однородные системы линейных уравнений
- •32. Фундаментальная система решений однородной системы линейных уравнений.
- •33. Общее решение системы линейных уравнений
- •34. Предмет лп. Матем модель эк зад
- •35. Общая задача линейного программ-ия
- •36. Мат.Модели эк.Задач.
- •37. Каноническая форма линейного прогр-ния
- •38. Приведение общей задачи лп к канон.Форме:
- •39. Графический метод решения злп.
- •40. Графический метод решения задачи лин прогр-ния с n переменными(неизвестными).
- •43. Допустимые преобразования канонической задачи
- •44. Разрешенная каноническая задача лин прогр-ния
- •45. Симплексный метод решения задач
- •48. Понятие о двойств.Задачах. Мат.Модель 2-ной злп.
- •49. Правила составления двойственной задачи
- •50. Первая теорема двойственности
- •51. Вторая теорема двойственности
- •52. Тзлп.
- •53. Необходимое и достаточное условие разрешимости транспортной задачи
- •54. Понятие цикла.Условие опорности допустимого решения. Метод вычёркивания проверки опорности решения задачи.
- •55. Метод минимальной стоимости.
- •57. Распределительный метод решения тз.
- •58. Метод потенциалов.Его алгоритм.
- •59. Особенности реш-я тз с неправ.Балансом.
50. Первая теорема двойственности
1) Если одна из пары двойственных задач имеет оптимальное решение,то и двойственная к ней имеет оптимальное решение,причём значения целевых ф-ий на своих оптимальных решениях совпадают.
2)Если одна из пары двойственных задач не имеет решения ввиду неограниченности целевой ф-ии,то и другая не имеет решения ввиду несовместности системы ограничений.
Если одна из пары двойственных задач имеет оптимальное решение, то и двойственная к ней имеет оптимальное решение, причем значения целевых функций на своих оптимальных решениях совпадает.
Если одна задача не имеет решения в виду неограниченности целевой функции, то другая не имеет решения в виду несовместности системы ограничений.
Z (x)= cixi -> max
F(y)= bj yj
aij xij ≤ bi (i=1,2,m) , xj=0
a ij y I ≥ cj (j=1;2;n) , yi≥0
xj aij yi ≥ xjcj
yi aij xj≤ yibi
yj aij xij≤ yibj
yi aij xj≤ yibi
xjcj≤ yibi
Z(x) = x1+x2+2x3->min
x1-x2-x3≥1 │y1
-2x1+3x2≥1│y2
3x1-4x2+2x3≥-1 │y3
F(y)=y1+y2-y3 -> max
y1+y2-y3->max
y1-2y2+3y3 ≤1
-y1+3y2-4y3≤1
-y1+2y3≤2
y 1,2,3≥0
Ɵ1 Ɵ2
1 -2 3 1 0 0│1│- │-
-1 3 -4 0 1 0│1│-│1/3
-1 0 2 0 0 1│2│-│-
――――――――――
-1 -1 1 0 0 0 │0
――――――――――
1 -2 3 1 0 0 │1
0 1 -1 1 1 0 │2
0 -2 5 1 0 1 │3
―――――――――
1 0 1 3 2 0 │5
0 1 -1 1 1 0 │2
0 0 3 3 2 1 │7
―――――――――
0 0 1 4 3 0 │7
Если в сопряженной задаче на max получено оптимальное решение, то решением задачи на min будут являться коэффициенты целевой строки последней симплексной таблицы стоящие под базисом опорного решения.
51. Вторая теорема двойственности
Для того,чтобы допустимые решения X=(x1 ,x2 ,xn ) и Y=(y1 ,y2 ,yn ) являлись оптимальными решениями пары двойственных задач необходимо и достаточно,чтобы выполнялись следующие равенства:
Xj(Σ aij yi – cj)=0 j=1,2….,n
Yi(Σ aij xj – bi)=0 i=1,2….,m
Другими словами: Если при подстановке оптимального решения в систему ограничений i-е ограничение выполняется как строгое неравенство,то i-ая координата двойственной задачи=0 и наоборот если i-ая координата оптимального решения положительна,то i-ое ограничение двойственной задачи удовлетворяется оптимальным решением как равенство.
52. Тзлп.
53. Необходимое и достаточное условие разрешимости транспортной задачи
Для того,чтобы транспортная задача лин.программирования имела решение необходимо и достаточно,чтобы суммарные запасы поставщиков равнялись суммарным запросам потребителей.
ai= bj –задача с правильным балансом
Ранг системы в-ров-усл-й ТЗЛП равен m+n-1/
54. Понятие цикла.Условие опорности допустимого решения. Метод вычёркивания проверки опорности решения задачи.
Циклом называется такая последовательность клеток таблицы
(I ;j ), (I ; j ), (I ; j )…..(I ;j ) в к-й 2 и только 2 соседние клетки цикла расположены в одной строке или столбце,причём первая и последняя тоже находятся в одной строке или столбце. Цикл-замкнутая ломаная линия.
Допустимое решение транспортной задачи-X является опорным т/т/т,когда из занятых клеток таблицы нельзя составить ни одного цикла.
Метод вычёркивания: для проверки возможности образования цикла используется так называемый метод вычёркивания,к-й состоит в следующем.
Если в строке или столбце таблицы одна занятая клетка,то она не может входить в какой-либо цикл,т.к цикл имеет 2 и только 2 клетки в каждой строке или в столбце. След-но,можно вычеркнуть все строки таблицы,содержащие по одной занятой клетке,затем вычеркнуть все столбцы,содержащие по одной занятой клетке,далее вернуться к строкам и продолжить вычёркивание строк и столбцов. Если в результате вычёркиваний все строки и столбцы будут вычеркнуты,значит,из занятых клеток таблицы нельзя выделить часть,образующую цикл,и система соответствующих векторов условий является лин.-независимой,а решение-опорным. Если же после вычёркиваний останется часть клеток,то эти клетки образуют цикл,система соответствующих векторов условий линейно зависима,а решение не является опорным.