Основы линейного программирования

Линейное программирование – основные понятия с примерами решения

Задача линейного программирования

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

Линейное программирование - основные понятия с примерами решения

Линейное программирование - основные понятия с примерами решения

Используя знак суммирования эту задачу можно записать следующим образом:

Линейное программирование - основные понятия с примерами решения

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

Линейное программирование - основные понятия с примерами решения

В данном случае введены векторы:

Линейное программирование - основные понятия с примерами решения

Здесь С – X – скалярное произведение векторов С и X.

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

Линейное программирование - основные понятия с примерами решения

где:

Линейное программирование - основные понятия с примерами решения

Здесь А – матрица коэффициентов системы уравнений, X -матрица-столбец переменных задачи; Линейное программирование - основные понятия с примерами решения – матрица-столбец правых частей системы ограничений.

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

Линейное программирование - основные понятия с примерами решения

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

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

Линейное программирование - основные понятия с примерами решенияприбавляется величина Линейное программирование - основные понятия с примерами решения такая, что переводит неравенство в равенство Линейное программирование - основные понятия с примерами решения, где: Линейное программирование - основные понятия с примерами решения

Неотрицательная переменная Линейное программирование - основные понятия с примерами решения называется дополнительной переменной.

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

Теорема. Каждому решению Линейное программирование - основные понятия с примерами решения неравенства Линейное программирование - основные понятия с примерами решения соответствует единственное решение Линейное программирование - основные понятия с примерами решения уравнения: Линейное программирование - основные понятия с примерами решенияи неравенства Линейное программирование - основные понятия с примерами решения и, наоборот, каждому решению Линейное программирование - основные понятия с примерами решения уравнения:Линейное программирование - основные понятия с примерами решения и неравенства Линейное программирование - основные понятия с примерами решения соответствует единственное решение Линейное программирование - основные понятия с примерами решения неравенства: Линейное программирование - основные понятия с примерами решения

Доказательство. Пусть Линейное программирование - основные понятия с примерами решения – решение неравенстваЛинейное программирование - основные понятия с примерами решения. Тогда:Линейное программирование - основные понятия с примерами решения

Если в уравнение Линейное программирование - основные понятия с примерами решения вместо переменных подставить значения Линейное программирование - основные понятия с примерами решения, получится:

Линейное программирование - основные понятия с примерами решения

Таким образом, решение Линейное программирование - основные понятия с примерами решения удовлетворяет уравнению: Линейное программирование - основные понятия с примерами решения и неравенству Линейное программирование - основные понятия с примерами решения.

Доказана первая часть теоремы.

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

т.е. Линейное программирование - основные понятия с примерами решения удовлетворяет неравенству: Линейное программирование - основные понятия с примерами решениячто и требовалось доказать.

Если в левую часть неравенств системы ограничений вида Линейное программирование - основные понятия с примерами решения

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

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

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

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

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

Множества допустимых решений

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

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

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

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

Граничные точки множества образуют его границу. Множество называется замкнутым, если оно содержит все свои граничные точки.

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

Пересечение двух или более выпуклых множеств будет выпуклым множеством, так как оно отвечает определению выпуклого множества.

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

Так, угловые точки треугольника – его вершины, круга – точки окружности, ее ограничивающие, а прямая, полуплоскость, плоскость, полупространство, пространство не имеют угловых точек.

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

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

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

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

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

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

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

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

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

Линейное программирование - основные понятия с примерами решения

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

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

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

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

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

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

Теорема. Любое опорное решение является угловой точкой области допустимых решений.

Теорема. Любая угловая точка области допустимых решений является опорным решением.

Пример:

Графический метод решения задачи линейной оптимизации рассмотрим на примере задачи производственного планирования при n = 2.

Предприятие изготавливает изделия двух видов А и В. Для производства изделий оно располагает сырьевыми ресурсами трех видов С, D и Е в объемах 600, 480 и 240 единиц соответственно. Нормы расхода ресурсов на единицу продукции каждого вида известны и представлены в табл. 14.1

Прибыль от реализации изделия А составляет 40 млн. руб., а изделия В – 50 млн.руб. Требуется найти объемы производства изделий А и В, обеспечивающие максимальную прибыль.

Линейное программирование - основные понятия с примерами решения

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

Тогда прибыль предприятия от реализацииЛинейное программирование - основные понятия с примерами решения изделий А и Линейное программирование - основные понятия с примерами решенияизделий В составит:

Линейное программирование - основные понятия с примерами решения

Ограничения по ресурсам будут иметь вид:

Линейное программирование - основные понятия с примерами решения

Естественно, объемы производства должны быть неотрицательными Линейное программирование - основные понятия с примерами решения

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

Линейное программирование - основные понятия с примерами решения

Каждое из записанных уравнений представляет собой прямую на плоскости, причем 4-я и 5-я прямые являются координатными осями.

Чтобы построить первую прямую, найдем точки ее пересечения с осями координат: Линейное программирование - основные понятия с примерами решения а при Линейное программирование - основные понятия с примерами решения.

Далее нас интересует, по какую сторону от прямой будет находиться полуплоскость, соответствующая первому неравенству. Чтобы определить искомую полуплоскость, возьмем точку O(0,0) подставив ее координаты в неравенство, видим, что оно удовлетворяется. Так как точка O(0,0) лежит левее первой прямой, то и полуплоскость будет находиться левее прямой

Линейное программирование - основные понятия с примерами решения. На рис 14 , расположение полуплоскости относительно первой прямой отмечено стрелками.

Аналогично построены 2-я и 3-я прямые и найдены полуплоскости, соответствующие 2-му и 3-му неравенству. Точки, удовлетворяющие ограничениям Линейное программирование - основные понятия с примерами решения, находятся в первом квадранте. Множество точек, удовлетворяющих всем ограничениям одновременно, является ОДР системы ограничений. Такой областью на графике (рис. 14.1) является многоугольник ОАВС.

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

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

Линейное программирование - основные понятия с примерами решения имеет координаты Линейное программирование - основные понятия с примерами решения

Линейное программирование - основные понятия с примерами решения

Рис. 14.1

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

Линейное программирование - основные понятия с примерами решения

Решив эту систему, получаем, что Линейное программирование - основные понятия с примерами решения

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

Линейное программирование - основные понятия с примерами решения

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

  1. Строится область допустимых решений;
  2. Строится вектор нормали к линии уровня с точкой приложении в начале координат;
  3. Перпендикулярно вектору нормали проводится одна из линий уровня, проходящая через начало координат;
  4. Линия уровня перемещается до положения опорной прямой. На этой прямой и будут находиться максимум или минимум функции.

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

На рис. 14.3 показан случай, когда прямая функции параллельна отрезку АВ, принадлежащему ОДР. Максимум функции Z достигается в точке А и в точке В, а, следовательно, и в любой точке отрезка АВ, т.к. эти точки могут быть выражены в виде линейной комбинации угловых точек А и В.

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

Линейное программирование - основные понятия с примерами решения

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

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

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

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

Рассмотрим две разновидности симплексного метода: симплекс-метод с естественным базисом и симплекс-метод с искусственным базисом (или М-метод).

  • Заказать решение задач по высшей математике

Симплекс-метод с естественным базисом

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

Для определенности предположим, что первые m векторов матрицы системы составляют единичную матрицу. Тогда очевиден первоначальный опорный план: Линейное программирование - основные понятия с примерами решения

Проверка на оптимальность опорного плана проходит с помощью критерия оптимальности, переход к другому опорному плану — с помощью преобразований Жордана-Гаусса и с использованием критерия оптимальности.

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

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

Теорема 1. Если для некоторого вектора, не входящего в базис, выполняется условие:

Линейное программирование - основные понятия с примерами решения

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

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

Теорема 2. Если для всех векторов выполняется условие Линейное программирование - основные понятия с примерами решениято полученный план является оптимальным.

На основании признака оптимальности в базис вводится вектор Ак, давший минимальную отрицательную величину симплекс-разности: Линейное программирование - основные понятия с примерами решения

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

Линейное программирование - основные понятия с примерами решения

Строка Линейное программирование - основные понятия с примерами решения называется направляющей, столбец Линейное программирование - основные понятия с примерами решенияи элемент Линейное программирование - основные понятия с примерами решениянаправляющими (последний называют также разрешающим элементом).

Элементы вводимой строки, соответствующей направляющей строке, в новой симплекс-таблице вычисляются по формулам:

Линейное программирование - основные понятия с примерами решения

а элементы любой другой i-й строки пересчитываются по формулам:

Линейное программирование - основные понятия с примерами решения

Значения базисных переменных нового опорного плана (показатели графы «план») рассчитываются по формулам:

Линейное программирование - основные понятия с примерами решения

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

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

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

Симплексный метод с искусственным базисом (М-метод)

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

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

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

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

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

Теория двойственности

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

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

Линейное программирование - основные понятия с примерами решения

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

Модель двойственной задачи имеет вид:

Линейное программирование - основные понятия с примерами решения

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

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

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

  1. Целевая функция исходной задачи формулируется на максимум, а целевая функция двойственной задачи – на минимум, при этом в задаче на максимум все неравенства в функциональных ограничениях имеют вид
  2. Матрица Линейное программирование - основные понятия с примерами решения, составленная из коэффициентов при неизвестных в системе ограничении исходной задачи, и аналогичная матрица Линейное программирование - основные понятия с примерами решения , в двойственной задаче получаются друг из друга транспонированием;
  3. Число переменных в двойственной задаче равно числу функциональных ограничений исходной задачи, а число ограничений в системе двойственной задачи – числу переменных в исходной задаче;
  4. Коэффициентами при неизвестных в целевой функции двойственной задачи являются свободные члены в системе ограничений исходной задачи, а правыми частями в ограничениях двойственной задачи – коэффициенты при неизвестных в целевой функции исходной задачи;
  5. Каждому ограничению одной задачи соответствует переменная другой задачи: номер переменной совпадает с номером ограничения; при этом ограничению, записанному в виде неравенства

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

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

Линейное программирование - основные понятия с примерами решения

где:

Линейное программирование - основные понятия с примерами решения

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

На некотором предприятии после выполнения годового плана возник вопрос: как поступить с остатками сырья? Из оставшегося сырья можно наладить производство продукции и реализовать его или продать сырье.

Предположим, что имеется два вида сырья Линейное программирование - основные понятия с примерами решения, остатки которого составляют соответственно 35 и 20 единиц. Из этого сырья можно наладить производство трех видов товаров: Линейное программирование - основные понятия с примерами решения

Линейное программирование - основные понятия с примерами решения

При исследовании первой возможности (наладить выпуск товаров Линейное программирование - основные понятия с примерами решения) возникает вопрос о плане выпуска, который задается тремя переменными Линейное программирование - основные понятия с примерами решения, которые соответствуют количеству произведенного товара. Эти переменные должны удовлетворять условиям:

Линейное программирование - основные понятия с примерами решения

Прибыль, которую получит предприятие от реализации товара, составит:

Линейное программирование - основные понятия с примерами решения

В интересах предприятия эту прибыль максимизировать.

Это прямая задача.

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

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

Это требование можно представить в виде системы неравенств: Линейное программирование - основные понятия с примерами решения

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

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

Теоремы двойственности

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

Возможны следующие случаи:

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

Первая теорема двойственности.

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

  1. В прямой и двойственной задачах имеются оптимальные решения, при этом значения целевых функций на оптимальных решениях совпадают: Линейное программирование - основные понятия с примерами решения
  2. В прямой задаче допустимое множество не пусто, а целевая функция на этом множестве не ограничена сверху. При этом у двойственной задачи будет пустое допустимое множество.
  3. В двойственной задаче допустимое множество не пусто, а целевая функция на этом множестве не ограничена снизу. При этом у прямой задачи допустимое множество оказывается пустым;
  4. Обе из рассматриваемых задач имеют пустые допустимые множества.

Вторая теорема двойственностн (теорема о дополняющей нежесткости):

Пусть Линейное программирование - основные понятия с примерами решения– допустимое решение прямой задачи, а Линейное программирование - основные понятия с примерами решения допустимое решение двойственной задачи.

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

Линейное программирование - основные понятия с примерами решения

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

Теорема об оценках:

Значения переменных Линейное программирование - основные понятия с примерами решения в оптимальном решении двойственной задачи представляют собой оценки влияния свободных членов Линейное программирование - основные понятия с примерами решения системы ограничений – неравенств прямой задачи на величину Линейное программирование - основные понятия с примерами решения:

Линейное программирование - основные понятия с примерами решения

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

Экономический смысл первой теоремы двойственности следующий. План производства X и набор ресурсов Y оказываются оптимальными тогда и только тогда, когда прибыль от реализации продукции, определенная при известных заранее ценах продукции Линейное программирование - основные понятия с примерами решения, равна затратам на ресурсы по «внутренним» (определяемым только из решения задачи) ценам ресурсов Линейное программирование - основные понятия с примерами решения Для всех других планов прибыль от продукции всегда меньше или равна стоимости затраченных ресурсов Линейное программирование - основные понятия с примерами решения, т.е. ценность выпущенной продукции не превосходит суммарной оценки затраченных ресурсов. Значит, величина Z(X)~ F(Y) характеризует производственные потери в зависимости от рассмотренной производственной программы и выбранных оценок ресурсов.

Задача линейного программирования

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

Общая задача линейного программирования формулируется следующим образом.
Найти максимум (или минимум) линейной функции n переменных :
(1.1)  
при ограничениях вида
(1.2)   left{begin{aligned}a_{11}x_1+a_{12}x_2+cdots+a_{1n}x_n&=b_1\............................&....\a_{p1}x_1+a_{p2}x_2+cdots+a_{pn}x_n&=b_p\a_{p+1,1}x_1+a_{p+1,2}x_2+cdots+a_{p+1,n}x_n&leqslant b_{p+1}\.....................................&.......\a_{p+q,1}x_1+a_{p+q,2}x_2+cdots+a_{p+q,n}x_n&leqslant b_{p+q}\a_{p+q+1,1}x_1+a_{p+q+1,2}x_2+cdots+a_{p+q+1,n}x_n&geqslant b_{p+q+1}\..........................................&.........\a_{p+q+s,1}x_1+a_{p+q+s,2}x_2+cdots+a_{p+q+s,n}x_n&geqslant b_{p+q+s}end{aligned}right.
(1.3)   .

Переменные задачи часто записывают в виде n-мерного вектора:
.

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

Система ограничений (1.2) может состоять из равенств
,
и неравенств обоих знаков:
, или
.

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

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

Различные формы задач ЛП

Каноническая форма задачи линейного программирования – это общая задача линейного программирования, в которой система ограничений состоит из равенств и условий не отрицательности для всех переменных:
           
(1.4)  
            . Симметричная форма задачи линейного программирования – это общая задача линейного программирования, в которой система ограничений состоит из неравенств одного знака и условий не отрицательности для всех переменных. Она имеет один из следующих двух видов:
           
(1.5)  
            .
Или
           
(1.6)  
            .

Теорема
Любую общую задачу линейного программирования (1.1) – (1.3) можно привести к каноническому виду (1.4). А любую задачу в канонической форме можно привести к любой из задач в симметричной форме (1.5) или (1.6).

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

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

переводится в равенство, введением дополнительной неотрицательной переменной :
.

Графический метод решения

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

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

Графическим методом можно решить задачу, если она имеет две переменные, или ее можно привести к задаче с двумя переменными.

Решим графическим способом следующую задачу.
(2.1)  
(2.2)  
(2.3)   .

Сначала проводим оси системы координат, и построим область допустимых решений (ОДР), которая определяется системой неравенств (2.2) и условиями не отрицательности переменных (2.3). Для построения ОДР, строим прямые, проходящие через границы неравенств:
.
С одной стороны каждой из построенных прямых соответствующее неравенство выполняется, а с другой стороны – нет. Поэтому ОДР ограничена этими прямыми. Также ОДР может быть ограничена осями координат, в силу неравенств . Замечаем, что точка удовлетворяет всем неравенствам (2.2)  и  (2.3). Поэтому она принадлежит ОДР. Заштриховываем область по границам прямых и осям координат, чтобы в нее вошла точка . Получаем, что ОДР является множеством точек внутри многоугольника вместе с его границей.

Теперь рассмотрим целевую функцию (2.1). Построим ее линию уровня, приравняв F к любому значению, например :
(2.4)   .
Строим прямую . С левой стороны от этой прямой . С правой стороны, . И чем больше мы удаляемся вправо и вверх, тем больше значение целевой функции F. Проводим прямую, параллельную прямой (2.4), так, чтобы она была максимально удалена в сторону увеличения значений F, то есть вправо, и при этом проходила хотя бы через одну точку ОДР. Такая прямая проходит через точку B с координатами . Это точка имеет наибольшее значение F среди всех точек ОДР. Поэтому является оптимальным планом с максимальным значением целевой функции:
.

Ответ

Решение задачи: .

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

Методы решения задач

Графический метод

Решение задачи графическим методом мы рассмотрели выше ⇑. Он применим, если в задаче имеются две переменные. Также он применим, если имеется n переменных и система ограничений содержит линейно независимых уравнения. Тогда, решая систему ограничений, мы можем выразить переменных через и , или через две другие переменные. В результате получим задачу с двумя переменными, которую можно решить графическим методом.

Метод перебора вершин

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

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

Решение задачи

Решим задачу (2.1) – (2.3) методом перебора вершин. При этом мы можем использовать результаты, полученные при решении графическим методом ⇑. Там мы нашли, что ОДЗ является многоугольником OABCD. И мы нашли координаты его вершин. Для каждой вершины мы можем вычислить значение целевой функции (2.1). Сравнивая их, можно определить наибольшее значение.

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

Для этого приведем задачу к канонической форме, вводя три дополнительные неотрицательные переменные :
(П.1)  
(П.2)  
(П.3)   .

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

1) В качестве свободных переменных возьмем и . Приравниваем их к нулю, и подставляем в (П.2); получаем: . Поскольку все , то мы нашли угловую точку ОДР или, что тоже самое, вершину многогранника ОДР: . На построении ⇑ ей соответствует точка O.

2) Возьмем свободные переменные и . Подставляя их нулевые значения в (П.2), получаем систему:

Решаем ее: . Поскольку все , то это угловая точка: , На построении ⇑ ей соответствует точка D.

3) Возьмем свободные переменные и . Подставляем их нулевые значения в (П.2). Решая систему, получаем: . Поскольку , то эта точка не принадлежит ОДЗ. Поэтому она не может быть планом задачи. Отбрасываем ее. На рисунке ⇑ ей соответствует точка пересечения прямой AB с осью .

4) Свободные переменные . Подставляя их нулевые значения в (П.2), находим: . Здесь также есть отрицательная переменная . Эта точка также не принадлежит ОДЗ. Отбрасываем ее. Это точка пересечения прямой BC с осью .

5) Свободные переменные . Подставляя в (П.2), находим решение системы: . Поскольку , то и эта точка не принадлежит ОДЗ. Отбрасываем ее. Это точка пересечения прямой DC с осью .

6) . Решение системы: . Поскольку все , то мы нашли угловую точку, которой на построении ⇑ соответствует точка A.

7) . Решение системы: . , точка не принадлежит ОДЗ. На рисунке ей соответствует точка пересечения прямой BC с осью .

8) . Решение системы: . , точка не принадлежит ОДЗ. Это точка пересечения прямых AB и DC.

9) . Решение системы: . Все . Это угловая точка – точка C.

10) . Решение системы: . Все . Это угловая точка. На построении ⇑ ей соответствует точка B.

Итак, мы нашли все угловые точки ОДР. Находим в них значения целевой функции.
;
;
;
;
.

Ответ

Наибольшим является значение целевой функции в точке B. Решение задачи: .

Симплексный метод

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

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

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

Решение задачи

Рассмотрим задачу (2.1) – (2.3). Как и при решении методом перебора вершин, вводим три дополнительных неотрицательных переменных . Получаем задачу в канонической форме:
(С.1)  
(С.2)  
(С.3)   .
Решаем задачу симплексным методом.

1. Вначале нам нужно найти любой опорный план, удовлетворяющий системе ограничений (С.2) – (С.3). Самый простой способ – это взять в качестве базиса дополнительные переменные . При этом из системы (С.2) мы сразу можем выразить базисные переменные через свободные:
(С.4)  
Приравнивая свободные переменные и к нулю, получаем первый опорный план, который мы обозначим буквой O: , или в сокращенной форме . Значение целевой функции: .
На рисунке ⇑, этому плану соответствует точка .

2. Теперь попробуем найти смежную вершину многогранника ОДР, в которой значение целевой функции было бы больше . Для этого нужно переместиться из вершины O вдоль одного из ребра многогранника на небольшое расстояние по направлению к смежной вершине и посмотреть, увеличилась ли при этом целевая функция?

2.1. Проверим, как изменится целевая функция, если свободной переменной вместо нулевого, присвоить положительное значение . При этом считаем, что мало отличается от нуля. То есть сделаем оценку свободной переменной . Положим, . Тогда, чтобы выполнялась система ограничений (С.4), необходимо также изменить базисные переменные:
.
Свободная переменная по прежнему равняется нулю. Подставляя в (С.4), и удаляя равные слагаемые в обеих частях равенств, получаем:
(С.5)  
Обозначим эту новую точку как . Найдем разность значений целевой функции в точках и :

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

2.2. Проделаем тоже самое с переменной . То есть сделаем оценку для свободной переменной . Положим, . Чтобы выполнялась система ограничений (С.4), также изменим базисные переменные. Положим . Свободная переменная при этом равняется нулю. Подставляя в (С.4), и удаляя равные слагаемые в обеих частях равенств, получаем:
(С.6)  
Обозначим эту новую точку как . Найдем разность значений целевой функции в точках и :

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

2.3. Итак, мы нашли, что если переменной или присвоить положительное значение, то целевая функция увеличится. Это означает, что первый опорный план не оптимален. Целевую функцию можно увеличить введением в базис или . При увеличении на единицу, целевая функция увеличится на . При увеличении на единицу, целевая функция увеличится на . В первом случае увеличение больше. Поэтому вводим в базис переменную . То есть считаем, что она может принимать отличные от нуля положительные значения.

3. Теперь определим следующий опорный план, то есть новую вершину многогранника ОДР с более высоким значением F. Определяем переменную, выходящую из базиса. Для этого нужно присвоить переменной максимально большое положительное значение, но чтобы при этом удовлетворялась система ограничений (С.4). При этом одна из переменных обратится в нуль. Ее мы исключим из состава базисных переменных. Переменная по прежнему имеет нулевое значение. Подставим в (С.4) :

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

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

Выводим , и вводим в состав базисных переменных. Для этого над системой (С.4) выполняем линейные преобразования, чтобы выразить базисные переменные через свободные . В результате линейных преобразований получаем эквивалентную систему:
(С.7)  
Приравнивая свободные переменные к нулю, получаем второй опорный план. Обозначим его буквой A: . Значение целевой функции:
.
На рисунке ⇑, этому плану соответствует точка . То есть в результате мы перешли из вершины в вершину многогранника ОДР.

4. Повторяем шаги 2 и 3.

4.1. Попробуем ввести в базис. Положим . Подставляем в (С.7):

Изменение целевой функции:
.

4.2. Попробуем ввести в базис . Положим . Подставляем в (С.7):

Изменение целевой функции:
.

Итак, если ввести в базис , то целевая функция увеличится. А если – уменьшится. Поэтому вводим в базис .

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

Переменная положительна при любых значениях . Переменная обращается в нуль при ; переменная – при . Наименьшее: . При этом переменная принимает нулевое значение и выходит из базиса.

Выводим из базиса. Для этого выражаем базисные переменные через свободные , преобразовав систему (С.7):
(С.8)  
Приравнивая свободные переменные и , получаем третий опорный план, который обозначим буквой B: . Значение целевой функции:
.
На рисунке ⇑, этому плану соответствует точка .

6. Повторяем шаги 4 и 5.

6.1. Попробуем ввести в базис . Положим . Подставляем в (С.8):

Изменение целевой функции:

.
. Введение в базис не приведет к увеличению значения целевой функции.

6.2. Попробуем ввести в базис . Положим . Подставляем в (С.8):

Изменение целевой функции:

.
И здесь . Введение в базис также не приведет к увеличению значения целевой функции. Поэтому последний план B оптимален.

Ответ

Решение задачи:
.

См. также Решение задач симплексным методом

Транспортная задача

См. также:

Транспортная задача – основные понятия, определения и теоремы
Решение транспортной задачи – онлайн калькулятор Транспортная задача – это задача линейного программирования следующего вида:
(Т.1)  
(Т.2)  
(Т.3)  
(Т.4)   ,
где .
В транспортной задаче требуется определить количество груза , которое нужно перевезти от -го поставщика к -му потребителю, чтобы суммарные затраты на перевозки были минимальны. Здесь – стоимость перевозки единицы груза от -го поставщика к -му потребителю; – мощность -го поставщика, то есть максимальное количество груза, которое может отправить поставщик; – мощность -го потребителя, то есть максимальное количество груза, которое может принять потребитель.

Транспортную задачу можно решить симплексным методом. Однако имеются методы, которые позволяют получить решение другими, как правило, более легкими способами, используя специфичный вид системы ограничений (Т.2) – (Т.3). Одним из таких методов является метод потенциалов. В нем, как и в симплексном методе ⇑, используется метод последовательного улучшения плана. Мы кратко рассмотрим применение этого метода на примере решения простой транспортной задачи.

Решение транспортной задачи методом потенциалов

Условие задачи

Пусть у нас имеется поставщика с мощностями , и потребителя с мощностями . Стоимость перевозки единицы груза от -го поставщика к -му потребителю задана в таблице:
(Т.5)  
Требуется найти план перевозок, при котором суммарные затраты на перевозки минимальны.

Решение

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

Задача имеет неотрицательных переменных:
.

Задача (Т.1) – (Т.4) имеет канонический вид. Подсчитаем число базисных переменных. Система ограничений (Т.2) – (Т.3) содержит уравнений:
(Т.6)  
Существует теорема, согласно которой, ранг r системы ограничений транспортной задачи равен . То есть система (Т.6) имеет линейно независимых уравнения. Тогда по теореме о числе базисных переменных ⇑, угловая точка ОДР имеет r = 4 базисных переменных, и свободных.

Поясним, почему ранг системы равен . Это означает, что эти уравнения имеют одну линейную зависимость. Найдем ее. Поскольку модель закрытая, то . Подставим (Т.2) и (Т.3):
;
.
Отсюда видно, что если сложить первые два уравнения (Т.6), и вычесть последние три, то получим тождество . Что означает, что система (Т.6) имеет линейную зависимость.

Применяем метод последовательного улучшения плана.

Метод северо-западного угла

Заполняем верхнюю левую ячейку, и вычеркиваем первую строку. Заполняем верхнюю левую ячейку, и вычеркиваем первую строку.

1. Вначале нам нужно найти любой опорный план, удовлетворяющий системе ограничений (Т.6) и условию не отрицательности переменных. Существует несколько методов, позволяющих это сделать. Мы применим метод северо-западного угла.

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

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

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

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

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

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

Первый опорный план. Первый опорный план.

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

В результате мы получили первый опорный план. Базисные переменные: . Свободные переменные: . Значение целевой функции:
.

Определение потенциалов

Определяем потенциалы . Для этого нужно найти любое решение системы уравнений, используя только заполненные клетки таблицы, то есть базисные переменные:
(Т.7)   .

Запишем уравнения (Т.7) для заполненных клеток:
(Т.8)  
Здесь 4 уравнения и 5 неизвестных. Поэтому одной переменной можно присвоить произвольное значение. Полагаем . Решаем систему (Т.8).
.

Находим оценки свободных клеток (то есть оценки свободных переменных) по формуле:
.

.

Поскольку есть отрицательная оценка , то план не оптимален. Вводим переменную с отрицательной оценкой в базис.

Переход к новому базису

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

Цикл с начальной вершиной в заданной пустой клетке – это ломаная, все вершины которой расположены в занятых клетках, кроме одной начальной вершины. И при этом две соседние вершины цикла расположены или в одной строке, или в одном столбце. Потенциалы и контур клетки (1,3). Потенциалы и контур клетки (1,3).

Строим цикл для клетки . Пронумеруем его вершины, начиная со свободной клетки.

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

Второй опорный план. Второй опорный план.

В результате получаем второй опорный план. Базисные переменные: . Свободные переменные: . Значение целевой функции:
.
Для первого опорного плана было . Мы видим, что значение целевой функции стало меньше.

Определение потенциалов нового плана

Определяем потенциалы для нового опорного плана. Запишем уравнения (Т.7) для заполненных клеток:
(Т.9)  
Полагаем . Решаем систему (Т.9).
.

Находим оценки свободных клеток по формуле:
.

.

Поскольку отрицательных оценок нет, то план оптимален.

Ответ

Наименьшее значение целевой функции . Оптимальный план показан в таблице 2 ⇑.

Использованная литература:
С. Гасс. Линейное программирование (методы и приложения). Москва, «Государственное издательство физико-математической литературы», 1961.
Общий курс высшей математики для экономистов. Под общей редакцией В. И. Ермакова. Москва, «ИНФРА-М», 2007.
К. Н. Лунгу. Линейное программирование. Руководство к решению задач. Москва, «ФИЗМАТЛИТ», 2005.
Д. Б. Юдин, Е. Г. Гольштейн. Задачи и методы линейного программирования. Москва, «Советское радио», 1961.

Автор: Олег Одинцов.     Опубликовано: 08-04-2021

Рейтинг
( 1 оценка, среднее 5 из 5 )
Загрузка ...