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

⇐ ПредыдущаяСтр 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 ед. Р₂. Как следует заселить озеро рыбами, чтобы максимизировать общую массу рыб?

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

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

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

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

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

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	18	15	12	360
II	6	4	8	192
III	5	3	3	180
Цена одного изделия (€)	9	10	16

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

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

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

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

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

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

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

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	Ө
…
…
∆к

где

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

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

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

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

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

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

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

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

Б.П.	С	18	12	0	0	b	Ө
Б.П.	С	x₁	x₂	x₃	x₄	b	Ө
x₃	0	15	10	1	0	70
x₄	0	12	14	0	1	100
∆к		-18	-12	0	0	0

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

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

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

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

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

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

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

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

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

Б.П.	С	18	12	0	0	b	Ө
Б.П.	С	x₁	x₂	x₃	x₄	b	Ө
x₃	0	15	10	1	0	70
x₄	0	12	14	0	1	100
∆к		-18	-12	0	0	0

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

Б.П.	С	18	12	0	0	b
Б.П.	С	x₁	x₂	x₃	x₄	b
x₁	18	1			0
x₄	0	0
∆к		0

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

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

Б.П.	С	18	12	0	0	b
Б.П.	С	x₁	x₂	x₃	x₄	b
x₁	18	1			0
x₄	0	0	6		1	44
∆к		0	0		0	84

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

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

Б.П.	С	18	12	0	0	b	Ө
Б.П.	С	x₁	x₂	x₃	x₄	b	Ө
x₁	18	1			0		7
x₄	0	0	6		1	44
∆к		0	0		0	84

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

Б.П.	С	18	12	0	0	b
Б.П.	С	x₁	x₂	x₃	x₄	b
x₂	12		1		0	7
x₄	0	18	0		1	2
∆к		0	0		0	84

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

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

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

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

→ max.

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

Решение.

Таблица 1

Б.П.	С	2	1	0	0	b	Ө
Б.П.	С	x₁	x₂	x₃	x₄	b	Ө
x₃	0	1	2	1	0	500	500
x₄	0	3	1	0	1	900	300
∆к		-2	-1	0	0	0

Таблица 2

Б.П.	С	2	1	0	0	b	Ө
Б.П.	С	x₁	x₂	x₃	x₄	b	Ө
x₃	0	0		1		200	120
x₁	2	1		0		300	900
∆к		0		0		600

Таблица 3

Б.П.	С	2	1	0	0	b
Б.П.	С	x₁	x₂	x₃	x₄	b
x₂	1	0	1			120
x₁	2	1	0			260
∆к		0	0			640

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

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

→ max

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

Решение.

Таблица 1

Б.П.	С	9	10	16	0	0	0	b	Ө
Б.П.	С	x₁	x₂	x₃	x₄	x₅	x₆	b	Ө
x₄	0	6	5	4	1	0	0	120	30
x₅	0	3	2	4	0	1	0	96	24
x₆	0	5	3	3	0	0	1	180	60
∆к		-9	-10	-16	0	0	0

Таблица 2

Б.П.	С	9	10	16	0	0	0	b	Ө
Б.П.	С	x₁	x₂	x₃	x₄	x₅	x₆	b	Ө
x₄	0	3	3	0	1	-1	0	24	8
x₃	16			1	0		0	24	48
x₆	0			0	0		1	108	72
∆к		3	-2	0	0	4	0

Таблица 3

Б.П.	С	9	10	16	0	0	0	b
Б.П.	С	x₁	x₂	x₃	x₄	x₅	x₆	b
x₂	10	1	1	0			0	8
x₃	16		0	1			0	20
x₆	0		0	0			1	96
∆к		5	0	0			0	400

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

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

Обозначим:

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 (свободные переменные).

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

• для каждой занятой клетки сумма потенциалов равна стоимости перевозки единицы груза, стоящей в этой клетке:

U_i + V_j =С _ij

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

U_i + V_j £ С _ij

Теорема 2. Любая закрытая транспортная задача имеет решение, которое достигается за конечное число шагов метода потенциалов.

Построение цикла и определение величины перераспределения груза.

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

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

• в каждой вершине цикла сходятся ровно два ребра – одно по строке, другое по столбцу.

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

Приведем примеры некоторых циклов.

Теорема 3. В таблице перевозок для каждой свободной клетки существует один цикл пересчета.

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

1. Поставим в соответствие каждой станции А _i потенциал и _i, а каждой станции В _j потенциал v_j. Для этого для каждой заполненной клетки х _ij ≠0 составим уравнение и _i + v_j =с _ij . Придадим и₁ =1 (можно любое другое значение) и найдем все остальные потенциалы.

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

3. Цикл пересчета начинается в свободной клетке, где ставим знак плюс, а остальные клетки заняты. Знаки в этих клетках чередуются. Выберем наименьшую из перевозок, стоящих в клетках со знаком минус. Тогда данную перевозку прибавляем к перевозкам со знаком плюс и вычитаем из перевозок со знаком минус. Получим новое оптимальное решение. Проверим его на оптимальность.

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

Пример 7.1. Четыре предприятия данного экономического района для производства продукции использует три вида сырья. Потребности в сырье каждого из предприятий соответственно равны 120, 50, 190 и 110 ед. Сырье сосредоточено в трех местах его получения, а запасы соответственно равны 160, 140, 170 ед. На каждое из предприятий сырье может завозиться из любого пункта его получения. Тарифы перевозок являются известными величинами и задаются матрицей .

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

Решение:

	B₁	B₂	B₃	B₄
A₁	7	8	1	2	160
A₂	4	5	9	8	140
A₃	9	2	3	6	170
	120	50	190	110	470

задача закрытого типа.

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

	B₁	B₂	B₃	B₄
A₁	7 120	8 40	1	2	160
A₂	4	5 10	9 130	8	140
A₃	9	2	3 60	6 110	170
	120	50	190	110	470

S₁=120·7+40·8+10·5+130·9+60·3+110·6=3120

Составим первый план методом минимальной стоимости. Будем заполнять клетки с минимальными тарифами.

	B₁	B₂	B₃	B₄
A₁	7	8	1 160	2	160
A₂	4 120	5	9	8 20	140
A₃	9	2 50	3 30	6 90	170
	120	50	190	110	470

S₂=160·1+120·4+20·8+50·2+30·3+90·6=1530

Стоимость при таком плане перевозок почти в два раза меньше. Начнем решение задачи с этого плана. Проверим его на оптимальность. Введем потенциалы α_i – соответственно отправления, β_j – соответственно назначения. По занятым клеткам составляем систему уравнений α_i + β_j=c_ij:

Для свободных клеток таблицы проверяем критерий оптимальности

Будем составлять разности

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