шпоры - 2 курс 2 семестр

1. Какая система векторов a1,…..an называется линейно зависимой и линейно независимой? Система единичных векторов ортогонального n-мерного пространства линейно зависима или линейно независима?

Система векторов a1, a2,…am называется линейно зависимой, если хотя бы один из е векторов может быть представлен в виде линейной комбинации остальных. Система называется линейно независимой, если ни один из ее векторов не может быть представлен в виде линейной комбинации остальных векторов.

Теорема. Для того, чтобы система векторов была линейно зависимой, необходимо и достаточно, чтобы существовал такой набор чисел μ1a1 + μ2a2+ …+ μmam=0

Необходимость. Пусть система линейно зависима. Тогда какой-либо вектор, например a1,можно представить в виде линейной комбинации остальных:

a1=λ2a2+ λ3a3+…+λmam Отсюда следует, что –a1 + λ2a2 + λ3a3 +…+ λmam = 0. Таким образом, имеем равенство вида, в котором μ1 = -1; μ2= λ2, …, μm = λm, т.е. μ1ǂ 0.

Достаточность. Пусть существует набор чисел μ1, μ2,…, μm, в котором, например μ1ǂ 0 и для которого выполняется равенство. Тогдаa1=- μ2/ μ1*a2 – μ3/ μ1*a3 - …- μm/ μ1*am ,

Т.к. вектор a1 представлен в виде комбинации остальных, что означает линейную зависимость системы векторов.

Из доказательства теоремы следует, что система линейно независима тогда и только тогда, когда равенство –a1 + λ2a2 + λ3a3 +…+ λmam = 0 справедливо лишь при условии, что μ1 = μ2=…= μm = 0

4.Дайте определение матрицы, обратной квадратной матрице А. Какое условие является необходимым и достаточным условием существования обратной матрицы?

Пусть задана кв. матрица А.Если сущ-т матрица В, такая что А*В=Е,то гов что матрица В явл обратной по отношению к мат А: В=А^-1, А*А^-1=Е.

Свойства: 1)Обратная и исходная матрицы перестановочны и матрица,обратная обратной, совпадает с исходной:

А*А^-1=А^-1*А=Е.

2)Единственность матрицы: если для данной матрицы обратная мат сущ-т,то она только одна.

Как выяснить явл ли кв. матрица обратной? Пусть исход матрица А имеет вид: а₁₁ а₁₂ а₁₃

А= а₂₁ а₂₂ а₂₃

а₃₁ а₃₂ а₃₃

Предпол что имеется какая-то мат В, В=(х_ij)=А^-1,кот явл обратной по отношению к исходной мат-це А. Тогда должно выполняться:

а₁₁ а₁₂ .. а_1n x₁₁ x₁₂ .. x_1n 10….0

а₂₁ а₂₂ .. а_2n * x₂₁ x₂₂ .. x_2n = 010...0

…………… ………….. …….

а₃₁ а₃₂ .. а_3n x_m1 x_m2 .. x_mn 000001

Это матричное ур-е можно переписать в виде системы n² линейных ур-й с n² неизвестными.

3)Квадратная матрица обратима тогда и только тогда, когда она является невырожденной.

7. дайте определения:

• разрешающая неизвестная

• разрешающее уравнение

• базисная и свободная переменная

• базисное и общее решение

В качестве разрешающей неизвестной можно принять любую неизвестную, при которой есть хоть один положительный коэффициент, а затем в качестве разрешающего уравнения следует взять то уравнение, которое соответствует наименьшему среди отношений свободных членов уравнений к соответствующим положительным коэффициентам при выбранной неизвестной в этих уравнениях.

Неизвестные типа X1,X2, …, Xm называют базисными , неизвестные Xm+1, X m+2, Xn – свободные.

Так как значения свободных неизвестных можно найти бесконечно много решений системы, называемых ее частными решениями, т.е. в этом случае система является совместной и неопределенной. Выражения базисных неизвестных через свободные вида

X1=h1-g1,m+1 - …- g1nxn ,

Xm = gm,m+1xm+1 - … - gmnxn

естественно назвать общим решением СЛАУ. Среди частных решений системы выделяются базисное , отвечающее нулевым значениям свободных неизвестных :

X1 = h1, x2 = h2, …, xm = hm, xm+1 = 0, …,Xn = 0

\

2.В каком случае вектор b можно назвать линейной комбинацией векторов a1 … an ?

Вектором называется упорядоченный набор чисел. Числа в векторе с учетом их расположения по номеру в наборе называются компонентами вектора. Число компонент вектора называется его размерностью.

В-р является линейной комбинацией в-ров , если его можно представить как сумму произведений данных в-ров на какие-либо числа - коэффициенты линейной комбинации.

5.СЛАУ решается методом Жордана- Гаусса. Каким образом в процессе решения убедиться в том, что СЛАУ:

1)не имеет решения?

2)имеет уравнение, являющееся линейной комбинацией каких-либо других уравнений системы?

Суть метода состоит в том, что за счёт элементарных преобразований, за конечное число шагов система приводится к так называемому, предпочитаемому или каноническому виду, кот легко исслед-ся и решается. Выбирается разрешающее ур-е, в кот выбирается неизвестная, коэф-т при кот отличен от нуля (разреш-ая неизвестная), а коэф-т при ней назыв разрешающий коэф-т. Путём элем-х преобразований разреш-ая неизвестная искл-ся из всех урав-й системы кроме разрешающей. Берётся след ур-е и след разреш-ая перем-ая отличная от первой, далее путём элем-х преобр-й она искл-ся из всех ур-й системы кроме разрешающей и т.д. Пример: а₁₁х₁+а₁₂х₂+а_1nх_n=b_{1 –} разреш урав-е

а₁₁0 а_m1х₁-разреш перем-ая

нужно искл х₁ из всех ур-й кроме разрешающего. Нужно 1-е ур-е умножить на (-а₂₁/а₁₁)=

-а₂₁х₁- а₁₂*а₂₁/а₁₁*х₂ -…- а₂₁*а_1n/а₁₁*х_n=-b₁*а₂₁/а₁₁ + 2 ур-е системы

В рез-те преобр-й возможны след.случаи:

1) в процессе реш-я появл равенства 0*х₁+0-х₂+…+0-х_n=b_i в_i0 при появл такого равенства пишем что сис-ма несовместна.

2) левая и правая части i ур-я обращ-ся в 0, т.е.0=0  данное ур-е явл линейной комбинацией ур-й вход-х в эту систему, в этом случае это ур-е исключается из всей системы

3) После того как будут получены решения системы, либо будет доказана её несовместность, система будет приведена к следующему виду:

х₁ + q_1,m+1*x_m+1 + … + q_1n*х_n=h₁

х₂ + q_2,m+1*x_m+1 + … + q_2n*х_n=h₂

_. . . . . . . . . . . . . . .

х_m + q_m,m+1*x_m+1 + … + q_mn*х_n=h_m

В этом случае говорят, что СЛАУ приведена к предпочитаемому или каноническому виду.

8) Матрица А=a_i,j, i,j=1,2,3. Разложите определитель матрицы А по элементам второго столбца?

a₁₁ a₁₂ a₁₃

А= a₂₁ a₂₂ a₂₃

a₃₁ a₃₂ a₃₃

1 2 3

4 5 6 = -2* 4 6 + 5*1 3 – 8* 1 3=

7 8 9 7 9 7 9 4 6

9) Дайте определение ранга матрицы размером m*n. Определите ранг матрицы (матрица задана).

Рангом системы n-мерных в-ров называется максимальное число линейно независимых в-ров этой системы. ранг системы единичных в-ров равен n.

Ранг системы в-ров не изменяется, если она подвергается элементарным преобразованиям:

• Умножение какого-нибудь в-ра системы на число, отличное от 0;

• Прибавление к какому-нибудь в-ру системы другого в-ра этой же системы, умноженного на число.

• Перестановка каких-либо в-ров системы.

У матрицы размером mxn можно рассматривать строки как n-мерные в-ры, а столбцы как m-мерные в-ры.

Ранг системы строк – строчный ранг. Ранг системы столбцов – столбцовый ранг. Таким образом, в прямоугольной матрице они всегда равны.

Ранг матрицы – максимальное число линейно независимых рядов.

3. Ввести необходимые векторы и матрицы и записать в векторно-матричной форме следующую задачу (дана задача ЛП, записанная в обычном виде).

Система из k ур-ний первой степени с n неизвестными им.след.вид:

a₁₁x₁+a₁₂x₂+…+a_1nx_n=b_{1 , где b – cвоб.члены;}

a₂₁x₁+a₂₂x₂+…+a_2nx_n=b₂

………………………..

a_m1x₁+a_m2x₂+…+a_mnx_n=b_m

Составим матрицу А из коэф-тов при неизвестных системы лин.алгебр.ур-ний. Она наз.матрицей системы,а матрицу A , получающуюся добавлением к А столбца своб.членов системы, наз.расширенной матрицей:

а₁₁ а₁₂ a_1n а₁₁ а₁₂ a_1n b₁

А= а₂₁ а₂₂ а_2n A = а₂₁ а₂₂ а_2n b₂

_{…………………………… ……………………………}

а_k1 а_k2 а_kn а_k1 а_k2 а_kn b_k

Введем в рассмотрение векторы-столбцы(матрицы-столбцы): a_j-коэф-ты при неизвестной x_j (j=1…n), b –своб.члены, x-неизвестные:

а_1j b₁ x₁

а_j= а_2j b= b₂ x= x₂

_{………………………………………………….}

а_kj b_k x_k

Очевидно, левые части ур-ний исх.сист. совпадают с эл-тами матрицы-произв-я Ах, а j-е слагаемые во всех ур.системы предст. собой эл-ты вектора-столбца a_jx_j, получаемого умножением вектора a_j на число x_j. Поэт.исх.СЛАУ м.зап. в векторной и матричной формах:

a₁x₁+a₂x₂+…+a_nx_n=b или Ax=b. прим(А-затраты,В-обьем,С-прибыль)

6)По каким правилам при нахождении неотрицательных решений СЛАУ выбирается разрешающая неизвестная и разрешающее уравнение? Решение () системы называют неотрицательным, если все его компоненты α_j неотрицательны. Если правые части всех уравнений полученных систем окажутся неотрицательными, то соответствующие базисные решения также будут неотрицательными. Следовательно, чтобы получить неотрицательные базисные решения СЛАУ, надо научиться вести процесс исключения неизвестных так, чтобы свободные члены всех уравнений на всех этапах этого процесса оставались неотрицательными. Для этого следует руководствоваться следующими правилами: 1)Если в СЛАУ имеются отрицательные свободные члены, то все такие уравнения необходимо умножить на (-1); 2) В качестве разрешающей неизвестной можно принять любую неизвестную, при которой есть хоть один положительный коэффициент, а затем в качестве разрешающего уравнения следует взять то уравнение, которое соответствует наименьшему среди отношений свободных членов уравнений к соответствующим положительным коэффициентам при выбранной неизвестной в этих уравнениях. Может случиться, что указанное минимальное отношение достигается при нескольких значениях индекса. Тогда любое из соответствующих им уравнений можно принять за разрешающее. Принято говорить в этом случае, что рассматриваемая СЛАУ является вырожденной. СЛАУ не будет иметь ни одного неотрицательного решения, если в процессе симплексных преобразований в ней появится уравнение, в котором свободный член строго положителен, а среди коэффициентов при неизвестных нет ни одного положительного. Преобразования системы в соответствии с этими правилами называются симплекс-преобразованиями системы.

10) Дайте определения:

• Совместная и несовместная СЛАУ

• Определенная и неопределенная СЛАУ

Решением СЛАУ называется такая система чисел к₁,к₂,…к_n, которые при подстановке обращает каждое из уравнений системы в верное тождество. В этом случае, когда система имеет решение, она называется совместной, в противном случае противоречивой или несовместной. Совместная система называется определенной или неопределенной в зависимости от того, имеет ли она одно или несколько решений. Две СЛАУ с одинаковым числом неизвестных называются эквивалентными или равносильными, если они имеют одни и те же решения, либо вообще не имеет решений. При этом число уравнений в равносильных системах может быть различным. Те преобразования, которые переводят СЛАУ в эквивалентную ей систему называются элементарными.

11)Действия над матрицами: сумма, произведение, транспорирование. Свойства и формулы для расчета элементов.

Матрицей размера mxn наз таблица чисел, кот расположена в m-строках и n-столбцах

a₁₁ а₁₂ …а_1n

А= a₂₁ а₂₂ …а_2n или кратко А=(a_ij)

…………..

a_m1 а_m2 …а_mn

Если т= п, то матрица называется квадратной матрицей n-го порядка. Кв. матрица наз треугольной, если все ее элементы, стоящие над или под главной диагональю, равны нулю. Кв. матрица называется диагональной, если все ее эл-ты, стоящие на главной диагонали, отличны от нуля, а остальные равны нулю. Диагональная матрица наз единичной, если а_ii=1, i=1,...,п. Транспонированной матрицей наз матрица, строки кот.заменены столбцами. Единичную матрицу принято обозначать буквой Е:

Суммой двух матриц одного размера называется матрица того же размера, каждый элемент которой равен сумме соответствующих элементов матриц-слагаемых. Так, если А - || а_ij || и В=|| b_ij||— матрицы размера т х п, то их суммой является матрица С = А + В, такая, что c_ij=a_ij+b_ij. Произведением матрицы А размера т х п на число А, называется матрица D того же размера, у которой d_ij=a_ijλ..Для транспонированных матриц справедливы следующие соотношения: 1)(А')' = A;

2)(АВ)' = В'А' ; 3) (А + В)' = А' + В'.

Произведением матрицы А размера т х п на матрицу В размера n х k наз матрица С размера т х k, эл-ты кот с_ij равны скалярному произведению i-й строки матрицы А на j-й столбец матрицы В, т.е

Произведение матриц обозначается С = АВ. Скалярное произведение векторов а и b можно представить как произведение вектора-строки (матрицы-строки) а на вектор-столбец (матрицу-столбец) b': (a, b) = ab'.Для операции произведения матриц справедливы следующие свойства:

1)A(BС) = (АВ)С;

2)(А+В)С=АС+ВС; 3)A(B+С)=AB+AC; 4) λАВ) = (λА)В.

4) λАВ) = (λА)В.

Каждой квадратной матрице А n-го порядка можно поставить в соответствие некоторое число, называемое определителем, или детерминантом, n-го порядка и обозначаемое det A, /A/ или a₁₁ a₁₂

/A/ = a₂₁ a₂₂= a₁₁A₁₁ + a₁₂A₁₂=a₁₁a₂₂-a₁₂a₂₁

13)Обратная матрица: определение, свойства, условие существования.

Пусть задана квадратная матрица А. Если существует матрица В, такая что А*В=Е, то говорят что матрица В является обратной по отношению к матрице А: В=А^-1, А*А^-1=Е.

Свойства:

1)Обратная и исходная матрицы перестановочны и матрица, обратная обратной, совпадает с исходной: А*А^-1=А^-1*А=Е.

2)Единственность матрицы: если для данной матрицы обратная мат сущ-т,то она только одна.

Только квадратная матрица может иметь обратную.

Для нахождения обратной матрицы можно использовать следующий алгоритм:

• Смотрим, квадратная ли матрица: если нет, обратной матрицы не существует; если квадратная, переходим к след. пункту;

• Вычисляем определитель ∆А; если он равен 0, обратной матрицы не существует; если он не равен 0, переходим к след. пункту;

• Вместо каждого элемента матрицы ставим его алгебраическое дополнение (алгебраическим дополнением некоторого элемента определителя называется минор этого элемента, умноженный на (-1)^s, где s – сумма номеров строки и столбца, на пересечении которых расположен этот элемент);

• Полученную матрицу транспонируем;

• Каждый элемент полученной матрицы делим на определитель исходной матрицы и получаем матрицу, обратную данной.

14) Постановка линейной производственной задачи Предположим, что предприятие выпускает n видов продукции при использовании m видов ресурсов. Известны: технологическая матрица расходов i-го вида ресурса на единицу j-го вида продукции – А=(а_ij), где i=; j=. Матрица запаса ресурсов

Известны прибыль, полученная предприятием от производства и реализации продукции j-го вида. Требуется составить план производства продукции: x = (x₁, x₂, x₃,...x_n), при котором предприятие получит наибольшую прибыль. Суммарная прибыль предприятия c_j x_j. Требуется среди всех решений системы уравнений (1) найти такое неотрицательное решение, при котором линейная форма (3) принимает наименьшее возможное значение.

Любое неотрицательное значение системы называют допустимым, а допустимое решение, при котором целевая ф-я принимает наименьшее значение – оптимальным решением задачи ЛП.

Ограничения по ресурсам записываются в виде:

а₁₁x₁ + a₁₂x₂ + … a_1nx_n ≤ b₁

а₂₁x₁ + a₂₂x₂ + … a_2nx_n ≤ b₂

. . . . .

а_m1x₁ + a_m2x₂ + … a_mnx_n ≤ b_m.

где b_i-запас ресурса iго вида, x₁≥0, x₂≥0, ...x_n≥0.

Математическая модель задачи выглядит следующим образом: найти производственную программу (x₁, x₂, x₃, x₄), максимизирующую прибыль z = c_j x_j → max, если переменная x_j удовлетворяет следующим ограничениям: a_ijx_j ≤ b_i; x_j≥ 0; i=; j=.

Если в матем-й модели какой-либо задачи планирования будут содержаться линейные неравенства, то их можно заменить линейными уравнениями с помощью дополнительных неотрицательных неизвестных.

12)Единичная матрица: определение, формулы для элементов.

Матрица – это прямоугольная таблица чисел, содержащая m строк и n столбцов.

a₁₁ а₁₂ …а_1n

А= a₂₁ а₂₂ …а_2n или кратко А=(a_ij)

…………..

a_m1 а_m2 …а_mn

Если т=п, то матрица называется квадратной матрицей n-го по­рядка. Кв. матрица наз треугольной, если все ее элемен­ты, стоящие над или под главной диагональю, равны нулю. Кв. матрица называется диагональной, если все ее эл-ты, стоящие на главной диагонали, отличны от нуля, а остальные равны нулю. Диагональная матрица наз единичной, если у нее по главной диагонали стоят 1. Единичную матрицу принято обозначать буквой Е:

15)Постановка общей задачи математического программирования.

Задачу линейного программирования нередко формулируют как задачу минимизации или макси-мизации линейной формы L=c₁x₁+c₂x₂+...c_nx_n (1) при ограничениях x₁≥0, x₂≥0, ...x_n≥0 и

∑ a_ijx_j≤b_i, i=1,2,...m₁,

∑ a_ijx_j=b_i, i= m₁+1, m₁+2,...m₂,

∑ a_ijx_j≥b_i, i= m₂+1, m₂+2,...m.

Такую запись называют общей задачей линейного программирования.

Обозначим через А матрицу системы линейных уравнений:

а₁₁x₁ + a₁₂x₂ + … a_1nx_n = b₁

а₂₁x₁ + a₂₂x₂ + … a_2nx_n = b₂ (2)

А = . . . . .

а_m1x₁ + a_m2x₂ + … a_mnx_n = b_m.

Через X и B – матрицы-столбцы (векторы) неизвестных и свободных членов:

, ,

а также введем в рассмотрение n-мерный вектор C = (с₁ … с_n), компонентами которого служат коэффициенты линейной формы (1), и n-мерный нуль-вектор 0(0, 0, …, 0). Тогда линейную форму можно рассматривать как скалярное произведение L=CX (3), систему линейных уравнений (2) заменить одним матричным уравнением AX=B (4), а условия x₁≥0, x₂≥0, ...x_n≥0 записать в виде X≥0 (5). Поэтому часто основную задачу линейного программирования кратко записывают как задачу минимизации линейной формы (3) при линейных ограничениях (4) и (5).

17)Многошаговые процессы решений в экономике. Динамическое программирование.Параметр состояния и функция состояния. Принцип оптимальности и рекуррентные соотношения.

Динамическое программирование представляет собой математический аппарат, разработанный для решения некоторого класса задач математического программирования путем их разложения на относительно небольшие и, следовательно, менее сложные задачи. Специфика метода динамического программирования состоит в том, что для отыскания оптимального управления планируемая операция разделяется на ряд последовательных шагов или этапов. Соответственно и сам процесс планирования операции становится многошаговым и развивается последовательно, от этапа к этапу, причем каждый раз оптимизируется управление только на одном шаге.

Принцип искать всегда оптимальное продолжение процесса относительно того состояния, которое достигнуто в данный момент, принято называть принципом оптимальности.

Состояние на каждом шаге характ-ся некоторой переменной величиной, кот. называется параметром состояния. Наилучший эффект на данном этапе вместе с уже рассмотренными шагами хар-ся функцией состояния. Решение конкретной задачи методом динамич. программирования сводится к выбору параметра состояния, составлению ф-ии состояния и рекурентных соотношений, связывающих ф-ии состояния для двух соседних последовательных этапов, и их применению для выбора оптимального управления.

25) В каком случае задача оптимального производственного планирования не имеет оптимального плана?

«задача оптимального производственного планирования» - «линейного производства»

(«≤», max).

Отсутствие оптимального решения – неограниченность целевой функции.

Х₃ Х₅ Х₇

Х₁ 300 1 -1 0 0

Х₅ 250 0 -3 1 0

Х₇ 0 -4 0 1

10

250 = - 3Х₃+Х₅

Х₅=250 + 3Х₃

30)Для задачи линейного программирования … получить выражение целевой функции z через свободные переменные общего решения системы ограничений.

C₃ П₃ Н₀ Х₁ Х₂ Х₃ Х₄ Х₅ Х₆ Х₇

3 Х₂ 1

0 Х₆ 1

5 Х₃ 1

-z+1400 Двойственные оценки

Коэффициент выражения ц.ф-и через свободные переменные – это двойственные оценки (с точностью до знака)

Правило: столбец С₃ * столбец матрицы, а затем вычетается верхнее значение наверху.

Док-во: правила вычисления двойственных оценок. Без ограничений общности, базисными стали Х₁, Х₂, Х_3.

C₃ П₃ Н₀ Х₁ Х₂ Х₃ Х₄ Х₅ Х₆ Х₇

Х₁ 1 S

Х₂ 1

Х₃ 1

Двойственные оценки

F = CX= C₁X₁+ C₂X₂= C₁*X₁ + C₂*X₂= C₁(H-SX₂) + C₂( H₂) = C₁H + (-C₁S + C₂)X₂= Z₀+(-C₁S + C₂)X₂=Z₀-(C₁S- C₂)X₂=Z

Z= Z₀-(C₁S- C₂)X₂

40=X₁+ 7X₄+2X₁

H=X₁+SX₂→X₁=H-SX₂

19) Основные понятия в теории графов: дуги, вершины в ориентированном и неориентированном графе. Примеры применения теории графов на практике.

Графом называется пара объектов, состоящая из множества точек и множества отрезков, соединяющих некоторые (может быть, все) из этих точек. Упомянутые точ-ки называются вершинами графа.

Если отрезки, соединяющие вершины графа, имеют направления, то граф называ-ется ориентированным, а сами отрезки — дугами. Если же отрезки не имеют направ-ления, то граф называется неориентированным, и в этом случае говорят, что вершины графа соединены ребрами. Смешанным называется граф, в котором содержатся как ориентированные, так и неориентированные отрезки. Ориентированный граф часто называют сетью.

Обозначим вершины графа , а дугу, соединяющую вершину X_i c X_j - u_ij.

Две дуги графа (два ребра) называются смежными, если они различны и имеют общую вершину. Две вершины графа называются смежными, если существует дуга (ребро), соединяющая их.

Говорят, что дуга исходит из вершины X_i, если X_i является ее началом. Дуга заходит в вершину X_j если X_j является ее концом.

Говорят, что в графе данная дуга инцидентна данной вершине, если эта вершина является началом или концом данной дуги.

Путь в ориентированном графе — это последовательность дуг, в которой конец предыдущей дуги совпадает с началом следующей. Путь, в котором ни одна вершина не встречается дважды, называется элементарным. Путь, в котором ни одна дуга не встречается дважды, называется простым, в противном случае — составным. Конечный путь, у которого конечная вершина совпадает с начальной, называется контуром. Контур, образованный одной дугой, называется петлей.

Ориентированный граф называется симметрическим, если любые две смежные вершины его соединены двумя противоположно ориентированными дугами. Ориентированный граф называется антисимметрическим, если каждая пара смежных вершин соединена только в одном направлении и петли отсутствуют.

26) В каком случае при решении задачи линейного программирования симплекс-методом значения линейной функции двух последовательных планов могут совпасть?

П₀ Х₀ Х₃ Х₅ Х₇ β

Х₁ 1 -1 0 0

Х₅ * 0 -3 1 0

Х₇ 0 -4 0 1

1240 -10 -10/3

1240 – β • * ≠ 0

Значения линейной функции двух последовательных планов могут совпадать, если среди базисного плана есть 0 – вырожденный план

31.Правила выбора ключевого столбца и строки при решении задачи ЛП симплексным методом, последствия неправильного выбора.

1)Ключевой столбец выбираем по минимальной двойственной оценке

2)Потом считается столбец альфа3)По минимальной альфа выбираем ключевую строку

32.Введение балансовых переменных в систему ограничений задачи ЛП: цель и правило введения.

“балансовые”=”дополнительные”-чтобы приравнять неравенство в равенство.

Правило:

≤ +Х7

≥ -Х7

21) Сформулировать и доказать критерий оптимальности решения задачи линейного программирования при отыскании максимума линейной функции симплексным методом.

Все дв. оценки ≥ 0. Но дв. оценки – это взятые с противоположным знаком коэффициенты выражения ц.ф. через свободные неизвестные. Значит, сами эти коэффициенты ≤ 0. Поэтому, как только любая из свободных неизвестных примет положительное значение – целевая функция уменьшается. А это и означает, что она максимальна при нулевых значениях св.неизвестных, т.е. для данного базисного решения. + 22 вопрос, тока min меняем на max

29)Доказать, что если при решении задачи линейного программирования : … симплексным методом в качестве начального базиса выбирают базис из дополнительных переменных, для которых Сj=0, то оценки для всех не базисных (свободных) переменных будут равны ∆ = -Сj, а соответствующее значение целевой функции z₀=∑с_jx_j=0.

Это следует из правила выч.дв.оценок. Точнее, это следует из их определения: это коэф-ты ц.ф. выражаются через свободные неизвестные, которыми и являются в данном случае все основные переменные задачи

35.В каких задачах находится симплекс-метод?

В задачах линейного программирования.Для задач,связанных с принятием решений в экономике,характерна ситуация,когда требуется достичь некоторой цели при ограниченных ресурсах.Если функция цели линейно зависит от переменных (размеров видов деятельности или производственных процессов) и расходы ресурсов также линейно зависят от переменных,то такая задача принятия решений сводится к задаче линейного программирования(ЛП).

36.Что представляет собой симплексная таблица

Симплекс-таблица составляется из коэффициентов при x₁, x₂, x₃, x₄ и чисел, стоящих в правых частях уравнений-ограничений задачи: в первой строке записываются элементы уравнения (А), во второй - (В). В последней строке симплекс-таблицы записываются коэффициенты и правая часть целевой функции (С). Таким образом, симплекс-таблица содержит две строки коэффициентов (по числу ограничений задачи) и строку коэффициентов целевой функции. Число столбцов в симплекс-таблице равно числу переменных задачи плюс один столбец правых частей (b):