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

о нахождении наивыгоднейших вариантов при решении различных планово-производственных задач.

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

достичь какого-то результата можно достичь различными способами. При большом

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


При следующих условиях

где целевая функция;
Условия (1),(2) специальные ограничения задачи
математического программирования.
Определение 1. Множество всех допустимых решений задачи математического программирования называется допустимым множеством.
Определение 2. Если задача математического программирования имеет хотя бы одно решение, то она называется допустимой.
Определение 3. Если задача математического программирования не имеет ни одного допустимого решения, то она называется недопустимой.

или глобальный минимум целевой функции. Глобальный максимум или глобальный

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

для задачи максимизации целевой функции;



для задачи минимизации целевой функции.

Если в задаче математического программирования целевая функция и функции

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

следующей задачи. Дана система m линейно независимых уравнений с

n неизвестными называемая системой ограничений задачи линейного программирования:



где В данной задаче число уравнений меньше числа неизвестных, то есть m

которые удовлетворяют уравнениям (1.1) и обращают в минимум целевую функцию

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

где A - матрица размером - мерный вектор; x и n - мерные векторы.

равно числу неизвестных рассматривается в обычной алгебре.
Если

определитель системы не равен нулю, то система имеет единственное решение, которое можно найти либо методом Крамера либо методом Гаусса.
Если же число уравнений меньше числа неизвестных (m удовлетворяющий системе уравнений (1.1), будем называть решением.

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

из уравнений вида (1.1) представлены в виде неравенств. Например,

вместо уравнения

в систему (1.1) может входить неравенство вида
или
Однако такие неравенства легко превратить в уравнения, вводя добавочную переменную
так, чтобы в зависимости от знака неравенства имело место одно из двух выражений



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

а максимизации ее. Эта задача сводится к предыдущей

путем перемены знака у выражения для q.
Обозначим значение целевой функции через q, если требуется ее минимизировать, и через q*, если она должна быть максимизирована.
В общем случае число переменных n в этой системе больше числа уравнений m, то одно из возможных решений можно найти, если n-m каких-либо переменных положить равными нулю. Полученную при этом систему m уравнений с m неизвестными можно решать обычными методами алгебры. Правда, для того чтобы система m уравнений с m неизвестными имела решение, необходимо, чтобы определитель, составленный из коэффициентов при неизвестных, не обращался в нуль. Если это условие не выполняется, то можно приравнять нулю другие n-m переменных. Полученное при этом решение называется базисным решением.

таких, что определитель, составленный из коэффициентов при этих переменных,

не равен нулю.
Определение 2. Эти m переменные называются базисными переменными (по отношению к данному базису).
Определение 3. Остальные n-m переменных называются небазисными или свободными переменными.
Если положить все свободные переменные равными нулю и решить полученную систему m уравнений с m неизвестными, то получим базисное решение.
Однако среди различных базисных решений будут такие, которые дают отрицательные значения некоторых переменных.
Эти базисные решения противоречат условию задачи и являются недопустимыми.

базисное решение, которое одновременно допустимо, то есть которое дает

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

базовое решение. Его можно найти, приняв какие-либо n-m переменных

за свободные, приравняв их нулю и решив получившуюся систему уравнений.
Если при этом некоторые из базисных переменных окажутся отрицательными, то нужно выбрать другие переменные, то есть перейти к новому базису.
После того как найдено допустимое базисное решение, проверяется, не достигнут ли уже максимум целевой функции q*. Если нет, то ищут новое допустимое базисное решение, но не любое, а такое, которое увеличивает значение целевой функции q*.
Затем процедура повторяется.
Данный метод довольно быстро приводит к цели, так как позволяет исключить из рассмотрения большое число базисных решений, заведомо не обращающих в максимум целевую функцию.

1. Найти максимум линейной формы


при ограничениях:





Для решения

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

неравенства имеют знак
« ». В

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

,

а свободные переменные - .
Шаг 2. Из системы уравнений (*) выразим базисные переменные через свободные:




Шаг 3. Положив свободные переменные равными нулю, получим базисное решение:

функции равно


Шаг 5. Проверим, доставляет ли выбранное базисное

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

( не худшему) решению: в новый состав базисных переменных

вводится та из свободных переменных, которая имеет наибольший положительный коэффициент в целевой функции.
В данном случае это коэффициент при .
Чтобы оценить, в каких пределах возможно изменение переменной , необходимо определить при каких значениях каждая из «старых» базисных переменных останется неотрицательной (соблюдение этого условия и делает новое искомое решение допустимым).
Очевидно, что для этого необходимо выполнения следующих неравенств:

если будут выполнены все ограничения данной системы. В свою

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

• Базисные переменные
• Свободны переменные

.
Шаг 2. Выразим основные переменные через не основные, воспользовавшись соотношением из разрешающего уравнения:




Шаг 3. Положив свободные переменные равными нулю, получим новое базисное решение:

и определим ее значение при данном базисном решении:


Шаг 5.

Проверим, доставляет ли выбранное базисное решение оптимум целевой функции. Коэффициент при в выражении целевой функции положителен, следовательно данное базисное решение не доставляет оптимума целевой функции и необходимо искать новое базисное решение, которое улучшило бы (или, по крайней мере, не ухудшило бы) значение функционала.
Шаг 6. Используя сформулированное выше правило перехода к лучшему решению, введем в новый состав базовых переменных .

уравнение.





Из разрешающего уравнения следует, что если

, то , следовательно можно опять вернуться к первому шагу.
Шаг 1.Определим новый состав основных и свободных переменных:
базисные переменные: ,
свободные переменные: .

Положив свободные переменные равными нулю, получим новое базисное решение:


Шаг

4. Выразим целевую функцию через свободные переменные и определим ее значение при данном базисном решение:

выполняется, так как коэффициент при положителен.
Шаг 6.

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

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

новое базисное решение:


Шаг 4. Выразим целевую функцию через свободные

переменные и определим ее значение при данном базисном решении:

что на этот раз он выполняется и что исследуемое

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

средства банка в сумме с депозитами составляют 100 млн.

долларов США. Эти средства банк может разместить в кредиты по ставке и в государственные ценные бумаги по ставке . Так как кредиты менее ликвидны по сравнению с ценными бумагами, то .
Банк обязан не менее 35% от суммы 100 млн. долларов разместить в кредитах. Ликвидное ограничение заключается в следующем: ценные бумаги должны составлять не менее 30% средств, размещенных в кредитах и ценных бумагах.

(млн. долларов), размещенные в кредитах,

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