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

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

K=m*n-(m+n-1)=(m-1)(n-1).

Для оптимального плана (m-1)(n-1) перевозок должны быть равны нулю.

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

Допустимый план называется опорным, если в нем отличны от нуля не более n+m-1 базисных перевозок, а остальные перевозки равны нулю.

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

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

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

Нахождение решения транспортной задачи заключается в преобразовании транспортной таблицы (табл.3).

Таблица 3

Улучшить план перевозок можно, произведя в нем «циклическую перестановку».

Циклом в транспортной таблице называется несколько клеток, соединенных замкнутой ломанной линией, которая в каждой клетке совершает поворот на ± 90◦.

Пусть знак «+» это те вершины цикла, в которых перевозки увеличиваются и знаком «-» - те вершины, в которых они уменьшаются. Цикл с отмеченными вершинами называется означенным (табл.4). В цикле знаки вершины должны чередоваться.

              Таблица 4

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

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

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

При улучшении плана с помощью циклических перестановок используют прием из симплекс-метода: на каждом шаге заменяют одну свободную переменную на базисную. Можно доказать, что для любой свободной клетки транспортной таблицы существует единственный цикл; одна из вершин которого лежит в этой свободной клетке, а все остальные вершины лежат в базисных клетках. Если цена цикла со знаком «+» в свободной клетке отрицательна, то имеет смысл совершить перестановку для улучшения плана.

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

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

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

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

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

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

Задача 1:

Предприятие предполагает выпускать два вида продукции А1 и А2 для производства которых используется сырьё  трёх видов.

Производство обеспечено сырьём каждого вида в количествах : 600, 357, 600 кг. Количество единиц сырья  каждого вида, необходимое для изготовления единицы изделия А1 А2 , а также прибыль, получаемая предприятием от реализации единицы продукции, даны в табл.1.

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

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

Задача

F(X)=22x1+15x2→ max,

x1+x2 170

2x1+ 3x2 438

  2x1+x2≤290             

x10 x20

Решение

Алгоритм решения ЗЛП:

1.Построить область допустимых значений;

2. Построить вектор (с1,с2) с точкой приложения в начале координат;

3. Перпендикулярно вектору провести одну из линий уровня, например с1х 1 + с2 х2=0;

4. Линию уровня переместить до положения опорной прямой. На этой прямой будет находиться минимум или максимум.

Изобразим на плоскости систему координат Ох1х2 и построим граничные прямые области допустимых решений (рис.3).