Добавил:
Upload Опубликованный материал нарушает ваши авторские права? Сообщите нам.
Вуз: Предмет: Файл:
Теория1.doc
Скачиваний:
4
Добавлен:
01.04.2025
Размер:
5 Мб
Скачать
☆

II. Задача с n переменными.

Графическим методом можно решать ЗЛП с n>2 переменными, если в её канонической записи число неизвестных “n” и число линейно независимых уравнений “m” связаны соотношением n-m≤2. В этом случае каноническую форму задачи преобразовывают в симметричную, которая будет содержать не более двух переменных. Решая эту задачу графически, находят два компонента оптимального плана. Подставляя их в ограничения задачи, определяют и остальные компоненты.

Пример:

Найти при ограничениях

Решение:

Т.к. , , , то

Тогда

Мы свели задачу к задаче с двумя переменными, которую мы уже умеем решать.

Свойства решений задачи линейного программирования

  1. Множество всех допустимых решений системы ограничений задачи линейного программирования является выпуклым (если оно не пусто).

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

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

Итак, если линейная функция задачи линейного программирования ограничена на многограннике решений, то: 1) существует такая угловая точка многогранника решений, в которой линейная функция задачи линейного программирования достигает своего оптимума; 2) каждый опорный план соответствует угловой точке многогранника. Поэтому для решения задачи линейного программирования необходимо исследовать только угловые точки многогранника решений, т.е. только опорные планы.

Симплекс – метод (метод перебора крайних точек)

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

Симплекс-метод в его непосредственной форме предназначен для решения канонической задачи линейного программирования.

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

Общее число групп основных переменных не превосходит число сочетаний

Критерий оптимальности. Целевая функция на min(max) оптимальна, если в выражении целевой функции через свободные переменные отсутствуют отрицательные (положительные) коэффициенты при свободных переменных.

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

Определение. Допустимое базисное решение – это базисное решение, в котором все переменные больше либо равны нулю. Допустимые базисные решения называют опорными планами.

Определение. Система уравнений называется совместной, если она имеет хотя бы одно решение и несовместной, если она не имеет решений.

Определение. Совместная система уравнений называется определенной, если она имеет единственное решение, и неопределенной, если она имеет более одного решения.

Теорема Кронекера – Капелли. Система линейных уравнений совместна тогда и только тогда, когда ранг матрицы системы равен рангу расширенной матрицы этой системы.

Теорема 1. Если ранг матрицы совместной системы равен числу переменных, т. е. , то система имеет единственное решение.

Теорема 2. Если , то система неопределенная и имеет бесконечное множество решений.