ПО ВЫПОЛНЕНИЮ КОНТРОЛЬНОЙ РАБОТЫ №2

Основные понятия и определения линейного программирования

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

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

Математическая модель задачи линейного программирования (ЗЛП) содержит:

1) совокупность переменных, которые должны быть неотрицательны ПО ВЫПОЛНЕНИЮ КОНТРОЛЬНОЙ РАБОТЫ №2 - student2.ru

ПО ВЫПОЛНЕНИЮ КОНТРОЛЬНОЙ РАБОТЫ №2 - student2.ru .

2) целевую функцию ПО ВЫПОЛНЕНИЮ КОНТРОЛЬНОЙ РАБОТЫ №2 - student2.ru .

3) условия (систему ограничений), налагаемые на переменные записанные в виде уравнений или неравенств.

ПО ВЫПОЛНЕНИЮ КОНТРОЛЬНОЙ РАБОТЫ №2 - student2.ru (1)

Оптимальным решением (или оптимальным планом) называется такое решение системы ограничений, при котором целевая функция принимает оптимальное (max или min) значение.

Систему ограничений (1) заданную в виде неравенств можно привести к системе уравнений, для чего нужно к левой части неравенства прибавить или отнять добавочную переменную. Таким образом, ЗЛП приводится к канонической форме, когда система ограничений задана в виде системы m линейных уравнений с n переменными.

При этом возможны три случая:

1. Система ограничений несовместна. Следовательно, ЗЛП не имеет решения.

2. Система ограничений совместная и определенная ПО ВЫПОЛНЕНИЮ КОНТРОЛЬНОЙ РАБОТЫ №2 - student2.ru . В этом случае система имеет единственное решение ПО ВЫПОЛНЕНИЮ КОНТРОЛЬНОЙ РАБОТЫ №2 - student2.ru .

3. Система ограничений совместная и неопределенная ПО ВЫПОЛНЕНИЮ КОНТРОЛЬНОЙ РАБОТЫ №2 - student2.ru . У такой системы существует бесчисленное множество решений.

Любые ПО ВЫПОЛНЕНИЮ КОНТРОЛЬНОЙ РАБОТЫ №2 - student2.ru переменных системы линейных уравнений с ПО ВЫПОЛНЕНИЮ КОНТРОЛЬНОЙ РАБОТЫ №2 - student2.ru переменными ПО ВЫПОЛНЕНИЮ КОНТРОЛЬНОЙ РАБОТЫ №2 - student2.ru называются основными (или базисными), если определитель из коэффициентов при них отличен от нуля. Этот определитель будем называть базисным минором матрицы А, из коэффициентов при переменных.

Тогда остальные ПО ВЫПОЛНЕНИЮ КОНТРОЛЬНОЙ РАБОТЫ №2 - student2.ru переменных называются неосновными или свободными.

Основными могут быть различные группы ПО ВЫПОЛНЕНИЮ КОНТРОЛЬНОЙ РАБОТЫ №2 - student2.ru переменных из ПО ВЫПОЛНЕНИЮ КОНТРОЛЬНОЙ РАБОТЫ №2 - student2.ru , но их количество не превышает числа сочетаний из ПО ВЫПОЛНЕНИЮ КОНТРОЛЬНОЙ РАБОТЫ №2 - student2.ru по ПО ВЫПОЛНЕНИЮ КОНТРОЛЬНОЙ РАБОТЫ №2 - student2.ru :

ПО ВЫПОЛНЕНИЮ КОНТРОЛЬНОЙ РАБОТЫ №2 - student2.ru

Из бесчисленного множества решений выделяют базисные решения.

Базисным решением системы ПО ВЫПОЛНЕНИЮ КОНТРОЛЬНОЙ РАБОТЫ №2 - student2.ru линейных уравнений с ПО ВЫПОЛНЕНИЮ КОНТРОЛЬНОЙ РАБОТЫ №2 - student2.ru переменными ПО ВЫПОЛНЕНИЮ КОНТРОЛЬНОЙ РАБОТЫ №2 - student2.ru называется решение, в котором неосновные переменные равны нулю.

Каждой группе основных переменных соответствует одно базисное решение. Базисные решения могут быть допустимыми или недопустимыми.

Базисное решение называется допустимым, если значения ПО ВЫПОЛНЕНИЮ КОНТРОЛЬНОЙ РАБОТЫ №2 - student2.ru основных переменных неотрицательны, а ПО ВЫПОЛНЕНИЮ КОНТРОЛЬНОЙ РАБОТЫ №2 - student2.ru неосновные переменные равны нулю.

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

Если в базисном решении хотя бы одна из основных переменных принимает нулевое значение, то оно называется вырожденным.

Наши рекомендации