СИМПЛЕКС-МЕТОД ЗАДАЧ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ

(Идея симплекс-метода)

Чтобы решить задачу ЛП надо представить ее в каноническом виде:

(4.1)

(4.2)

С помощью метода Жордана-Гаусса преобразуем систему (2) и выделим базисные переменные.

Если , то система имеет единственное решение, подставляем его в целевую функцию (1) и получаем решение задачи ЛП.

Если , то выражаем базисные переменные через свободные. Пусть базисные переменные – ,…, ,свободные переменные – .

Получаем преобразованную задачу:

(4.3)

(4.4)

В этой задаче:

1. Система ограничений выражена через свободные переменные;

2. Целевая функция выражена через свободные переменные;

3. Все ;

4. Все .

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

Одно из решений системы (4.4) получается, если в ней свободные неизвестные приравнять к 0. Получаем базисное решение:

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

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

(4.3)

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

Случай 1. Среди коэффициентов целевой функции (3) нет положительных:

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

Т.к. ищем максимальное решение, то уже найденное решение и будет оптимальным. Но оно может быть не единственным, если в целевой функции (4.3) есть коэффициенты, равные 0.

Случай 2. Среди коэффициентов целевой функции (4.3) найдется хотя бы один положительный, например .

Положим в уравнениях (4.3) и (4.4) все свободные переменные равными нулю, кроме .

Тогда система (4.4) и уравнение (4.3) примут вид:

(4.5)

(4.6)

Если увеличивать, то будет увеличиваться и целевая функция (4.5), но возможность роста определяется системой (4.6) и зависит от знаков коэффициентов .

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

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

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

Это означает, что: , для тех индексов , у которых .

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

Допустим, что оно достигается при , т.е.:

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

Далее целевую функцию (4.3) и систему (4.4) записываем через новые свободные переменные.

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

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

1. Записываем систему ограничений в каноническом виде;

2. Записываем базисное решение;

3. Выбираем переменную из целевой функции, которую будем увеличивать;

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

5. Среди уравнений выбираем то, где рост переменной минимален;

6. Делаем выбранную переменную базисной, а базисную свободной;

7. Записываем систему ограничений и целевую функцию через новую свободную переменную;

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

Пример 4.1. Озеро можно заселить двумя видами рыб А и В. Средняя масса рыбы для вида А равна 2 кг и для вида В – 1 кг. В озере имеется два вида пищи: P₁ и Р₂. Средние потребности одной рыбы вида А составляют 1 ед. корма P₁ и 3 ед. корма P₂ в день. Аналогичные потребности для рыбы вида В составляют 2 ед. P₁ и 1 ед. P₂. Ежедневный запас пищи поддерживается на уровне500 ед. P₁ и 900 ед. Р₂. Как следует заселить озеро рыбами, чтобы максимизировать общую массу рыб?

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

Вид пищи	Кол-во корма для одной рыбы	Ежедневный запас пищи
Рыбы вида А	Рыбы вида В
Р₁
Р₂
Вес рыб (кг)

Составим математическую модель задачи.

Введем переменные задачи:

х₁ – количество рыб вида А;

x₂ – количество рыб вида В.

Составим систему ограничений:

Зададим целевую функцию. Масса рыб → max.

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

2. Запишем базисное решение.

F₀(0;0;500;900) = 0.

3. Выбираем переменную из целевой функции , которую будем увеличивать.

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

5. Выбираем второе уравнение, т.к. рост переменной минимален.

6. Делаем выбранную переменную базисной, а базисную свободной.

7. Записываем систему ограничений и целевую функцию через новую свободную переменную.

Подставим в и целевую функцию.

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

2. Запишем базисное решение.

F₁(300;0;200;0) = 0.

3. Выбираем переменную из целевой функции , которую будем увеличивать.

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

5. Выбираем первое уравнение, т.к. рост переменной минимален.

6. Делаем выбранную переменную базисной, а базисную свободной.

7. Записываем систему ограничений и целевую функцию через новую свободную переменную.

Подставим в и целевую функцию.

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

2. Запишем базисное решение.

F₁(260;120;0;0) = 640.

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

Ответ: Для получения максимального веса рыб 640кг, следует заселить 260 рыб вида А и 120 рыб вида В.

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

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

Виды сырья	Нормы затрат сырья (кг) на одно изделие	Общее количество сырья (кг)
А	В	С
I
II
III
Цена одного изделия (?)

Решение: Составим математическую модель. Обозначим:

– выпуск изделий вида А;

– выпуск изделий вида В;

– выпуск изделий вида С.

Запишем систему ограничений:

Общая стоимость произведенных товаров составляет: .

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

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

2. Запишем базисное решение.

F₀(0;0;0;120;96;180) = 0.

3. Выбираем переменную из целевой функции , которую будем увеличивать.

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

5. Выбираем второе уравнение, т.к. рост переменной минимален.

6. Делаем выбранную переменную базисной, а базисную свободной.

7. Записываем систему ограничений и целевую функцию через новую свободную переменную.

Подставим в , и целевую функцию.

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

2. Запишем базисное решение.

F₁(0;0;24;24;0;108) = 384.

3. Выбираем переменную из целевой функции , которую будем увеличивать.

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

5. Выбираем первое уравнение, т.к. рост переменной минимален.

6. Делаем выбранную переменную базисной, а базисную свободной.

7. Записываем систему ограничений и целевую функцию через новую свободную переменную.

Подставим в , и целевую функцию.

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

2. Запишем базисное решение.

F₂(0;8;20;0;0;96) = 400.

Ответ: Для получения максимальной стоимости всей произведенной продукции 400?, необходимо производить 0 изделий вида А, 8 изделий вида В и 20 изделие вида С.

ТАБЛИЧНАЯ ИНТЕРПРЕТАЦИЯ СИМПЛЕКСНОГО МЕТОДА

Рассмотрим решение задач симплексным методом используя построение симплексных таблиц.

Пример 5.1. На приобретение мебели для офиса предприятием было выделено средств на сумму 70 тыс. руб. Мебель должна быть размещена на общей площади, не превышающей 100 м². Предприятие может заказать мебель двух типов: А и В, стоимостью 15 тыс. руб. и 10 тыс. руб. соответственно. Мебели типа А требуется 12 м² площади (с учетом проходов), мебели типа В – 14 м² (с учетом проходов). Доход от эксплуатации мебели типа А составляет 18 тыс. руб. в месяц, В – 12 тыс. руб. в месяц.

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

Решение:

Составим математическую модель задачи.

Введем переменные задачи:

х₁ – количество мебели вида А,

x₂ – количество мебели вида В.

Составим систему ограничений:

Зададим целевую функцию:

F(x) = 18x₁ + 12x₂ → max

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

где, x₃ - остаток выделенных средств (тыс. руб.) на приобретение мебели,

x₄- остаток площади (м²) на которой размещается мебель.

F(x) = 18∙x₁ + 12∙x₂ + 0∙x₃ + 0∙x₄→ max

- данная задача представлена в каноническом виде;

- система уравнений приведена к единичному базису;

- каждое уравнение системы ограничений содержит базисную переменную;

- правые части всех ограничений неотрицательны.

Строим симплекс – таблицу, имеющую следующий вид:

Б.П.	С			b	Ө
x₁	x₂	…	…
…
…
∆к

где

Б.П. – столбец базисных переменных

С – содержит коэффициенты при базисных переменных в целевой функции;

b – столбец свободных членов;

∆к – индексная строка. По ее данным определяется, является ли решение оптимальным.

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

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

В столбец Б.П. записываем базисные (новые введенные) переменные x_{3 ,}x_{4 .}

В столбце С и над переменными записываем коэффициенты переменных целевой функции.

Б.П.	С			b	Ө
x₁	x₂	x₃	x₄
x₃
x₄
∆к		-18	-12

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

Если целевая функция исследуется как максимум, то в оптимальном плане все оценки должны быть ≥ 0. Если индексная строка не отвечает критериям оптимальности, то план можно улучшить. У нас все оценки отрицательны.

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

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

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

Для выбора разрешающей строки в столбцах Ө составляем следующие отношения , где a_i — коэффициенты (берем только положительные) при x_i в разрешающей строке. Т.е. Элементы столбца свободных членов симплексной таблицы делят на соответствующие положительные элементы разрешающего столбца. Выбираем минимальное значение из данных отношений Ө = { } = . Данная строка определяет переменную, которая на следующем этапе выйдет из базиса и станет свободной.

Разрешающие столбец и строку обозначим стрелками.

В нашем случае вместо переменной x₃в базисе будет переменная x_1.

На пересечении разрешающего столбца и строки получаем разрешающий элемент.

Б.П.	С			b	Ө
x₁	x₂	x₃	x₄
x₃
x₄
∆к		-18	-12

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

Б.П.	С			b
x₁	x₂	x₃	x₄
x₁
x₄
∆к

Oстальные элементы рассчитываются по методу Жордана –Гаусса.

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

Б.П.	С			b
x₁	x₂	x₃	x₄
x₁
x₄
∆к

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

Получаем, F = 84. Опорное решение Х = ( ; 0; 0; 44) является оптимальным, т.к. для всех векторов условий оценки в задаче на максимум неотрицательны. Однако данное решение не единственное, т.к. вектор x₂, не входящий в базис, имеет нулевую оценку. Этот вектор нужно ввести в базис опорного решения, чтобы получить еще одно оптимальное решение.

Б.П.	С			b	Ө
x₁	x₂	x₃	x₄
x₁
x₄
∆к

Рассчитываем по методу Жордана –Гаусса последнюю симплекс таблицу.

Б.П.	С			b
x₁	x₂	x₃	x₄
x₂
x₄
∆к

Получаем: F = 84; Х = (0; 7; 0; 2).

Ответ: Для того чтобы обеспечить максимальную прибыль 84 тыс. руб., предприятию можно приобрести только 7 шт. мебели вида В.

Рассмотрим решение примеров 4.1. и 4.2. с помощью симплексных таблиц.

Пример 5.2. (решение примера 4.1.)

→ max.

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

Решение.

Таблица 1

Б.П.	С			b	Ө
x₁	x₂	x₃	x₄
x₃
x₄
∆к		-2	-1

Таблица 2

Б.П.	С			b	Ө
x₁	x₂	x₃	x₄
x₃
x₁
∆к

Таблица 3

Б.П.	С			b
x₁	x₂	x₃	x₄
x₂
x₁
∆к

Ответ: F(x) = 640, X = (260, 120, 0, 0), т.е. для получения максимального веса рыб 640 кг, следует заселить 260 рыб вида А и 120 рыб вида В.

Пример 5.3. (решение примера 4.2.)

→ max

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

Решение.

Таблица 1

Б.П.	С					b	Ө
x₁	x₂	x₃	x₄	x₅	x₆
x₄
x₅
x₆
∆к		-9	-10	-16

Таблица 2

Б.П.	С						b	Ө
x₁	x₂	x₃	x₄	x₅	x₆
x₄						-1
x₃
x₆
∆к			-2

Таблица 3

Б.П.	С					b
x₁	x₂	x₃	x₄	x₅	x₆
x₂
x₃
x₆
∆к

ТРАНСПОРТНАЯ ЗАДАЧА

Математическая постановка транспортной задачи состоит в определении оптимального плана перевозок некоторого однородного груза из т пунктов отправления А₁, А₂, …, А_т в п пунктов назначения В₁, В₂, …, В_п. При этом в качестве критерия оптимальности обычно берется либо минимальная стоимость перевозок всего груза, либо минимальное время его доставки. Рассмотрим транспортную задачу, в качестве критерия оптимальности которой взята минимальная стоимость перевозок всего груза.

Обозначим:

c_ij – тарифы перевозки единицы груза из i-го пункта отправления в j-й пункт назначения,

a_i – запасы груза в i-м пункте отправления,

b_j – потребности в грузе в j–м пункте назначения,

x_ij – количество единиц груза, перевозимого из i-го пункта отправления в j-й пункт назначения.

Тогда математическая постановка задачи состоит в определении минимального значения функции: (6.1)

при условиях (6.2)

(6.3)

Всякое неотрицательное решение систем линейных уравнений (6.2) и (6.3), определяемое матрицей Х=(х_ij), называется планом транспортной задачи.

План Х*=(х*ij), при котором функция (6.1) принимает свое минимальное значение, называется оптимальным планом транспортной задачи.

Обычно исходные данные транспортной задачи записывают в виде таблицы.

Для определения опорного плана существует несколько методов: метод северо-западного угла, метод наименьшей стоимости, метод аппроксимации Фогеля и др.

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

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

Метод наименьшей стоимости

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

Метод аппроксимации Фогеля

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

Широко распространенным методом решения транспортных задач является метод потенциалов.

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

Теорема 1. Если опорный план Х=(х_ij) является оптимальным, существует система из (т+п) чисел, называемых потенциалами, U_i, V_j, такая, что:

• U_i+ V_j=С_ij ,для х_ij>0 (базисные переменные);

• U_i+ V_j=С_ij ,для х_ij=0 (свободные переменные).

Не нашли, что искали? Воспользуйтесь поиском по сайту: