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

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

Линейное программирование: методы

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

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

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

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

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

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

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

Линейное программирование: задачи

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

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

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

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

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

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

Линейное программирование – математическая дисциплина, посвящённая теории и методам решения задач об экстремумах линейных функций на множествах n -мерного векторного пространства, задаваемых системами линейных уравнений и неравенств.

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

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

Линейное программирование применяется при решении следующих экономических задач:

1. Задача управления и планирования производства.

2. Задач определения оптимального размещения оборудования на морских судах, в цехах.

3. Задача определения оптимального плана перевозок груза (транспортная задача).

4. Задача оптимального распределения кадров.

5. Задач о смесях, диете (планирование состава продукции) и т.д.

3. МОДЕЛЬ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ, ЕЁ ПРЕДСТАВЛЕНИЕ В ЭЛЕКТРОННЫХ ТАБЛИЦАХ MS EXCEL.

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

Основные этапы создания модели линейного программирования в Excel:

1. Написание и проверка символической модели линейного программирования. Модель записывается на бумаге в математическом виде.

2. Создание и отладка табличной модели линейного программирования. На основе символической модели ЛП создается ее представление в Excel.

3. Попытка оптимизации модели с помощью надстройки ПОИСК РЕШЕНИЯ.

4. ИСПОЛЬЗОВАНИЕ НАДСТРОЙКИ ПОИСК РЕШЕНИЯ .

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

Поиск решения – это надстройка, которая предназначена для оптимизации моделей при наличии ограничений. Она состоит из двух программных компонентов: программы написанной на языке Visual Basic, который транслирует представленную на рабочем письме информацию для внутреннего представления, которая используется другой программой. Вторая программа находится в памяти компьютера в виде отдельного программного модуля. Она выполняет оптимизацию и возвращает найденное решение первой программе, которая возобновляет данные на рабочем листе. С помощью ее можно найти оптимальное значение формулы, которая сохраняется в целевой ячейке. Эта процедура работает с группой ячеек, которые непосредственно связанные с формулой в целевой ячейке. Чтобы получить результат по формуле в целевой ячейке, процедура изменяет значение в ячейках, которые влияют на поиск. Для того, чтобы уменьшить множественное число значений, которые используются в модели задачи, применяют ограничение. Эти ограничения могут содержать ссылку на другие ячейки, которые влияют на поиск.

Общий алгоритм работы с надстройкой Поиск решения.

1. В меню Сервис выбрать команду Поиск решения .
2. В поле Установит целевую ячейку введите адрес ячейки, в которй находится формула, для оптимизации модели.
3. Для того, чтобы максимизировать значение целевой ячейки путем изменения значений влияющих ячеек, установите переключатель в положение Максимальному значению . Для того, чтобы минимизировать значение целевой ячейки путем изменения значений влияющих ячеек, установите переключатель в положение Минимальному значению . Для того, чтобы целевая ячейка приобретала значение конкретного числа, установите переключатель в положение Значение и введите соответствующее число.
4. В поле Изменяя ячейки введите адреса ячеек, которые изменяют свои значения, разделяя их запятыми. Изменяемые ячейки должны быть прямо или непрямо связанные с целевой ячейкой. Допускается установка до 200 изменяемых ячеек.
5. В поле Ограничения введите все ограничения, которые налагаются на поиск решения.
6. Нажмите кнопку Выполнить .
7. Для сохранения найденного решения установите переключатель в диалоговом окне Результаты поиска решения в положение Сохранить найденное решение . Для возобновления входных данных установите переключатель в положение Восстановить исходные значения.
8. Для того, чтобы прервать поиск решения, нажмите клавишу Еsс . MS Excel пересчитает лист с учетом найденных значений ячеек, которые влияют на результат.

Алгоритм роботи з надбудовою Поиск решения.

5. РЕШЕНИЕ ЗАДАЧИ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ ПРИ ПОМОЩИ ПРОГРАММЫ MS EXCEL.

Пример. Кондитерский цех для изготовления трех видов карамели А, В, С использует три основных вида сырья: сахар, патоку и фруктовое пюре. Нормы затрат сахара на изготовление 1кг карамели каждого вида соответственно уровни: 0,8кг; 0,5кг; 0,6кг; патоки – 04кг; 0,4кг; 0,3кг; фруктового пюре – 0кг; 0,1кг; 0,1кг. Конфеты можно производить в любых количествах (реализация обеспечена), но запас сырья ограниченный: запасы сахара – 80кг, патоки – 60кг, фруктового пюре – 12кг. Прибыль от реализации 1кг карамели вида А составляет 10грн., вида В – 11грн., вида С – 12грн.

Таблица 1

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

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

Основное содержание симплексного метода заключается в следующем:

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

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

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

1. Привести задачу к каноническому виду
2. Найти начальное опорное решение с "единичным базисом" (если опорное решение отсутствует, то задача не имеет решение ввиду несовместимости системы ограничений)
3. Вычислить оценки разложений векторов по базису опорного решения и заполнить таблицу симплексного метода
4. Если выполняется признак единственности оптимального решения, то решение задачи заканчивается
5. Если выполняется условие существования множества оптимальных решений, то путем простого перебора находят все оптимальные решения

Пример решения задачи симплексным методом

Пример 26.1

Решить симплексным методом задачу:

Решение:

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

Для этого в левую часть первого ограничения-неравенства вводим дополнительную переменную x 6 с коэффициентом +1. В целевую функцию переменная x 6 входит с коэффицентом ноль (т.е. не входит).

Получаем:

Находим начальное опорное решение. Для этого свободные (неразрешенные) переменные приравниваем к нулю х1 = х2 = х3 = 0.

Получаем опорное решение Х1 = (0,0,0,24,30,6) с единичным базисом Б1 = (А4, А5, А6).

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

Δ k = C б X k — c k

• C б = (с 1 , с 2 , ... , с m) — вектор коэффициентов целевой функции при базисных переменных
• X k = (x 1k , x 2k , ... , x mk) — вектор разложения соответствующего вектора А к по базису опорного решения
• С к — коэффициент целевой функции при переменной х к.

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

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

В последней строке таблицы с оценками Δ k в столбце "А 0 " записываются значения целевой функции на опорном решении Z(X 1).

Начальное опорное решение не является оптимальным, так как в задаче на максимум оценки Δ 1 = -2, Δ 3 = -9 для векторов А 1 и А 3 отрицательные.

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

Определим, введение какого из двух векторов приведет к большему приращению целевой функции.

Приращение целевой функции находится по формуле: .

Вычисляем значения параметра θ 01 для первого и третьего столбцов по формуле:

Получаем θ 01 = 6 при l = 1, θ 03 = 3 при l = 1 (таблица 26.1).

Находим приращение целевой функции при введении в базис первого вектора ΔZ 1 = — 6*(- 2) = 12, и третьего вектора ΔZ 3 = — 3*(- 9) = 27.

Следовательно, для более быстрого приближения к оптимальному решению необходимо ввести в базис опорного решения вектор А3 вместо первого вектора базиса А6, так как минимум параметра θ 03 достигается в первой строке (l = 1).

Производим преобразование Жордана с элементом Х13 = 2, получаем второе опорное решение Х2 = (0,0,3,21,42,0) с базисом Б2 = (А3, А4, А5). (таблица 26.2)

Это решение не является оптимальным, так как вектор А2 имеет отрицательную оценку Δ2 = — 6. Для улучшение решения необходимо ввести вектор А2 в базис опорного решения.

Определяем номер вектора, выводимого из базиса. Для этого вычисляем параметр θ 02 для второго столбца, он равен 7 при l = 2. Следовательно, из базиса выводим второй вектор базиса А4. Производим преобразование Жордана с элементом х 22 = 3, получаем третье опорное решение Х3 = (0,7,10,0,63,0) Б2 = (А3, А2, А5) (таблица 26.3).

Это решение является единственным оптимальным, так как для всех векторов, не входящих в базис оценки положительные

Δ 1 = 7/2, Δ 4 = 2, Δ 6 = 7/2.

Ответ: max Z(X) = 201 при Х = (0,7,10,0,63).

Метод линейного программирования в экономическом анализе

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

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

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

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

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

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

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

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

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

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

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

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

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

укрупненное планирование производства (составление графиков производства, минимизирующих общие издержки в связи с изменением ставки процента);

планирование ассортимента изделий (определение оптимальной структуры производства продуктов питания для человека);

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

регулирование запасов (определение оптимального сочетания продуктов на складе);

календарное планирование производства (составление календарных планов, минимизирующих издержки с учетом расходов на содержание запасов, оплату сверхурочной работы и заказов на стороне);

планирование распределения продукции и пр.

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

Чтобы решить задачу оптимизации, достаточно найти ее оптимальное решение, т.е. указать
такое, чтоf (X 0 )≥ f (X ) при любом
, или для случая минимизации -f (X 0 )≤ f (X ) при любом
.

Оптимизационная задача является неразрешенной, если она не имеет оптимального решения. В частности, задача максимизации будет неразрешенной, если целевая функция f (X ) не ограничена сверху на допустимом множестве W .

Методы решения оптимизационных задач зависят как от вида целевой функции f (X ) , так и от строения допустимого множества W . Если целевая функция в задаче является функцией п переменных, то методы решения называются методами математического программирования.

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

При этом система линейных уравнений (2) и неравенств (3), (4), определяющая допустимое множество решений задачи W , называется системой ограничений задачи линейного программирования, а линейная функция f (X ) называется целевой функцией, или критерием оптимальности.

Если математическая модель задачи линейного программирования имеет вид:

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

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

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

1) если в исходной задаче требуется определить максимум линейной функции, то следует изменить знак и искать минимум этой функции;

2) если в ограничениях правая часть отрицательна, то следует умножить это ограничение на (-1);

3) если среди ограничений имеются неравенства, то путем введения дополнительных неотрицательных переменных, они преобразуются в равенства;

4) если некоторая переменная x k не имеет ограничений по знаку, то она заменяется (в целевой функции и во всех ограничениях) разностью между двумя новыми неотрицательными переменными: x k = x ’ k - x 1 , где 1 – свободный индекс, x ’ k ≥ 0, x 1 ≥ 0.

Обобщая сказанное можно сделать следующие выводы:

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

2. Линейная функция может стремиться как к максимуму, так и к минимуму.

3. Переменные в модели всегда неотрицательны.

4. От любой задачи линейного программирования можно перейти к канонической (основной) задаче линейного программирования.

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

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

	………………………..

В задаче требуется максимизировать целевую функцию; все ограничения являются неравенствами со знаком ≤, все переменные х 1 , х 2 ,…,х п п управляющих переменных и m ограничений. Коэффициенты при переменных в целевой функции: c 1 , c 2 ,…, c n ; свободные члены: b 1 , b 2 ,…, b m .

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

	………………………..

В двойственной задаче требуется найти минимум целевой функции, ограничения – неравенства со знаком ≥, управляющие переменные y 1 , y 2 ,…, y m неотрицательны. Задача содержит m управляющих переменных и n ограничений. Коэффициенты целевой функции задачи b 1 , b 2 ,…, b m являются свободными членами исходной задачи линейного программирования, а свободные члены двойственной задачи c 1 , c 2 ,…, c n – коэффициентами целевой функции исходной задачи линейного программирования. Матрица коэффициентов двойственной задачи транспонирована, т.е. строки заменены столбцами, а столбцы – строками.

Задачи (9) –(10) и (11) – (12) образуют пару задач, называемую в линейном программировании двойственной парой.

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

1. Целевая функция исходной задачи задается на максимум, а целевая функция двойственной – на минимум.

2. Матрица А (13)

,

составленная из коэффициентов при неизвестных в системе ограничений (10) исходной задачи (9) – (10) и аналогичная матрица в двойственной задаче (11) – (12) получаются друг из друга транспонированием.

3. Число переменных в двойственной задаче (11) – (12) равно числу ограничений в системе (10) исходной задачи, а число ограничений в системе (12) двойственной задачи – числу переменных в исходной задаче.

4. Коэффициентами при неизвестных в целевой функции (11) двойственной задачи являются свободные члены в системе (10) исходной задачи, а правыми частями в ограничениях системы (12) двойственной задачи - коэффициенты при неизвестных в целевой функции (9) исходной задачи.

5. Если переменная x j исходной задачи (9) –(10) может принимать только лишь неотрицательные значения, то j - е ограничение в системе (12) двойственной задачи является неравенством вида ≥. Если же переменная x j может принимать как положительные, так и отрицательные значения, то j - е ограничение в системе (12) представляет собой уравнение. Аналогичные связи имеют место между ограничениями (10) исходной задачи и переменными двойственной задачи. Если i - е ограничение в системе (10) исходной задачи является неравенством, то i - я переменная двойственной задачи y i ≥ 0. Если же i - е ограничение есть уравнение, то переменная y i может принимать как положительные, так и отрицательные значения.

Идея последовательного улучшения решения легла в основу универсального метода решения задач линейного программирования – симплекс-метода. Геометрический смысл этого метода состоит в последовательном переходе от одной вершины многогранника ограничений (называемой первоначальной) к соседней, в которой линейная функция принимает лучшее (по крайней мере, не худшее) значение (по отношению к цели задачи) до тех пор, пока не будет найдено оптимальное решение – вершина, где достигается оптимальное значение функции цели (если задача имеет конечный оптимум). Идеи метода были опубликованы российским ученым Л.В. Канторовичем в 1939 г.

Для применения симплекс-метода в ограничения задачи вводятся дополнительные переменные y 1 , y 2 ,…, y i и условие исходной задачи принимает вид:

	……….…………………..

Эту постановку можно представить в виде таблицы – первой таблицы симплекс-метода (табл. 1.1).

Таблица 1.1.

Первая симплекс-таблица

	Свободные члены	Свободные переменные
		x 1	x 2		x n
y 1	b 1	a 11	a 12		a 1n
y 2	b 2	a 21	a 22		a 2n
y m	b m	a m1	a m2		a mn
Индексная строка		-c 1	-c 2		-c n

Для составления симплекс-таблицы можно применить определенные правила.

1. Для первой таблицы:

а) в первый столбец записывают y m – базисные переменные, которые находятся в уравнениях слева;

б) свободные переменные a mn выносят в верхнюю строку таблицы;

в) в остальные столбцы записывают коэффициенты перед свободными переменными.

2. Для последующих таблиц:

а) выбирается наименьший отрицательный элемент в индексной строке при отыскании максимума, но наибольший положительный – при отыскании минимума, исключая вектор свободных членов;

б) этот элемент определяет ключевой вектор-столбец и он вводится в базис;

в) компоненты вектора свободных членов делятся на положительные элементы ключевого столбца;

г) из полученных отношений выбирается наименьшее;

д) вектор-строка, содержащая наименьшее положительное частное - ключевая и выводится из базиса;

е) на пересечении ключевых строк и столбца находится разрешающий элемент;

ж) преобразование матрицы:

Каждый элемент ключевой строки делится на разрешающий элемент. Полученные частные являются элементами ключевой строки следующей таблицы,

Ключевой столбец в новой таблице – нули, за исключением разрешающего элемента,

Остальные элементы новой таблицы рассчитываются по схеме:

Новый элемент = Старый элемент –

- Элемент ключевой строки*Элемент ключевого столбца

Разрешающий элемент

Если нулевая строка (столбец) содержит нуль, то соответствующий столбец (строка0 в новой таблице не изменится.

3. Пункты «а» - «ж» повторяются до тех пор, пока в индексной строке не останется ни одного отрицательного элемента при отыскании максимума (но ни одного положительного при отыскании минимума).

Пример 1.1. Требуется принять решение об оптимальном плане производства трикотажа на месяц на ОАО «Свияж» с применением симплекс-методы.

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

Таблица 1.2.

Исходные данные

Ресурсы (i )	Вид продукции (j )				Запас ресурса (b i )
	Брюки спортивные модель 7060	Свитер мужской модель 55-1	Джемпер мужской модель 38-0	Костюм спортивный модель
	удельный расход ресурса (a ij )
Трудовые
Материальные
Оборудование
	x 1	x 2	x 3	x 4

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

По строке «Оборудование» проставлена сводная трудоемкость изготовления единицы изделия в нормо-часах как суммарная по всем детале-операциям. Остальные виды ресурсов также взяты в натуральных единицах: трудовые ресурсы – в часах; материальные – в дм 2 .

Строка «Прибыль» отражает прибыль от реализации единицы изделия, взята в из плановой калькуляции на единицу изделия.

Через x 1 , x 2 , x 3 , x 4 обозначили количество выпускаемой продукции каждого вида ассортимента.

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

В ограничениях задачи введем дополнительные переменные y 1 , y 2 , y 3 и перепишем условие задачи в виде уравнения:

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

Таблица 1.3.

Первая симплекс-таблица

	Свободные члены	Свободные переменные
		x 1	x 2	x 3	x 4
y 1
y 2
y 3
Индексная строка

В первый столбец записаны y i – базисные переменные, которые находятся в уравнении слева, а свободные переменные x j вынесены в верхнюю строку таблицы. В остальных столбцах записаны коэффициенты перед свободными переменными. Индексная строка – результат вычитания из нуля коэффициентов перед свободными переменными.

Для построения следующей таблицы выбирается наименьший отрицательный элемент в индексной строке (это 222). Этот элемент определяет ключевой вектор-столбец и он вводится в базис. Компоненты вектора свободных членов делятся на положительные элементы ключевого столбца и из полученных отношений выбирается наименьшее. Вектор-строка, содержащая наименьшее положительное частное, - ключевая и выводится из базиса (y 2 ). На пересечении ключевых строк и столбца находится разрешающий элемент (это 55,50).

Затем каждый элемент ключевой строки делится на разрешающий элемент. Полученные частные являются элементами ключевой строки следующей таблицы. В итоге получена вторая симплекс-таблица (табл. 1.4).

Таблица 1.4.

Вторая симплекс-таблица

	Свободные члены	Свободные переменные
		x 1	x 2	x 3	x 4
y 1
y 2
y 3
Индексная строка

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

В итоге получена табл. 1.5.

Таблица 1.5.

Итоговая симплекс-таблица

	Свободные члены	Свободные переменные
		x 1	x 2	x 3	x 4
y 1
y 2
y 3
Индексная строка

На основании таблицы 1.5 можно сделать выводы: в столбце свободных членов все элементы положительны (это значит, что полученное решение является допустимым); в индексной строке все элементы также положительны (это значит, что полученное решение – оптимально, т.е. максимизирует целевую функцию); оптимальным планом будут величины:
(значит, они базисные);
(так как они свободны); целевая функцияL = 4 201 195.

Из таблицы 1.5 также следует, что базисная переменная y 3 =9716, а свободные переменные y 1 = y 2 = 0, т.е. в оптимальном плане резервы трудовых и материальных ресурсов равны нулю, так как они используются полностью. А резерв ресурсов оборудования y 2 = 9716, что свидетельствует о его излишках.

Таким образом, в результате применения метода линейного программирования принято решение о производстве джемперов мужских выбранной модели в количестве 3981 шт., свитеров мужских модели 55-1 в количестве 29 875 шт.

Назначение сервиса . Онлайн-калькулятор предназначен для решения задач линейного программирования симплексным методом путем перехода к КЗЛП и СЗЛП . При этом задача на минимум целевой функции сводятся к задаче на поиск максимума через преобразование целевой функции F*(X) = -F(X) . Также имеется возможность составить двойственную задачу .

Решение происходит в три этапа:

1. Переход к КЗЛП. Любая ЗЛП вида ax ≤ b , ax ≥ b , ax = b (F(X) → extr) сводится к виду ax = b , F(X) → max ;
2. Переход к СЗЛП. КЗЛП вида ax = b сводится к виду ax ≤ b , F(X) → max ;
3. Решение симплексным методом;

Инструкция . Выберите количество переменных и количество строк (количество ограничений). Полученное решение сохраняется в файле Word .

Количество переменных 2 3 4 5 6 7 8 9 10
Количество строк (количество ограничений) 1 2 3 4 5 6 7 8 9 10

Переход от задачи минимизации целевой функции к задаче максимизации

Задача минимизации целевой функции F(X) легко может быть сведена к задаче максимизации функции F*(X) при тех же ограничениях путем введения функции: F*(X) = -F(X) . Обе задачи имеют одно и то же решение X*, и при этом min(F(X)) = -max(F*(X)) .
Проиллюстрируем этот факт графически:

F(x) → min

F(x) → max

Для оптимизации функции цели используем следующие понятия и методы.
Опорный план – план с определёнными через свободные базисными переменными.
Базисный план – опорный план с нулевыми базисными переменными.
Оптимальный план – базисный план, удовлетворяющий оптимальной функции цели (ФЦ).

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

Переменные x 1 , …, x m , входящие с единичными коэффициентами только в одно уравнение системы, с нулевыми - в остальные, называются базисными или зависимыми . В канонической системе каждому уравнению соответствует ровно одна базисная переменная. Переход осуществляется с помощью метода Гаусса-Жордана . Основная идея этого метода состоит в сведении системы m уравнений с n неизвестными к каноническому виду при помощи элементарных операций над строками.
Остальные n-m переменных (x m +1 ,…, x n) называются небазисными или независимыми переменными .

Базисное решение называется допустимым базисным решением , если значения входящих в него базисных переменных x j ≥0, что эквивалентно условию неотрицательности b j ≥0.
Допустимое базисное решение является угловой точкой допустимого множества S задачи линейного программирования и называется иногда опорным планом .
Если среди неотрицательных чисел b j есть равные нулю, то допустимое базисное решение называется вырожденным (вырожденной угловой точкой) и соответствующая задача линейного программирования называется вырожденной .

Пример №1 . Свести задачу линейного программирования к стандартной ЗЛП.
F(X) = x 1 + 2x 2 - 2x 3 → min при ограничениях:
4x 1 + 3x 2 - x 3 ≤10
- 2x 2 + 5x 3 ≥3
x 1 + 2x 3 =9
Для приведения ЗЛП к канонической форме необходимо:
1. Поменять знак у целевой функции. Сведем задачу F(X) → min к задаче F(X) → max. Для этого умножаем F(X) на (-1). В первом неравенстве смысла (≤) вводим базисную переменную x 4 ; во втором неравенстве смысла (≥) вводим базисную переменную x 5 со знаком минус.
4x 1 + 3x 2 -1x 3 + 1x 4 + 0x 5 = 10
0x 1 -2x 2 + 5x 3 + 0x 4 -1x 5 = 3
1x 1 + 0x 2 + 2x 3 + 0x 4 + 0x 5 = 9
F(X) = - x 1 - 2x 2 + 2x 3
Переход к СЗЛП .
Расширенная матрица системы ограничений-равенств данной задачи:

4	3	-1	1	0	10
0	-2	5	0	-1	3
1	0	2	0	0	9

Приведем систему к единичной матрице методом жордановских преобразований.
1. В качестве базовой переменной можно выбрать x 4 .
2. В качестве базовой переменной выбираем x 2 .
Разрешающий элемент РЭ=-2. Строка, соответствующая переменной x 2 , получена в результате деления всех элементов строки x 2 на разрешающий элемент РЭ=-2. На месте разрешающего элемента получаем 1. В остальных клетках столбца x 2 записываем нули. Все остальные элементы определяются по правилу прямоугольника. Представим расчет каждого элемента в виде таблицы:

4-(0 3):-2	3-(-2 3):-2	-1-(5 3):-2	1-(0 3):-2	0-(-1 3):-2	10-(3 3):-2
0: -2	-2: -2	5: -2	0: -2	-1: -2	3: -2
1-(0 0):-2	0-(-2 0):-2	2-(5 0):-2	0-(0 0):-2	0-(-1 0):-2	9-(3 0):-2

Получаем новую матрицу:

4	0	6 1 / 2	1	-1 1 / 2	14 1 / 2
0	1	-2 1 / 2	0	1 / 2	-1 1 / 2
1	0	2	0	0	9

3. В качестве базовой переменной выбираем x 3 .
Разрешающий элемент РЭ=2. Строка, соответствующая переменной x 3 , получена в результате деления всех элементов строки x 3 на разрешающий элемент РЭ=2. На месте разрешающего элемента получаем 1. В остальных клетках столбца x 3 записываем нули. Все остальные элементы определяются по правилу прямоугольника. Представим расчет каждого элемента в виде таблицы:

4-(1 6 1 / 2):2	0-(0 6 1 / 2):2	6 1 / 2 -(2 6 1 / 2):2	1-(0 6 1 / 2):2	-1 1 / 2 -(0 6 1 / 2):2	14 1 / 2 -(9 6 1 / 2):2
0-(1 -2 1 / 2):2	1-(0 -2 1 / 2):2	-2 1 / 2 -(2 -2 1 / 2):2	0-(0 -2 1 / 2):2	1 / 2 -(0 -2 1 / 2):2	-1 1 / 2 -(9 -2 1 / 2):2
1: 2	0: 2	2: 2	0: 2	0: 2	9: 2

Получаем новую матрицу:

3 / 4	0	0	1	-1 1 / 2	-14 3 / 4
1 1 / 4	1	0	0	1 / 2	9 3 / 4
1 / 2	0	1	0	0	4 1 / 2

Поскольку в системе имеется единичная матрица, то в качестве базисных переменных принимаем X = (4,2,3).
Соответствующие уравнения имеют вид:
3 / 4 x 1 + x 4 - 1 1 / 2 x 5 = -14 3 / 4
1 1 / 4 x 1 + x 2 + 1 / 2 x 5 = 9 3 / 4
1 / 2 x 1 + x 3 = 4 1 / 2
Выразим базисные переменные через остальные:
x 4 = - 3 / 4 x 1 + 1 1 / 2 x 5 -14 3 / 4
x 2 = - 1 1 / 4 x 1 - 1 / 2 x 5 +9 3 / 4
x 3 = - 1 / 2 x 1 +4 1 / 2
Подставим их в целевую функцию:
F(X) = - x 1 - 2(- 1 1 / 4 x 1 - 1 / 2 x 5 +9 3 / 4) + 2(- 1 / 2 x 1 +4 1 / 2)
или

Система неравенств:
- 3 / 4 x 1 + 1 1 / 2 x 5 -14 3 / 4 ≥ 0
- 1 1 / 4 x 1 - 1 / 2 x 5 +9 3 / 4 ≥ 0
- 1 / 2 x 1 +4 1 / 2 ≥ 0
Приводим систему неравенств к следующему виду:
3 / 4 x 1 - 1 1 / 2 x 5 ≤ -14 3 / 4
1 1 / 4 x 1 + 1 / 2 x 5 ≤ 9 3 / 4
1 / 2 x 1 ≤ 4 1 / 2
F(X) = 1 / 2 x 1 + x 5 -10 1 / 2 → max
Упростим систему.
3 / 4 x 1 - 1 1 / 2 x 2 ≤ -14 3 / 4
1 1 / 4 x 1 + 1 / 2 x 2 ≤ 9 3 / 4
1 / 2 x 1 ≤ 4 1 / 2
F(X) = 1 / 2 x 1 + x 2 -10 1 / 2 → max

Пример №2 . Найдите сначала графическим методом, а затем симплекс-методом решение задачи
F(X) = x 1 + x 2 - x 3 + x 5 +15 → max (min) при ограничениях:
-3x 1 + x 2 + x 3 =3
4x 1 + 2x 2 - x 4 =12
2x 1 - x 2 + x 5 =2
x 1 ≥ 0, x 2 ≥ 0, x 3 ≥ 0, x 4 ≥ 0, x 5 ≥ 0