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

Что такое оптимум задачи линейного программирования

  • автор:

Что такое оптимум задачи линейного программирования

МОДЕЛИ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ

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

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

Функция n переменных x 1, x 2, . x n

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

Иногда линейной называют также функцию вида

отличающуюся от предыдущей постоянным слагаемым d .

а также неравенства

называются линейным равенством и линейными неравенствами , если функция

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

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

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

Всякий набор значений переменных, то есть вектор X значений,

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

Решить задачу линейного программирования — значит найти ее оптимальный план и оптимум.

Вопрос 24. Что такое оптимальный план задачи линейного программирования?

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

Вопрос 25. Если оптимальное значение основной переменной задачи линейного программирования больше нуля, то оптимальное значение дополнительной переменной в соответствующем ограничении двойственной задачи .

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

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

1. всегда 2. никогда 3. если задача на максимум

Вопрос 28. Сколько допустимых планов может иметь задача линейного программирования (не целочисленная)?

1. 0 или 1 2. всегда 1 3. 0, 1 или бесконечное множество

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

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

Вопрос 30. Что такое допустимый план задачи линейного программирования?

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

Вопрос 31. Если задача линейного программирования разрешима, в каком случае будет разрешима двойственная к ней задача?

1. всегда 2. другое 3. никогда

Вопрос 32. В каком направлении сдвигают линию уровня целевой функции при решении задачи линейного программирования на максимум?

1. вверх 2. в направлении антиградиента 3. в направлении градиента

Вопрос 33. Сколько оптимальных планов может иметь задача линейного программирования (не целочисленная)?

1. 0 или 1 2. всегда 1 3. 0, 1 или бесконечное множество

Вопрос 34. Каким образом можно избавиться от не ограниченных по знаку переменных в системе ограничений?

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

Вопрос 35. Какое из приведенных ниже утверждений о разрешимости сопряженных задач является НЕ верным?

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

Вопрос 36. На графике оптимальный план задачи линейного программирования с двумя переменными представляет собой. 1. верхнюю точку области допустимых планов 2. пересечение градиента и крайнего положения линии уровня 3. пересечение области допустимых планов и крайнего положения линии уровня

Вопрос 37. В чем заключается критерий допустимости симплексной таблицы?

1. все коэффициенты в критериальном ограничении должны быть неотрицательными (или неположительными) 2. все свободные члены должны быть неотрицательными (или неположительными) 3. все свободные члены должны быть неотрицательными

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

1. основных переменных 2. другое 3. ограничений

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

1. суммируются дополнительные переменные 2. другое 3. суммируются искусственные переменные

Вопрос 40. Какая переменная входит в базис при преобразовании симплексной таблицы?

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

Что такое оптимум задачи линейного программирования

ГРАФИКА ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ

Область допустимых планов . Оптимальный план и оптимум

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

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

Планы такой задачи — это пары чисел (x1, x2). Им соответствуют точки координатной плоскости ( Рис. 2.1 ).

Рис. STYLEREF 1 \ s 2 . 1 . Ограниченная область допустимых планов

Область допустимых планов

Рассмотрим систему ограничений. Возьмем одно из неравенств системы,

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

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

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

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

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

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

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

Оптимальный план и оптимум

Как найти оптимальный план? Обратимся к целевой функции. Приравняем ее какой-нибудь константе d

Мы получили уравнение, определяющее некоторую прямую на координатной плоскости. Все точки этой прямой соответствуют одному и тому же значению целевой функции, равному d, одному и тому же уровню значений. Такая прямая называется линией уровня целевой функции.

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

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

Однако, существует более простой способ. А именно, изобразим в координатной плоскости вектор, начало которого находится в начале координат, а конец которого упирается в точку с координатами ( c 1, c2), где c 1 и c2 — коэффициенты при переменных в целевой функции. Это градиент целевой функции. Этот вектор-градиент перпендикулярен всем линиям уровня целевой функции, а его направление указывает направление роста значений функции.

На Рис. 2.1 изображен градиент, направленный внутрь первого координатного угла. Это означает, что коэффициенты c 1 и c 2 положительны. Разумеется, это не во всех задачах так, в разных задачах знаки этих коэффициентов могут быть различными. Начало градиента всегда располагается в начале координат, но направлен он может быть в любую сторону.

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

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

На Рис. 2.1 множество оптимальных планов состоит из одной единственной точки — вершины многоугольника, обозначенной посредством X*max .

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

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

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

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

Линейное программирование – метод решения задач оптимизации.

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

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

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

Или в сокращённом виде с сигмой:

Можно встретить обозначение целевой функции и через C, и через F.

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

Или в сокращённом виде:

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

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

Задачей линейного программирования в стандартной, или, как говорят иначе, нормальной форме, называется задача, в которой требуется найти максимум целевой функции при ограничениях, заданных системой неравенств одного смысла, то есть с одинаковым знаком, и этот знак — «меньше или равно», причём действует также условие неотрицательности переменных. Если в задаче линейного программирования, заданной в стандартной форме, требуется найти минимум целевой функции, то система ограничений состоит из системы неравенств со знаком «больше или равно».

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

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

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

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

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

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

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

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

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

Разберём несколько типов экономических задач и запишем их в виде математических соотношений. Или, говоря иначе, построим математическую модель предметной области.

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

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

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

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

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

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

Для изготовления двух видов продукции и требуется четыре вида ресурсов (сырья): , , , . Запасы сырья — соответственно , , , единицы.

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

Решение. Для удобства сначала все данные запишем в виде таблицы:

Виды сырья Запасы сырья Виды продукции
Доход от реализации одной единицы продукции

Тогда на основании таблицы запишутся неравенства (ограничения):

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

Из остальных строк таблицы составим ещё 3 неравенства системы.

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

Пример 2. Схема задачи о смесях.

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

Требуется найти наиболее дешёвый набор из доступных исходных материалов, обеспечивающих получение смеси с заданными свойствами. Полученные смеси должны иметь в свойм составе n различных компонент в определённых количествах, а сами компоненты являются составными частями m исходных материалов. Для упрощения примем, что n=3 и m=4. Пусть стоимость одной единицы материала соответственно составляет , , , . В свою очередь необходимое количество каждой из компонент в смеси составляет соответственно , , .

Решение. Строим таблицу:

Виды материалов Цена единицы материала Количество компонент в материале
K 1 K 2 K 3
1
2
3
4
Необходимое количество компонент

Коэффициенты a ij показывают количество j-й компоненты в единице i-го материала K 1 . Требуется получить смесь с заданными свойствами при наименьших затратах на приобретение материалов.

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

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

Пример 3. Схема задачи о питании.

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

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

Решение. Строим таблицу:

Питательные вещества Норма Продукты
Ж
Б
У
В
Стоимость питательных веществ

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

Запишем задачу в виде математических соотношений. В задаче неизвестно количество каждого вида продукта. Поэтому обозначим количество продукта буквой , количество продукта — буквой , количество продукта — буквой .

Получим систему неравенств (ограничений):

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

Пример 4. Схема задачи об использовании мощностей оборудования.

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

Предприятию требуется за время T выпустить N 1 единиц продукции П 1 и N 2 единиц продукции П 2 . Каждый из этих двух видов продукции может производиться тремя машинами A, B, C . Составить оптимальный план работы машин, то есть найти время загрузки машин A, B, C , с тем расчётом, чтобы стоимость изготовления всей продукции предприятием оказалась минимальной.

Мощность машин задана следующей таблицей:

Машины П 1 П 2
A
B
C

В этой таблице — количество единиц продукции, производимое за единицу времени.

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

Машины П 1 П 2
A
B
C

В этой таблице, например, число означает цену одной единицы рабочего времени машины B , затрачиваемой на изготовление одной единицы продукции П 1 .

Запишем задачу в виде математических соотношений. Неизвестным является время загрузки машин по производству продукции. Обозначим через время загрузки машины A по изготовлению продукции П 1 , через — время загрузки машины A по изготовлению продукции П 2 . Аналогично — время загрузки машины B по изготовлению продукции П 1 , — время загрузки машины B по изготовлению продукции П 2 , — время загрузки машины C по изготовлению продукции П 1 , время загрузки машины C по изготовлению продукции П 2 .

Машины A, B, C работают одновременно, значит если обозначим время одновременной работы всех трёх машин буквой T , то получим систему неравенств:

Машина A изготовлением продукции П 1 занята единицы времени на единицы продукции. Машина B изготовлением П 1 занята единицы времени по единицы продукции.

Аналогично машина C изготовлением П 1 занята единицы времени, по единицы продукции и т.д. Всего нужно N 1 единиц продукции П 1 и N 2 единицы П 2 .

То есть получаем ещё одну систему:

Тогда общая стоимость всей продукции запишется в виде равенства:

Окончательно получаем систему ограничений, состоящую из соотношений:

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

Пример 5. Транспортная задача (схема).

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

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

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

Решение. Считаем, что запас всего груза на обоих пунктах отправления равен потребности в этом грузе на всех трёх пунктах назначения, т. е.

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

Пункт отправления Пункт назначения Запас груза
Потребность в грузе

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

Тогда система ограничений запишется в виде уравнений:

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

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

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

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

Пример 6. Записать систему неравенств

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

Решение. Прибавляя к левым частям неравенств по одной дополнительной переменной, получим систему уравнений:

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

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

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

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

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

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

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

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

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

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

Справедливость этого утверждения вытекает из теорем 2 и 4.

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

Продолжение темы «Линейное программирование»

  • Графический метод решения задач линейного программирования
  • Пример задачи линейного программирования: задача использования ресурсов, её графическое решение
  • Симплекс-метод решения задач линейного программирования: типичный пример и алгоритм
  • Симплекс-метод: случай, когда максимум целевой функции — бесконечность
  • Симплекс-метод: случай, когда система не имеет ни одного решения
  • Симплекс-метод: случай, когда оптимальное решение — не единственное
  • Двойственная задача линейного программирования
  • Решение задачи целочисленного программирования: методы и примеры
  • Решение транспортной задачи распределительным методом на примерах

Добавить комментарий

Ваш адрес email не будет опубликован. Обязательные поля помечены *