Тема № 3. Симплексный метод.

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

Содержание основных понятий темы

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

Идея последовательного улучшения решения легла в основу уни­версального метода решения задач линейного программирования -­ симплексного метода.

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

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

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

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

3. В данной или полученной после выполнения п. 2 системе m уравнений с n переменными (т < n) m переменных принять за основные. Основными могут быть любые m переменных, коэффициенты при которых образуют отличный от нуля определитель. Проще всего в качестве основных взять добавочные переменные (в этом случае от­падает необходимость вычислять определитель, который заведомо от­личен от нуля, так как каждая добавочная переменная входит только в одно из уравнений системы ограничений).

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

Если найденное базисное решение окажется допустимым, то пере­ходят к п. 5; если же оно окажется недопустимым, то предварительно выполняют п. 4.

4. От полученного недопустимого базисного решения перейти к допустимому базисному решению или установить, что система ог­раничений данной задачи противоречива.

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

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

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

7. Чтобы решить, какую из основных переменных следует переве­сти в неосновные, найти абсолютные величины отношений свобод­ных членов уравнений к коэффициентам при переменной, переводимой в основные, причем только из тех уравнений, в которых эти коэффи­циенты отрицательны. Для уравнений, в которых указанные коэффи­циенты положительны или равны нулю (переменная, переводимая в основные, в них отсутствует), эти отношения считают равными ∞. Из найденных отношений выбрать наименьшее и тем самым решить, какая из основных переменных перейдет в неосновные. Соответствую­щее уравнение выделить.

8. Выразить новые основные переменные и линейную форму через неосновные переменные (это начать делать с выделенного урав­нения).

9. Повторять п. 6-8 до тех пор, пока не будет достигнут кри­терий оптимальности (см. п. 5). После этого выписать компоненты оптимального решения и найти оптимум линейной формы.

10. Если допустимое базисное решение дает оптимум линейной формы (критерий оптимальности выполнен), а в выражении линейной­ формы через неосновные переменные отсутствует хотя бы одна из них, то полученное оптимальное решение не единственное.

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

Задача 1 (о планировании производства).

Для изготовления двух видов продукции P₁ и P₂ используют четыре вида ресурсов S₁, S₂, S₃, S₄. Запасы ресурсов, число единиц ресурсов, затрачиваемых на изготовление единицы продукции, приведены в таблице (цифры условные).

Вид ресурса	Запас ресурса	Число ед. ресурсов, затрачиваемых на изготовление ед. продукции
		P1	P2
S1	18	1	3
S2	16	2	1
S3	5	-	1
S4	21	3	-

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

Решение.

Составим экономико–математическую модель задачи. Обозначим x₁ и x₂ – число единиц продукции соответственно P₁ и P₂, запланированных к производству. Для их изготовления потребуется (1x₁+3x₂)единиц ресурса S₁, (2x₁+1x₂) единиц ресурса S₂, 1x₂ единиц ресурса S₃ и 3x₁ единиц ресурса S₄. Так как потребление ресурсов S₁, S₂, S₃, S₄ не должно превышать их запасов, соответственно 18, 16, 5 и 21 ед., то связь между потреблением ресурсов и их запасами выразится системой неравенств

По смыслу задачи переменные . Суммарная прибыль F составит 2x₁ руб. от реализации продукции P₁ и 3x₂ руб. – от реализации продукции P₂, т.е. .

Итак, экономико–математическая модель задачи: найти такой план выпуска продукции X=(x₁,x₂), удовлетворяющий системе ограничений и дополнительным условиям, при котором функция F принимает максимальное значение. Решим задачу симплексным методом.

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

Введем в каждое уравнение системы по одной из дополнительных неотрицательных переменных x₃, x₄, x₅, x₆ со знаком «плюс», так как все неравенства системы ог­раничений вида « ». Получим следующую систему огра­ничений:

Любое решение этой системы будет состоять из четы­рех основных и двух неосновных переменных. В качестве основных переменных на первом шаге берем дополнитель­ные переменные x₃, x₄, x₅, x₆ (определитель из коэффици­ентов при них (базисный минор) будет отличен от нуля)

1 шаг.

Основные переменные: x₃, x₄, x₅, x_6.

Несновные переменные: x₁,x₂.

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

Полагая неосновные переменные равными нулю, т.е. , получим первое базисное решение х₁= (0; 0;18; 16; 5; 21), которое является допустимым. При этом От этого первоначального решения нужно перейти к другому, при котором значение линейной функций F увеличится. Это можно до­стичь изменением базисного решения, т.е. - переводом од­ной из неосновных переменных в основные, а одной из ос­новных в неосновные. Геометрически это означает переход к соседней вершине многоугольника допустимых решений.

Увеличить значение линейной функции F можно пере­водам в основные пере­менную, которая входит в выражение линейной функции с положительным коэффициентом, например х₂ (или х₁). На её место из основных в неосновные переводится перемен­ная, которая первой обратится в нуль при росте х₂. Урав­нение, из которого находится эта переменная, называется разрешающим.

Разрешающее уравнение, а значит переменная, переводимая из основных в неосновные, находится по минимуму оценочных отношений, каждое из которых определяет ог­paничение данного уравнения по росту переменной х₂:

Эти отношения определяются отнощением свободных членов уравнений к коэффициентам при переводимой в основные переменной х₂ при условии, что эти числа имеют разные знаки. В случае одинаковых знаков или отсутствия в уравнении переменной, переводимой в основные, соот­ветствующее оценочное отношение считается равным ∞.

При х₂= 5 переменная x₅ обращается в нуль и переходит в неосновные, т.е. разрешающее уравнение тре­тье.

2 шаг.

Основные переменные: x₂, x₃, x₄, x_6.

Heoсновныe переменные: x₁, x₅.

Выразим новые основные переменные через новые неосновные­, начиная с разрешающего уравнения (его исполь­зуем при записи выражения для x₂):

или

Второе базисное решение x₂ = (0; 5; 3; 11; 0; 2) соответ­ствует вершине (0; 5) многоугольника допустимых решений.

Выразив линейную функцию через неосновные переменные­, получим

Значение линейной функции F₂=F(x₂)= 15.

Переводим в основные переменную x₁ которая входит в выражение линейной функции с положительным коэф­фициентом. При этом

x₁= min{∞;3/1;11/2;21/3}=3.

Второе уравнение является разрешающим, переменная x₃ переходит в неосновные.

3 шаг.

Основные переменные: x₁, x₂, x₄, x_6.

Неосновные переменные: x₃, x_5.

Выражаем новые основные переменные и линейную функцию через новые неосновные, начиная с разрешаю­щего уравнения. После преобразований получаем

Третье базисное решение x₃= (3; 5; 0; 5; 0; 12) соответ­ствует вершине (3, 5) многоугольника допустимых решений.

Fз = F(x₃) = 21.

4 шаг.

Основные переменные: x₁, x₂, x₅, x_6.

Неосновные переменные: x₃, x_4.

После преобразований получаем

Четвертое базисное решение x₄ = (6; 4; 0; 0; 1; 3) соответ­ствует вершине (6; 4) многоугольника допустимых решений.

F4=F (x₄) = 24.

Решение x₄ является оптимальным (обозначаем Х*), так как выполнен критерий оптимальности решения зада­чи на отыскание максимума линейной функции - отсут­ствие в выражении линейной функции положительных ко­эффициецтов при неосновных переменных.

Итак, прибыль предприятия принимает максимальное значение 24 руб. при реализации 6 ед. продукции P₁(x₁=6) и 4 ед. продукции P₂(x₂=4). Дополнительные переменные x₃, x₄, x₅, x_6. показывают разницу между запасами ресурсов каждого вида и их потреблением, т. е. остатки ресурсов.

При оптимальном плане производства x₃= x₄= О остатки ресурсов S₁ и S₂ равны нулю, а остатки ресурсов S₃ и S₄ равны соответственно 1 и 3 ед.

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

Самостоятельно решите следующие задачи:

3.1. Решить задачи симплексным методом и дать, если это возможно, геометрическую интерпретацию:

1) 2)

при условиях при условиях

и - неотрицательные и - неотрицательные

и целые. и целые.

3) 4)

при условиях при условиях

и - неотрицательные и - неотрицательные

и целые. и целые.

5) 6)

7) 8)

3.2. Решить задачи симплексным методом:

1) 2)

3) 4)

3.3. Для выпуска изделий двух типов (А и В) на заводе используется сырье четырех видов (I, II, III и IV). Расход сырья каждого вида на изготовление еди­ницы продукции задан таблицей.

Изделие	Сырьё
	I	II	III	IV
А	2	1	2	1
В	3	1	1	0

Запасы сырья составляют, I вида - 21 ед., II вида –8 ед., III вида – 12 ед.,

IV вида – 5 ед. Выпуск одного изделия типа А приносит 3 ден. ед. прибыли, од­ного изделия типа. В –2 ден. ед. Составить план производства, обеспечивающий наибольшую прибыль.

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

Виды Типы Станков дет.	Время обработки одной детали (ч)		Время работа станка в тече­нии цикла производства (ч)
	I	ΙΙ
1 - й станок	4	2	16
2 – й станок	1 3	6	30
3 – й станок	2	0	12
Прибыль от реализации одной детали (руб.)	3	4

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

3.5. На четырех станках (I,II, III и IV) обрабатываются два вида деталей (А и В), причем каждая деталь проходит обработку на всех станках. Известны время обработки деталей на каждом станке, время работы станков в течение одного цик­ла производства и прибыль, получаемая от выпуска одной детали каждого вида. Эти данные приведены в таблице. Составить план производства, обеспечиваю­щий наибольшую прибыль при условии, что количество деталей вида В не долж­но быть меньше количества деталей вида А.

Станки	Время обработки детали		Время работы станка за цикл производства, ч.
	А	В
I	1	2	16
II	2	3	26
III	1	1	10
IV	3	1	24
Прибыль на одну деталь, руб.	4	1

3.6. Совхоз должен по плану произвести не менее 120 усл.ед. пшениuы, 70 усл. ед. кукурузы и 15 усл. ед. гречихи. Для этого можно использовать два массива сельскохозяйственных угодий в 1000 и 800 га. В таблице приведены урожайность каждой культуры на различных участках (верхний показатель) и затраты на 1 га сельскохозяйственных угодий при производстве различных культур (нижний показатель). Требуется составить такой план засева, чтобы валовой сбор зерна удовлетворял плановому заданию, а стоимость затрат была наименьшей.

Поле	Размер поля	Культуры
		пшеница	Кукуруза	гречиха
I	1000	10 7	20 10	6 15
II	800	12 8	24 12	5 20
План по культурам		120	70	15

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

Вид пряжи	Запасы пряжи	Расход пряжи в единицу времени на фабриках
		1	2	3	4
I II	6000 4000	4 1	9 1	7 3	10 4
Производительность фабрик		12	20	18	40

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

3.8. Для производства продукции 2-х видов А и В используется материал трех сортов. Данные о затратах сырья на производство единицы продукции, запасах сырья и прибыли от реализаций единицы продукции приведены в таб­лице.

Сорт сырья Вид продукции	Ι	ΙΙ	ΙΙΙ	Прибыль
А	4	8	5	4
В	I	7	9	6
Запасы сырья	196	552	567

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

3.9. Для производства двух видов продукции (А н В) предприятие должно ис­пользовать оборудование трех видов (I, II, III), имеющееся в количествах соот­ветственно 8, 6, 9 ед. По техническим условиям для производства 1 шт. продукции А требуется 2 ед. оборудования I вида, l eд. оборудования - II вида и 3 ед. оборудования - III вида, а для производства 1 шт. продукции B- 2, 2 и 0 ед. соответствующих видов оборудования. Известно, что от реализации 1 шт. продук­ции А предприятие получит 1 ден. ед. прибыли, l шт. продукции В - 3 ден. ед. Сколько единиц продукции каждого вида должно выпустить предприятие, что­бы получить наибольшую прибыль?

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

Тип оборудования	Затраты времени на обраб. одного изделия (ст.\ч.)			Общий фонд рабочего времени (ч)
	А	В	С
Фрезерное	2	4	5	120
Токарное	1	8	6	280
Сварочное	7	4	5	240
Шлифовальное	4	6	7	360
Прибыль	10	14	12

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