Линейное программирование

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

2. Каноническая форма

2.1. Канонической формой задачи линейного программирования называется задача вида F=C1X1+C2X2+…C,X,+…CnXn->ex+n(1) A11,X1+A1X2+…+A1nXn<B1 A21X1+A22X2+…+A2nXn<Bn (2) Am1X1+Am2X2+…AmXn<Bm X1X2…Xn>0 (3)

3. Правила приведения

3.1. Рассмотрим теперь те приёмы, которые позволяют произвольные формы задач линейного программирования приводить к указанным выше стандартным формам. 1. Превращение max в min и наоборот. Если целевая функция в задаче линейного программирования задана в виде c1x1+c2x2+...+CnXn=min то, умножая её на (- 1), приведем её к виду (-c1)x1+(-c2)x2+...+(-Cn)Xn=max так как смена знака приводит к смене min на max. Аналогично можно заменить max на min.

3.2. 2. Смена знака неравенства. Если ограничение задано в виде Ai1X1+Ai2X2+...+AinXn<Bi то, умножая на (-1), получим: (-Ai1)X1+(-Ai2)X2+...+(-Ain)Xn>-Bi Аналогично, неравенство вида больше либо равно можно превратить в неравенство вида меньше либо равно .

3.3. 3. Превращение равенства в систему неравенств. Если ограничение задано в виде Ai1X1+Ai2X2+...+AinXn=Bi то его можно заменить эквивалентной системой двух неравенств Ai1X1+Ai2X2+...+AinXn<Bi (-Ai1)X1+(-Ai2)X2+...+(-Ain)Xn <-B2 или такой же системой неравенств со знаками больше либо равно. Указанные выше приемы позволяют приводить задачи линейного программирования к стандартной форме.

3.4. 4. Превращение неравенств в равенства. Для приведения задачи к канонической форме, где все ограничения имеют вид равенств, вводят дополнительные переменные Xn+1.Xn+2...Xn+p , которые тоже считаются неотрицательными и записывают исходную задачу в виде C1X1+C2X2+...+CnXn+0*Xn+1+0*Xn+2...+0*Xn+y=min

4. Стандартная форма

4.1. Первая стандартная форма задачи линейного программирования имеет вид

4.2. Вторая стандартная форма задачи линейного программирования имеет вид