Особенности определения начального базисного решения

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

Практическое занятие: Задача линейного программирования

Сформулируем задачу линейного программирования

Завод выпускает 2 вида продукции. П1 и П2. На их производство затрачивается 4 вида сырья С1-С4. Запасы сырья равны S1=19, S2=13, S3=15, S4=18. На выпуск единицы продукции П1 затрачивается две единицы сырья с С1, две единицы С2, и три единицы сырья С4. Вычислить выпуск продукции П1 и П2 чтобы максимизировать доход и выполнить ограничение по запасам сырья.

Стоимость единицы продукции П1=7 единицы, стоимость единицы продукции П2=5 единиц.

Обозначим х1 и х2 количество продукции вида П1 и П2. Сведем исходную информацию в таблицу

Виды сырья	Запасы	Количество единиц П1 и П2
С1		2 3
С2		2 1
С3		- 3
С4		3 -

Представим данные из таблицы в виде системы ограничений

2х1+3х2<=19

2х1+1х2<=13 (1)

3x2<=15

3x1<=18

X1=>0, x2=>0 (2)

Критерием в данной задачи является доход который зависит

R(x1,x2…)=7x1+5x2->max (3)

Решение задачи (1-3) линейного программирования является такая совокупность чисел х1*, х2*, которые удовлетворяют всем условиям (2) и максимизируются в доход (3).

2)решим задачу (1-3) геометрически и прокомментируем полученный результат.

Вначале построим область допустимых решений к задачи отвечающую неравенствам (1-3).

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

R(x1,x2)=7x1+5x2->max

2х1+3х2=19

2х1+1х2=13

3x2=15

3x1=18

X1=0

График

Согласно линейного программирования оптимальное решение надо искать в вершинах многогранника Х.

Найдем оптимальную точку построим линии равного уровня например для числа 60.

Для того чтобы найти координаты точки А4, необходимо решить систему уравнений

2х1+3х2=19

2х1+х2=13

Х1=5

Х2=3

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

R(x*)=R(x1,x2)=7*5+5*3=50->max

Подставим полученные значения х1* и х2* в неравенство один

2*5+3*3=19

2*5+1*3=13

3*3=9<15

 

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

Комментарий к решению задач симплексного метода

При решение симплексным методом перебираются вершины многогранника условий так что следующая вершина не хуже предыдущей.

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

A11x1+a12x2+…a1mxn=b1

A21x1+a22x2+…a2mxn=b2

…

An1x1+an2x2+…anmxn=bn

Будем считать что в такой системе все уравнения линейно независимы.

Любые m-переменных в системе 1 называются основными (базисными). Если определить в матрице коэффициентов при них не равен нулю. Оставшиеся m-n переменных называются свободными или не основные.

Число возможных групп переменных меньше или равно числа сочетаний из n по m.

Найти все основные группы переменных в следующей системе уравнений.

X1-x2-2x3+x4=0

2x1+x2+2x3-x4=2

N=4

M=2

Проверим какие сочетания могут быть основными переменными.

Комбинации могут быть базисными переменными, а следующая комбинация не могут быть.

Решим систему уравнений:

Основными переменными могут быть 3 комбинации.

Возьмем в качестве основных х1 и х2

Когда х3 и х4 не основные, свободные переменные.

Оставим в левой части систему х1 и х2 а не основные перенесем в правую часть.

сложив оба уравнения получим 3х1=2, х1=2/3

таким образом исходная система уравнений имеет бесчисленное множество решений. Каждое из них соответствует определенной комбинации свободных переменных х3,х4.

Решение называется допустимым решением задачи или системы 1 если все компоненты больше или равно 0, в противном случае недопустимы. Среди бесконечного числа решения выделяют базисные решения. То есть такие решения в котором все n-m-свободных или не базисных решений равны 0. Особенно нас интересуют допустимые базисные решения, в которых не более.

Пример:

Найти все базисные решения в системе

X1-x2-2x3+x4=0

2x1+x2+2x3-x4=2

Возьмем первую комбинацию х1 и х2 при этом они являются основными переменными, а х3 и х4 являются свободными не базисными. Пусть х3 =0 и х4=0. Х1-x2=0

Таким образом первое решение, это базисное решение. Это допустимое базисное решение.

 

Дискректное программирование

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

В качестве допустимых решений в задаче ДП могут быть:

1)перестановки элементов (задача Комми Во Яжора и теории расписания)

2)пути в сетях

3)подмножество заданного конечного множества (задача о ранце)

4)целочисленные точки заданного выпуклого многогранника (задача целочисленного программирования)

Целочисленные задачи наиболее распространена. В виде задачи ДПР формулируются задачи управления, размещения, планирования и другие.