Особенности определения начального базисного решения
используется метод искусственного базиса, с рассмотрением различных случаев.
Практическое занятие: Задача линейного программирования
Сформулируем задачу линейного программирования
Завод выпускает 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)целочисленные точки заданного выпуклого многогранника (задача целочисленного программирования)
Целочисленные задачи наиболее распространена. В виде задачи ДПР формулируются задачи управления, размещения, планирования и другие.