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

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

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

Стандартная форма

В стандартной форме задаются ( n ) действительных чисел (с_1, c_2, ldots, c_n ); ( m ) действительных чисел ( b_1,b_2,ldots ,b_m ); и ( mn ) действительных чисел ( a_ ), где ( i=1,2, ldots, m ) и ( j = 1,2, ldots, n ).
Требуется найти ( n ) действительных чисел ( x_1,x_2,ldots,x_n ) которые:

Максимизируют целевую функцию ( sumlimits_^n c_j x_j ) при заданных ограничениях : ( sumlimits_^n a_ x_j le b_i) при ( i=1,2, ldots, m ) и ограничениях неотрицательности ( x_j ge 0 ) при ( j= 1,2,ldots,n )

Преобразование в стандартную форму

Задача находится не в стандартной форме если:

1. Целевая функция минимизируется, а не максимизируется
2. На имеющиеся переменные не наложены условия неотрицательности
3. Некоторые ограничения имеют форму равенства, т.е. имеют знак равенства вместо меньше или равно
4. Некоторые ограничения вместо знака “меньше или равно” имеют знак “больше или равно”.

Как получить стандартную форму в таких случаях? Рассмотрим по пунктам:

1. Достаточно поменять знаки целевой функции, например: ( -5x_1+2x_2 to min ) эквивалентно ( 5x_1-2x_2 to max ).
2. Если отсутствует ограничение неотрицательности для переменной (x_j), то заменяем эту переменную выражением ( x_j^<‘>-x_j^ <“>) из двух неотрицательных переменных (x_j^<‘>,x_j^ <“>ge 0 ).
3. Если ограничение имеет вид равенства, то заменяем его парой из двух неравеств “меньше или равно” и “больше или равно”.
4. Для смены смены выда неравенства с “больше или равно” на “меньше или равно” умножаем обе части неравества на -1 и меняем знак сравнения.

[-5x_1+3x_2 to min ]

Шаг 1. Меняем знак целевой функции

[5x_1-3x_2 to max ]

Шаг 2. Для второй переменной (x_2) ограничений неотрицательности нет. Заменим на выражение (x_2=x_2^<‘>-x_2^ <”>):

Шаг 3. Заменяем равенство на два неравенства:

Шаг 4. Изменяем знак неравества:

Получили задачу в стандартном виде.

Примечание:

В данной заметке рассмотрен основной подход к виду стандартной формы задачи ЛП. Существует и другой подход, например в книге Соколов А. В., Токарев В.В. Методы оптимальных решений. В 2-х т. Т 1. Общие положения. математическое программирование. – 3-е изд. – 564 с. на с. 423 выделяется стандартный вид задачи на максимум:

Однако в общепринят первый вариант из которого второй получается простым умножением обеих частей неравенств на -1.

Формы задачи линейного программирования

СОДЕРЖАНИЕ

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

1.1 Формы задачи линейного программирования

1.2 Переход к канонической форме

2.1 Теоретические основы симплекс-метода

2.2 Прямой алгоритм симплексного метода

4. Математическая и техническая постановка задачи. Программная реализация. Описание проекта

4.2 Описание графического интерфейса

4.3 Описание созданных функций

ВВЕДЕНИЕ

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

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

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

1. ПОСТАНОВКА ЗАДАЧИ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ [2]

Формы задачи линейного программирования

В общем виде задача линейного программирования (в дальнейшем ЗЛП) может быть сформулирована как задача нахождения наибольшего значения линейной функции

(1.1)

на некотором множестве D Ì R n ,где x Î D удовлетворяют системе ограничений

(1.2)

и, возможно, ограничениям

(1.3)

He умаляя общности, можно считать, что в системе (1.2) первые т ограничений являются неравенствами, а последующие — l-уравнениями. Очевидно, этого всегда можно добиться за счет простого переупорядочения ограничений. Относительно направления знака неравенства будем предполагать, что левая часть меньше или равна правой. Добиться этого можно, умножив на (-1) обе части тех неравенств, которые имеют противоположный знак. Ограничения (1.3), вообще говоря, могут быть рассмотрены как частный случай ограничений в форме неравенств, но в силу особой структуры их обычно выделяют отдельно и называют условиями неотрицательности (или тривиальными ограничениями).

Дополнительно следует заметить, что выбор типа искомого экстремума (максимума или минимума) также носит относительный характер. Так, задача поиска максимума функции

(1.4)

эквивалентна задаче поиска минимума функции

(1.5)

Часто условия задачи (1.1) — (1.3), содержащей ограничения только типа неравенств, бывает удобно записывать в сокращенной матричной форме

(1.6)

где с и x — векторы из пространства R n , b — вектор из пространства R m , a А — матрица размерности m ´ п.

Задачу линейного программирования, записанную в форме (1.1) — (1.3), называют общей задачей линейного программирования (ОЗЛП).

Если все ограничения в задаче линейного программирования являются уравнениями и на все переменные x_j наложены условия неотрицательности, то она называется задачей линейного программирования в канонической форме, или канонической задачей линейного программирования (КЗЛП). В матричной форме КЗЛП можно записать в следующем виде:

(1.7)

Поскольку любая оптимизационная задача однозначно определяется целевой функцией f и областью D, на которой отыскивается оптимум (максимум), будем обозначать эту задачу парой (D, f).

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

Планом ЗЛП называется всякий вектор х из пространства R n .

Допустимым планом называется такой план ЗЛП, который удовлетворяет ограничениям (1.2)-(1.3), т. е. содержится в области D. Сама область D называется при этом областью допустимых планов. Оптимальным планом х * называется такой допустимый план, при котором целевая функция достигает оптимального (в нашем случае — максимального) значения, т. е. план, удовлетворяющий условию

Величина f * = f(x * ) называется оптимальным значением целевой функции.

Решением задачи называется пара (х * , f * ), состоящая из оптимального плана и оптимального значения целевой функции, а процесс решения заключается в отыскании множества всех решений ЗЛП.

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

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

Приведение задач к стандартной форме производится по следующим правилам:

2. Ограничение в виде неравенств, например 4×x₁ + 5×x₂ 800, может быть при­ведено к стандартной форме 4×x₁ + 5×x₂ + x₃ = 800, где x₃ — новая неотрицательная переменная.

Ограничение может быть приведено к стандартной форме , где новая переменная x₅ неотрицательна.

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

, где и .

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

Приведем к стандартной форме задачу, рассмотренную в примере 1.

Эта задача может быть представлена в следующем виде:

минимизировать функцию Z = — 20x₁ — 40x₂

, i = 1, … ,4.

В матричной форме ограничения можно записать следующим образом:

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

Конечно, имея два уравнения с четырьмя неизвестными, можно получить

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

Переменные, приравненные нулю, называются небазисными переменными.

Остальные называются базисными и образуют базис.

Лекция 3: Математическое программирование. Линейное программирование. Виды задач линейного программирования. Постановка задач линейного программирования и исследование их структуры. Решение задач линейного программирования симплекс-методом

1. Понятие математического программирования

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

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

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

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

В зависимости от свойств целевой функции и функции ограничений все задачи математического программирования делятся на два основных класса:

• задачи линейного программирования,
• задачи нелинейного программирования .

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

2. Понятие линейного программирования. Виды задач линейного программирования

Линейное программирование (ЛП) – один из первых и наиболее подробно изученных разделов математического программирования . Именно линейное программирование явилось тем разделом, с которого и начала развиваться сама дисциплина » математическое программирование «. Термин «программирование» в названии дисциплины ничего общего с термином «программирование (т.е. составление программы) для ЭВМ» не имеет, т.к. дисциплина » линейное программирование » возникла еще до того времени, когда ЭВМ стали широко применяться для решения математических, инженерных, экономических и др. задач.

Термин » линейное программирование » возник в результате неточного перевода английского » linear programming «. Одно из значений слова «programming» — составление планов, планирование. Следовательно, правильным переводом английского » linear programming » было бы не » линейное программирование «, а «линейное планирование», что более точно отражает содержание дисциплины. Однако, термины линейное программирование , нелинейное программирование, математическое программирование и т.д. в нашей литературе стали общепринятыми и поэтому будут сохранены.

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

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

Линейное программирование применяется при решении экономических задач, в таких задачах как управление и планирование производства; в задачах определения оптимального размещения оборудования на морских судах, в цехах; в задачах определения оптимального плана перевозок груза (транспортная задача); в задачах оптимального распределения кадров и т.д.

Задача линейного программирования (ЛП), как уже ясно из сказанного выше, состоит в нахождении минимума (или максимума) линейной функции при линейных ограничениях.

Общая форма задачи имеет вид: найти при условиях

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

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

Дата добавления: 2015-08-06 ; просмотров: 1015 ; Нарушение авторских прав

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

Задача ЛП в стандартной форме с ограничениями и переменными имеет следующий вид:

максимизировать или минимизировать

Задачи ЛП в стандартной форме можно записать в компактных матричных обозначениях следующим образом:

максимизировать или минимизировать

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

где — матрица размерности , — вектор-столбец размерности , — вектор-столбец размерности , а c — вектор-строка размерности .

Обычно назначается матрицей коэффициентов, — вектором переменных, — вектором ресурсов, — вектором оценок задачи ЛП.

При решении задачи ЛП симплекс–методом требуется, чтобы задача была представлена в стандартной форме. Однако не все практические задачи ее имеют, поэтому для удовлетворения требования алгоритма необходимо следующее.

1. При помощи введения дополнительных остаточных или избыточных переменных преобразовать неравенства в равенства.

2. Для получения неотрицательных переменных задачи неограниченные по знаку переменные заменить разностью двух неотрицательных.

При решении задач ЛП используются следующие основные понятия. Допустимым решением являются неотрицательные значения переменных, для которых выполняются ограничения, а допустимой областью – совокупность допустимых решений. Оптимальным решением называются такие допустимые значения переменных, при которых ЦФ экстремальна, т.е. имеет оптимальное значение. В ряде случаев ЦФ имеет одно оптимальное значение при нескольких комбинациях значений переменных, следовательно, задача обладает неединственностью оптимума. Когда в задаче ЛП нет конечного оптимума, то в этом случае существует неограниченный оптимум.