Общая форма задачи линейного программирования

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

Назначение сервиса . Онлайн-калькулятор предназначен для перехода ЗЛП к КЗЛП. Приведение задачи к канонической форме означает, что все ограничения будут иметь вид равенств, путем ввода дополнительных переменных.
Если на какую-либо переменную x_j не наложено ограничение, то она заменяется на разность дополнительных переменных, x_j = x_j1 — x_j2, x_j1 ≥ 0, x_j2 ≥ 0.

• Решение онлайн
• Видеоинструкция

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

Математическая модель называется канонической, если ее система ограничений представлена в виде системы m линейно независимых уравнений (ранг системы r=m), в системе выделен единичный базис, определены свободные переменные и целевая функция выражена через свободные переменные. При этом правые части уравнений неотрицательны (b_i ≥ 0).

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

Решение системы называется базисным, если в нем свободные переменные равны 0, и оно имеет вид:
X_баз = (0, 0; b₁, …, b_m), f(X_баз) = c

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

Базисное решение называется опорным, если оно допустимо, т.е. все правые части уравнений системы (или неравенств) положительны b_i ≥ 0.

Компактная форма канонической модели имеет вид:
AX = b
X ≥ 0
Z = CX(max)

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

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

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

Одним из универсальных методов ЛП является симплексный метод, который, однако, можно применять, если задача ЛП имеет каноническую форму.

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

Утверждение. Любая общая задача ЛП может быть приведена к канонической форме.
Приведение общей задачи ЛП к канонической форме достигается путем введения новых (их называют дополнительными) переменных.
Система ограничений (3) этой задачи состоит из четырех неравенств. Введя дополнительные переменные y₁≥ 0, y₂≥ 0, y₃≥ 0, y₄ ≥ 0, можно перейти к системе ограничений:

Эти дополнительные переменные y _i имеют абсолютно ясный экономический смысл, а именно означают величину неиспользованного времени работы (простоя машины i-го вида).
Например, если бы машины первого вида работали все 18 ч, то x + y = 18, следовательно, y ₁ = 0. Но мы допускаем возможность неполного использования времени работы первой машины x + y
Неравенства были обращены в сторону «больше», поэтому вводя дополнительные переменные y ₁, y ₂, y ₃≥ 0, их необходимо вычесть из левой части, чтобы уравнять ее с правой. Получим систему ограничений в канонической форме:
Переменные y_i также будут иметь экономический смысл. Если вы вспомните практическое содержание задачи, то переменная y ₁ будет означать количество излишнего вещества А в смеси, y ₂ –количество излишков вещества В в смеси, y₃ – излишки С в смеси.
Задача нахождения максимального значения целевой функции может быть сведена к нахождению минимума для функции –F ввиду очевидности утверждения max F = –min (– F ). Посмотрите на рисунок: если в какой-то точке x= x функция y= F(x) достигает своего максимума, то функция y= –F(x), симметричная ей относительно оси OX, в этой же точке x достигнет минимума, причем F_max = – (–F_min) при x = x.

Вывод. Для представления задачи ЛП в канонической форме необходимо:

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

Пример №1 . Следующую задачу ЛП привести к каноническому виду: F(X) = 5x₁ + 3x₂ → max при ограничениях:
2x₁ + 3x₂≤20
3x₁ + x₂≤15
4x₁≤16
3x₂≤12
Модель записана в стандартной форме. Введем балансовые неотрицательные переменные x₃, x₄, x₅, x₆, которые прибавим к левым частям ограничений-неравенств. В целевую функцию все дополнительные переменные введем с коэффициентами, равными нулю:
В первом неравенстве смысла (≤) вводим базисную переменную x₃. Во 2-ом неравенстве смысла (≤) вводим базисную переменную x₄. В третьем неравенстве вводим базисную переменную x₅. В 4-м неравенстве — базисную переменную x₆. Получим каноническую форму модели:
2x₁ + 3x₂ + 1x₃ + 0x₄ + 0x₅ + 0x₆ = 20
3x₁ + 1x₂ + 0x₃ + 1x₄ + 0x₅ + 0x₆ = 15
4x₁ + 0x₂ + 0x₃ + 0x₄ + 1x₅ + 0x₆ = 16
0x₁ + 3x₂ + 0x₃ + 0x₄ + 0x₅ + 1x₆ = 12
F(X) = 5x₁ + 3x₂ + 0x₃ + 0x₄ + 0x₅ + 0x₆ → max

Для приведения ЗЛП к канонической форме необходимо:
1. Поменять знак у целевой функции
— F = -2x₁ + x₂ — 4x₃ +2x₄ → max

4. Соответствующая целевая функция примет вид:
— F = -2x₁ + x₂ — 4(x₈ – x₉) +2(x₁₀ – x₁₁) → max

Пример №2 . Преобразовать следующие задачи ЛП к канонической форме и решить их симплекс-методом.

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

СОДЕРЖАНИЕ

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 * ), состоящая из оптимального плана и оптимального значения целевой функции, а процесс решения заключается в отыскании множества всех решений ЗЛП.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Общий вид задачи линейного программирования.

Найти значения переменных x₁, x₂, x₃, . , x_n, при которых максимума или минимума max (min) достигает целевая функция.

Если для переменных x1, x2, . , xn выполняются ограничения

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

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

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

Нужно определить оптимальные объемы производства изделия каждого вида.

Решение

Пусть изделий 1 го вида изготавливается x₁ штук, а 2 го вида – x₂ штук.

Ограничения:

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

Чтобы решить графически нужно выполнить следующее:

1) построить многоугольник допустимых решений

2) если при некоторых значениях x₁, x₂ целевая функция z = a, то прямая c₁x₁ + c₂x₂ = a будет перпендикулярна нормаль вектору

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

Продолжаем рассматривать начатый выше пример.

(1)

пробная точка O (0, 0): выполняется.

O (0, 0) лежит в полуплоскости

(2)

O (0, 0): выполняется.

(3)

O (0, 0): выполняется.

Двигаем до точки А.

А – опорное решение

Найдем координаты точки А.

Прибыль:

Симплекс-метод

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

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

1) Если в ограничении есть знак ≤, то мы прибавляем к левой части остаточную переменную

Решение, полученное занулением n – m переменных называется базисным. Переменные не равные нулю называются базисными переменными, а равные нулю – небазисными.