Система ограничений может состоять из уравнений

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

Введение в линейное программирование

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

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

Задача условной оптимизации называется задачей линейного программирования (ЛП), если целевая функция и все функции ограничений являются линейными функциями: (5.1)
где c_i,b_j,a_ij постоянные коэффициенты. Это есть стандартная форма задачи ЛП. В общем случае ограничения могут иметь знак „» или „=». Однако, умножая неравенство на -1 и заменяя равенство двумя неравенствами „≤» и „≥», можно придти к стандартной форме. Кроме того, взяв вместо f(x) функцию — f(x), можно получить задачу на минимум.
Обозначим через c=(c₁ ,…,c_n) — вектор коэффициентов целевой функции, b =(b₁,…,b_k) — вектор свободных членов ограничений, — матрицу коэффициентов ограничений и запишем нашу задачу в векторной форме: (5.2)
где — скалярное произведение двух векторов c и x. Такая компактная запись удобна для теоретических исследований.
Несколько примеров задач, которые сводятся к задачам линейного программирования:

Задача оптимального раскроя материала. Фирма изготовляет изделие состоящее из р деталей. Причем в одно изделие эти детали входят в количествах k₁ . k_r . С этой целью производится раскрой m партий материала. В i-ой партии имеется b_i единиц материала. Каждую единицу материала можно раскроить на детали n способами. При раскрое единицы i-ой партии j-м способом получается а_ijr деталей r-го вида. Требуется составить такой план раскроя материала, чтобы из них получить максимальное число изделий.

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

Задача о назначениях на работу. Имеется n работ и n исполнителей. Стоимость выполнения работы i исполнителем j равна c_ij. Нужно распределить исполнителей на работы так, чтобы минимизировать затраты на оплату труда.

3адача о смесях (о рационе). Из m видов исходных материалов каждый из которых состоит из n компонент, составить смесь, в которой содержание компонент должно быть не меньше b₁ . b_n. Известны цены единиц материалов с₁ . с_m и удельный вес j-го компонента в единице i-го материала. Требуется составить смесь, в которой затраты будут минимальными.

Задача о рюкзаке. Имеется n предметов. Вес предмета i равен р_i , ценность – с_i (i=1. n). Требуется при заданной ценности груза выбрать совокупность предметов минимального веса.

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

Для любой задачи ЛП можно составить двойственную к ней задачу по следующим правилам.
1. Привести исходную задачу ЛП к стандартной форме.
2. Ввести новые переменные по числу основных ограничений исходной задачи.
3. Составить новые ограничения из новых переменных в виде линейных неравенств, знаки которых противоположны знакам неравенств исходной задачи, коэффициентами которых служат элементы транспонированной матрицы исходной задачи, а свободными членами — коэффициенты при целевой функции исходной задачи.
4. Для новых переменных написать условия неотрицательности.
В результате для исходной задачи (5.1) получим следующую двойственную задачу ЛП: (5.3)
Задача (5.1) относительно задачи (5.3) называется прямой задачей ЛП . Векторная форма задачи (5.3) имеет вид: (5.4)
Рассмотрение взаимно двойственных задач ЛП полезно как с теоретической, так и с практической точек зрения. Это видно из следующих утверждений.
1. Если одна из задач (5.1) и (5.3) имеет оптимальное решение, то и другая имеет оптимальное решение, причем
2. Если целевая функция одной из задач неограниченна, то ограничения другой задачи несовместны (т.е. множество допустимых решений пусто).
3. Для того, чтобы допустимое решение и были оптимальными решениями соответствующих задач (5.1) и (2.3) , необходимо и достаточно, чтобы

4. Для любых допустимых решений x 0 и y 0 справедливо неравенство f(x 0 ) ≤ z(y 0 ); если f(x 0 ) = z(y 0 ), то x 0 и y 0 — оптимальные решения задач (5.1) и (5.3).
5. Если прямая задача (5.1) моделирует максимизацию дохода при ограниченных ресурсах, то двойственная задача (5.3) при тех же предпосылках моделирует минимизацию затрат при фиксированном уровне дохода.

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

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

Общая задача линейного программирования формулируется следующим образом.
Найти максимум (или минимум) линейной функции n переменных :
(1.1)
при ограничениях вида
(1.2)
(1.3) .

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

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

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

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

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

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

Теорема
Любую общую задачу линейного программирования (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 среди всех точек ОДР. Поэтому является оптимальным планом с максимальным значением целевой функции:
.

Свойства решений задач ЛП

Графический метод иллюстрирует основные свойства решений задач ЛП. Мы увидели, что поскольку ОДР ограничена конечным числом прямых, то она является выпуклым многоугольником. Далее, целевая функция не может иметь экстремума во внутренней точке ОДР, а достигает экстремума только на границе. Причем экстремум достигается в одной из вершин многоугольника ОДР. Если взять целевую функцию , то экстремум будет на отрезке BC . То есть экстремум может достигаться в двух вершинах, и во всех точках отрезка между ними.

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

Далее приводим более строгую трактовку этих рассуждений.

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

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

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

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

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

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

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

Теорема
Угловая точка ОДР (1.2) – (1.3) является решением системы из n уравнений, полученной из (1.2) – (1.3), вычеркиванием части неравенств, и заменой оставшихся неравенств равенствами.

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

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

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

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

Свободные переменные – это переменные задачи ЛП в канонической форме, на которые, в рассматриваемом опорном плане, наложено условие их равенства нулю: . Базисные переменные – это переменные задачи ЛП в канонической форме, которые в рассматриваемом опорном плане, не являются свободными. Они имеют неотрицательные значения, которые определяются из решения системы уравнений (1.4). Невырожденный план (невырожденное решение) – это опорный план, в котором все базисные переменные отличны от нуля. Вырожденный план (вырожденное решение) – это опорный план, в котором есть одна или несколько базисных переменных, равных нулю. Векторы условий – это n векторов, которые являются столбцами матрицы коэффициентов системы (1.4). Базис – это r векторов, которые являются столбцами матрицы коэффициентов системы (1.4) при базисных переменных. То есть базис – это векторы условий при базисных переменных.

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

Теорема о числе базисных переменных
При решении задачи линейного программирования в канонической форме ⇑, в любом опорном плане имеется r базисных переменных ⇑. Отсюда следует, что в опорном плане как минимум переменных равны нулю. Здесь n – число переменных; r – ранг матрицы системы ограничений (1.4), из которой определяются значения базисных переменных.

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

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

Решение задачи графическим методом мы рассмотрели выше ⇑. Он применим, если в задаче имеются две переменные. Также он применим, если имеется 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 оптимален.

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

Транспортную задачу можно решить симплексным методом. Однако имеются методы, которые позволяют получить решение другими, как правило, более легкими способами, используя специфичный вид системы ограничений (Т.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).

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

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

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

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

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

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

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

.

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

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

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

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

Составляют систему ограничения задачи

2. Составляют систему ограничения задачи.

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

В общем виде система записывается в виде

3. Задают целевую функцию.

Целевая функция – это функция Z(X) которая характеризует качество выполнения задачи, экстремум которой надо найти. В общем виде целевая функция записывается Z(X) = (max, min)

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

и условию неотрицательности 0 (j = ), которая обеспечивает экстремум целевой функции Z(Y) =

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

Множество допустимых решений образует область допустимых решений задачи (ОДР).

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

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

Математическая модель задачи должна иметь каноническую форму.

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

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

перейти от неравенств к уравнению следующим образом: в левую часть неравенств вводим дополнительную переменную с коэффициентом (+1) для неравенства () и (-1) для неравенства () дополнительные переменные не наложены целевые неотрицательности, то её заменяют разностью двух неотрицательных переменных, то есть:

= – (

Общий вид канонической формы:

Глава ΙΙ Решение задачи симплексным методом

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

Название метода от латинского simplecx – простой т.к. из начального область допустимых решений задачи имела простейший вид. Идеи метода предложил российский математик Контарович Л.В. в 1939 году и затем эту идею развил и разработал Дж. Данциг в 1949 году.

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

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

На предприятии в процессе производства используется 3 вида станков Ι, ІΙ, ІΙІ. При этом расходуется сырьё, трудовые ресурсы, и учитываются накладные расходы.

Известно, что для изготовления станка Ι – ого вида требуется 4 ед. сырья, 2 ед. трудовых ресурсов и 10 ед. накладных расходов; станка ΙІ – ого вида 6 ед. сырья, 2 ед. трудовых ресурсов и 8 ед. накладных расходов; для станка ΙΙІ – ого вида требуется 4 ед. сырья, 2 ед. трудовых ресурсов и 18 ед. накладных расходов; Предприятие имеет в наличии 420 ед. сырья, 120 ед. трудовых ресурсов и 250 ед. накладных ресурсов.

Прибыль от реализации станка І вида — 28 тыс. руб., ІΙ вида — 24 тыс. руб., ΙІΙ вида — 20 тыс. руб. Условия производства требует, чтобы трудовые ресурсы были использованы полностью, а накладные расходы были бы не менее имеющихся в наличии.

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

§ 2 Составление математической модели задачи

Записываем условие задачи в виде таблицы.

1. Выбирают переменные задачи.

Пусть количество производимых станков 1-ого, 2-ого и 3-его вида,