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

Научная электронная библиотека

Бельков В. Н., Ланшаков В. Л.,

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

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

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

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

.

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

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

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

где A — матрица размерности mxn, x — вектор-столбец размерности nxl, b— вектор-столбец размерности mxl, а c — вектор-строка размерности .1xn.

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

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

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

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

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

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

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

В стандартной форме задаются ( 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.

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

ФЕДЕРАЛЬНОЕ АГЕНСТВО ЖЕЛЕЗНОДОРОЖНОГО ТРАНСПОРТА РОССИЙСКОЙ ФЕДЕРАЦИИ

Государственное образовательное учреждение высшего профессионального образования

«ПЕТЕРБУРГСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ ПУТЕЙ СООБЩЕНИЯ»

Кафедра «Математика и моделирование»

Методические указания и варианты индивидуальных заданий для студентов заочного факультета

Линейное программирование. Решение задачи. Методические указания и варианты индивидуальных заданий для студентов заочного факультета, – СПб.: Петербургский государственный университет путей сообщения, 2006, 22 с.

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

Рецензент: профессор В.В. Гарбарук (кафедра «Высшая математика» ПГУПС)

© Петербургский государственный университет

Постановка задачи

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

Задача. Найти экстремум линейной функции F, если ее аргументы удовлетворяют некоторым ограничениям.

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

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

1. Записать задачу в матричной форме

2. Записать каноническую задачу.

3. Решить задачу геометрически.

4. Найти начальный базисный план с помощью искусственных переменных.

5. Решить задачу симплекс-методом.

6. Написать двойственную задачу к искомой в матричной и развернутой формах.

7. Найти решение двойственной задачи и доказать его оптимальность с помощью теоремы двойственности.

Варианты задач и пример решения указаны в конце этих указаний.

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

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

Определение 1. Следующая задача называется стандартной задачей линейного программирования.

Задача 1. Найти

, (1)

, , (2)

где A – матрица системы ограничений, имеющая m строк и n столбцов, b – столбец из m элементов; c, x – столбцы из n элементов. Таким образом, эти матрицы имеют вид

, , , . (3)

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

Задача 1’. Найти максимум линейной функции

,

.

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

Определение 3. Линейная функция F задачи 1 называется целевой функцией, а множество D решений системы (2) – множеством допустимых решений (планов) этой задачи.

Пример 1. Записать задачу линейного программирования (1), (2) с матрицами

; ; ;

в развернутой форме .

Решение. В развернутой форме задача формулируется следующим образом.

Найти максимум функции при ограничениях

.

Пример 2. Записать следующую задачу линейного программирования в матричной форме.

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

.

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

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

,

, ,

; ; ; .

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Принцип оптимальности в планировании и управлении, общая задача оптимального программирования

Линейное программирование

Слово “программирование” используется в значении “планирование”, не имеет отношения к компьютерному программированию.

Линейное программирование — это частный раздел опти­мального программирования. В свою очередь оптимальное (математическое) программирование — раздел прикладной математики, изучающий задачи условной оптимизации. В экономике такие задачи возникают при практической реализации принципа оптимальности в планировании и управлении.

Необходимым условием использования оптимального подхода к планированию и управлению (принципа опти­мальности) является гибкость, альтернативность производст­венно-хозяйственных ситуаций, в условиях которых прихо­дится принимать планово-управленческие решения. Именно такие ситуации, как правило, и составляют повседневную практику хозяйствующего субъекта (выбор производствен­ной программы, прикрепление к поставщикам, маршрутиза­ция, раскрой материалов, приготовление смесей и т.д.). Суть принципа оптимальности состоит в стремлении выбрать такое планово-управленческое решение = (х₁, х₂, . x_п), где x_j, (j =) — его компоненты, которое наилучшим образом учитывало бы внутренние возможности и внешние условия производственной деятельности хозяйствующего субъекта.

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

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

Таким образом, реализовать на практике принцип опти­мальности в планировании и управлении — это значит ре­шить экстремальную задачу вида:

где f() — математическая запись критерия оптималь­ности — целевая функция. Задачу условной оптимизации (2.1), (2.2) обычно записывают в виде:

Найти максимум или минимум функции

при ограничениях j₁=(х₁, х₂, . x_п)<>b₁,