Решение задач симплекс методом примеры для чайников – Математическое программирование. Графический и симплекс метод. Примеры решения задач

Решение симплекс методом задачи ЛП: пример и алгоритм

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

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

Перед тем, как перейти к алгоритму симплекс метода, несколько определений.

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

Пусть имеется система m ограничений с n переменными (m n).

Допустимым базисным решением является решение, содержащее m неотрицательных основных (базисных) переменных и n — m неосновных. (небазисных, или свободных) переменных. Неосновные переменные в базисном решении равны нулю, основные же переменные, как правило, отличны от нуля, то есть являются положительными числами.

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

неосновными (или свободными).

Алгоритм симплекс метода

• Шаг 1. Привести задачу линейного программирования к канонической форме. Для этого перенести свободные члены в правые части (если среди этих свободных членов окажутся отрицательные, то соответствующее уравнение или неравенство умножить на — 1) и в каждое ограничение ввести дополнительные переменные (со знаком «плюс», если в исходном неравенстве знак «меньше или равно», и со знаком «минус», если «больше или равно»).
• Шаг 2. Если в полученной системе m уравнений, то m переменных принять за основные, выразить основные переменные через неосновные и найти соответствующее базисное решение. Если найденное базисное решение окажется допустимым, перейти к допустимому базисному решению.
• Шаг 3. Выразить функцию цели через неосновные переменные допустимого базисного решения. Если отыскивается максимум (минимум) линейной формы и в её выражении нет неосновных переменных с отрицательными (положительными) коэффициентами, то критерий оптимальности выполнен и полученное базисное решение является оптимальным — решение окончено. Если при нахождении максимума (минимума) линейной формы в её выражении имеется одна или несколько неосновных переменных с отрицательными (положительными) коэффициентами, перейти к новому базисному решению.
• Шаг 4. Из неосновных переменных, входящих в линейную форму с отрицательными (положительными) коэффициентами, выбирают ту, которой соответствует наибольший (по модулю) коэффициент, и переводят её в основные. Переход к шагу 2.

Важные условия

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

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

Будет нелишним открыть в новом окне пособие Действия с дробями: их, дробей в задачах на симплекс-метод, мягко говоря, хватает.

Пример. Найти максимум функции при ограничениях

Решение.

Вводим добавочные неотрицательные переменные и сводим данную систему неравенств к эквивалентной ей системе уравнений

.

Это было сделано с соблюдением следующего правила: если в первоначальном ограничении знак «меньше или равно», то добавочную переменную нужно прибавлять, а если «больше или равно», то добавочную переменную нужно отнимать.

Введённые добавочные переменные принимаем за основные (базисные). Тогда и — неосновные (свободные) переменные.

Выразив основные (базисные) переменные через неосновные (свободные), получим

Функцию цели также выразим через неосновные (свободные) переменные:

Из коэффициентов при переменных (неизвестных) построим первую симплексную таблицу.

Таблица 1
Базисные неизвестные	Свободные члены	Свободные неизвестные		Вспомогательные коэффициенты
		X1	X2
X3	-2	1	-2
X4	-4	-1	-1
X5	2	1	-1
X6	6	0	1
F	0	-1	-2

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

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

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

Для перехода к следующей таблице найдём наибольшее (по модулю) из чисел и . Это число 2. Поэтому ведущий столбец — тот столбец, в котором записано

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

Итак,

.

Поэтому ведущая строка — та, в которой записано

Ведущим элементом, таким образом, является -2.

Составляем вторую симплексную таблицу.

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

Заполняем первую строку. Для этого все числа, стоящие в ведущей строке таблицы 1, делим на ведущий элемент и записываем в соответствующий столбец первой строки таблицы 2, кроме числа, стоящего в ведущем столбце, куда записывается величина, обратная ведущему элементу (то есть, единица, делённая на ведущий элемент).

Заполняем столбец вспомогательных коэффициентов. Для этого числа ведущего столбца таблицы 1, кроме ведущего элемента, записываем с противоположными знаками в графу вспомогательных коэффициентов таблицы 2.

Таблица 2
Базисные неизвестные	Свободные члены	Свободные неизвестные		Вспомогательные коэффициенты
		X1	X3
X2	1	-1/2	-1/2
X4	-3	-3/2	-1/2	1
X5	3	1/2	-1/2	1
X6	5	1/2	1/2	-1
F	2	-2	-1	2

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

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

Например, для получения свободного члена второй строки число 1 умножаем на 1 и прибавляем из таблицы 1 число -4. Получаем -3. Коэффициент при во второй строке находим так же: . Так как в предыдущей таблице отсутствует столбец с новой свободной переменной , то коэффициент второй строки в столбце новой свободной переменной будет (то есть из таблицы 1 прибавляем 0, так как в таблице 1 столбец с отсутствует).

Так же заполняется и индексная строка:

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

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

Для перехода к следующей симплексной таблице найдём наибольшее (по модулю) из чисел и , то есть, модулей коэффициентов в индексной строке. Это число 2. Поэтому ведущий столбец — тот столбец, в котором записано .

Для поиска ведущей строки найдём минимум отношений свободных членов к элементам ведущей строки. Получаем:

.

Следовательно, ведущая строка — та, в которой записано , а ведущим элементом является -3/2.

Составляем третью симплексную таблицу

Новую базисную переменную записываем первой строкой. В столбец, в котором было , вписываем новую свободную переменную .

Первая строка:

Вспомогательные коэффициенты:

Таблица 3
Базисные неизвестные	Свободные члены	Свободные неизвестные		Вспомогательные коэффициенты
		X4	X3
X1	2	-2/3	1/3
X2	2	-1/3	-1/3	1/2
X5	2	1/3	-2/3	-1/2
X6	4	1/3	1/3	-1/2
F	6	-4/3	-1/3	2

Вычисление остальных строк на примере второй строки:

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

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

Для перехода к четвёртой симплексной таблице найдём наибольшее из чисел и . Это число .

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

Для нахождения ведущей строки найдём минимум модулей отношений свободных членов к элементам ведущего столбца:

.

Поэтому ведущая строка — та, в которой записано , а ведущий элемент 1/3.

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

Первая строка:

Вспомогательные коэффициенты:

.

Таблица 4
Базисные неизвестные	Свободные члены	Свободные неизвестные		Вспомогательные коэффициенты
		X5	X3
X4	6	3	-2
X1	6	2	-1	2/3
X2	4	1	-1	1/3
X6	2	-1	1	-1/3
F	14	4	-3	4/3

Вычисление остальных строк на примере второй строки:

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

Для улучшения плана перейдём к следующей симплексной таблице.

Найдём наибольшее из чисел 4 и . Это число 4. Следовательно, ведущий столбец .

Для нахождения ведущей строки найдём

.

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

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

Для нахождения ведущей строки найдём

.

Следовательно, ключевая строка — та, в которой записано , а ведущий элемент 1.

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

Первая строка:

Вспомогательные коэффициенты:

.

Таблица 5
Базисные неизвестные	Свободные члены	Свободные неизвестные		Вспомогательные коэффициенты
		X5	X6
X3	2	-1	1
X4	10			2
X1	8			1
X2	6			1
F	20	1	3	3

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

Свободные члены:

— во второй строке ;

— в третьей строке ;

— в четвёртой строке .

Индексная строка:

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

Ответ:

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

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

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

Пример. Найти максимум функции при ограничениях

Решение.

Шаг I. Вводим добавочные неотрицательные переменные и сводим данную систему неравенств к эквивалентной ей системе уравнений

.

Введённые добавочные переменные принимаем за основные, так как в этом случае базисное решение системы легко находится. Тогда и — неосновные переменные.

Выразив основные переменные через неосновные, получим

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

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

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

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

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

Шаг II.

Основные переменные , неосновные переменные .

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

Следовательно, имеем новое базисное решение , которое также является недопустимым, а поэтому не оптимальным. Но в нём, как мы и предвидели, только одна переменная отрицательна (а именно ).

От полученного базисного решения необходимо перейти к другому. Рассмотрим уравнение с отрицательным свободным членом, т. е. второе уравнение. Оно показывает, что в основные переменные можно перевести и . Переведём в основные переменные . Найдём наименьшее из абсолютных величин отношений свободных членов системы к коэффициентам при . Имеем . Значит, в неосновные переменные нужно перенести . Так как наименьшее отношение получено из второго уравнения, то его выделяем. В новом базисном решении уже не окажется отрицательных компонент, т. е. оно является допустимым.

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

Шаг III.

Основные переменные: , неосновные переменные: . Выразив основные переменные через неосновные, получим

Новое базисное решение имеет вид . Является ли оно оптимальным, можно установить, если выразить линейную форму через неосновные переменные рассматриваемого базисного решения. Сделав это, получим . Так как мы ищем максимум линейной формы, а нашли лишь одно допустимое решение, то продолжим перебор.

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

В некотором особом случае решение завершается на III шаге: это случай, когда оптимальное решение — не единственное.

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

Шаг IV.

Основные переменные: , неосновные переменные: . Выразив основные переменные через неосновные, получим

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

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

Шаг V.

Основные переменные: , неосновные переменные: . Выразив основные переменные через неосновные, получим

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

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

Начало темы «Линейное программирование»

Продолжение темы «Линейное программирование»

Поделиться с друзьями

function-x.ru

Симплекс-метод, примеры решения задач

Здесь приведено ручное (не апплетом) решение двух задач симплекс-методом (аналогичным решению апплетом) с подробными объяснениями для того, чтобы понять алгоритм решения задач симплекс-методом. Первая задача содержит знаки неравенства только » ≤ » (задача с начальным базисом), вторая может содержить знаки » ≥ «, » ≤ » или » = » (задача с искусственным базисом), они решаются по разному.

 

Симплекс-метод, решение задачи с начальным базисом

1)Симплекс-метод для задачи с начальным базисом (все знаки неравенств-ограничений » ≤ «).

Запишем задачу в канонической форме, т.е. ограничения-неравенства перепишем в виде равенств, добавляя балансовые переменные:

Эта система является системой с базисом (базис s₁, s₂, s₃, каждая из них входит только в одно уравнение системы с коэффициентом 1), x₁ и x₂ — свободные переменные. Задачи, при решении которых применяется симплекс-метод, должны обладать следующими двумя свойствами: -система ограничений должна быть системой уравнений с базисом; -свободные члены всех уравнений в системе должны быть неотрицательны.

Полученная система — система с базисом и ее свободные члены неотрицательны, поэтому можно применить симплекс-метод. Составим первую симплекс-таблицу (Итерация 0) для решения задачи на симплекс-метод, т.е. таблицу коэффициентов целевой функции и системы уравнений при соответствующих переменных. Здесь «БП» означает столбец базисных переменных, «Решение» — столбец правых частей уравнений системы. Решение не является оптимальным, т.к. в z – строке есть отрицательные коэффициенты.

симплекс-метод итерация 0

БП	x1	x2	s1	s2	s3	Решение	Отношение
z	-4	-6	0	0	0	0	—
s1	2	1	1	0	0	64	64/1=64
s2	1	3	0	1	0	72	72/3=24
s3	0	1	0	0	1	20	20/1=20

Для улучшения решения перейдем к следующей итерации симплекс-метода, получим следующую симплекс-таблицу. Для этого надо выбрать разрешающий столбец, т.е. переменную, которая войдет в базис на следующей итерации симплекс-метода. Он выбирается по наибольшему по модулю отрицательному коэффициенту в z-строке (в задаче на максимум) – в начальной итерации симплекс-метода это столбец x₂ (коэффициент -6).

Затем выбирается разрешающая строка, т.е. переменная, которая выйдет из базиса на следующей итерации симплекс-метода. Она выбирается по наименьшему отношению столбца «Решение» к соответствующим положительным элементам разрешающего столбца (столбец «Отношение») – в начальной итерации это строка s₃ (коэффициент 20).

Разрешающий элемент находится на пересечении разрешающего столбца и разрешающей строки, его ячейка выделена цветом, он равен 1. Следовательно, на следующей итерации симплекс-метода переменная x₂ заменит в базисе s₁. Заметим, что в z-строке отношение не ищется, там ставится прочерк » — «. В случае если есть одинаковые минимальные отношения, то выбирается любое из них. Если в разрешающем столбце все коэффициенты меньше или равны 0, то решение задачи бесконечно.

Заполним следующую таблицу «Итерация 1». Её мы получим из таблицы «Итерация 0». Цель дальнейших преобразований — превратить разрешающий столбец х₂ в единичный (с единицей вместо разрешающего элемента и нулями вместо остальных элементов).

1)Вычисление строки х₂ таблицы «Итерация 1». Сначала делим все члены разрешающей строки s₃ таблицы «Итерация 0» на разрешающий элемент (он равен 1 в данном случае) этой таблицы, получим строку x₂ в таблице «Итерации 1». Т.к. разрешающий элемент в данном случае равен 1, то строка s₃ таблицы «Итерация 0» будет совпадать со строкой х₂ таблицы «Итерация 1». Строку x₂ таблицы «Итерации 1» мы получили 0 1 0 0 1 20, остальные строки таблицы «Итерация 1» будут получены из этой строки и строк таблицы «Итерация 0» следующим образом:

2) Вычисление z-строки таблицы «Итерация 1». На месте -6 в первой строке (z-строке) в столбце х₂ таблицы «Итерация 0» должен быть 0 в первой строке таблицы «Итерация 1». Для этого все элементы строки х₂ таблицы «Итерация 1» 0 1 0 0 1 20 умножим на 6, получим 0 6 0 0 6 120 и сложим эту строку с первой строкой (z — строкой) таблицы «Итерация 0» -4 -6 0 0 0 0, получим -4 0 0 0 6 120. В столбце x₂ появился ноль 0, цель достигнута. Элементы разрешающего столбца х₂ выделены красным цветом.

3) Вычисление строки s₁ таблицы «Итерация 1». На месте 1 в s₁ строке таблицы «Итерация 0» должен быть 0 в таблице «Итерация 1». Для этого все элементы строки х₂ таблицы «Итерация 1» 0 1 0 0 1 20 умножим на -1, получим 0 -1 0 0 -1 -20 и сложим эту строку с s₁ — строкой таблицы «Итерация 0» 2 1 1 0 0 64, получим строку 2 0 1 0 -1 44. В столбце х₂ получен необходимый 0.

4) Вычисление строки s₂ таблицы «Итерация 1». На месте 3 в s₂ строке таблицы «Итерация 0» должен быть 0 в таблице «Итерация 1». Для этого все элементы строки х₂ таблицы «Итерация 1» 0 1 0 0 1 20 умножим на -3, получим 0 -3 0 0 -3 -60 и сложим эту строку с s₁ — строкой таблицы «Итерация 0» 1 3 0 1 0 72, получим строку 1 0 0 1 -3 12. В столбце х₂ получен нужный 0. Столбец х₂ в таблице «Итерация 1» стал единичным, он содержит одну 1 и остальные 0.

Строки таблицы «Итерация 1» получаем по следующему правилу:

Новая строка = Старая строка – (Коэффициент разрешающего столбца старой строки)*(Новая разрешающая строка).

Например для z-строки имеем:

Старая z-строка                                              (-4   -6 0 0 0 0) -(-6)*Новая разрешающая строка                 -(0 -6 0 0 -6 -120) =Новая z-строка (-4 0 0 0 6 120).

Для следующих таблиц пересчет элементов таблицы делается аналогично, поэтому мы его опускаем.

симплекс-метод итерация 1

БП	x1	x2	s1	s2	s3	Решение	Отношение
z	-4	0	0	0	6	120	—
s1	2	0	1	0	-1	44	44/2=22
s2	1	0	0	1	-3	12	12/1=12
x2	0	1	0	0	1	20	—

Разрешающий столбец х₁, разрешающая строка s₂, s₂ выходит из базиса, х₁ входит в базис. Совершенно аналогично получим остальные симплекс-таблицы, пока не будет получена таблица со всеми положительными коэффициентами в z-строке. Это признак оптимальной таблицы.

симплекс-метод итерация 2

БП	x1	x2	s1	s2	s3	Решение	Отношение
z	0	0	0	4	-6	168	—
s1	0	0	1	-2	5	20	20/5=4
x1	1	0	0	1	-3	12	—
x2	0	1	0	0	1	20	20/1=20

Разрешающий столбец s₃, разрешающая строка s₁, s₁ выходит из базиса, s₃ входит в базис.

симплекс-метод итерация 3

БП	x1	x2	s1	s2	s3	Решение	Отношение
z	0	0	6/5	8/5	0	192	—
s3	0	0	1/5	-2/5	1	4	—
x1	1	0	3/5	-1/5	0	24	—
x2	0	1	-1/5	2/5	0	16	—

В z-строке все коэффициенты неотрицательны, следовательно, получено оптимальное решение x₁ = 24, x₂ = 16, z_max = 192.

studfiles.net

Симплекс метод онлайн

Данный онлайн калькулятор решает задачу линейного программирования симплекс методом. Дается подробное решение с пояснениями. Для решения задачи линейного программирования задайте количество ограничений и количество переменных. Затем введите данные в ячейки и нажимайте на кнопку «Вычислить». Теоретическую часть смотрите в статье: Решение задачи линейного программирования. Симплекс метод.

Количество ограничений: m=	1234567891011121314151617181920
Количество переменных : n=	1234567891011121314151617181920

 

Очистить все ячейки?

Инструкция ввода данных. Числа вводятся в виде целых чисел (примеры: 487, 5, -7623 и т.д.), десятичных чисел (напр. 67., 102.54 и т.д.) или дробей. Дробь нужно набирать в виде a/b, где a и b (b>0) целые или десятичные числа. Примеры 45/5, 6.6/76.4, -7/6.7 и т.д.

Симплекс метод

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

Примеры решения ЗЛП симплекс методом

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

Р е ш е н и е. Матрица коэффициентов системы уравнений имеет вид:

Правая часть ограничений системы уравнений имеет вид:

Составляем симплексную таблицу. В столбец x₀ записывается правая часть ограничений. С правой стороны записывается матрица коэффициентов A. Последняя строка — это целевая функция, умноженная на −1. Последние три векторы столбцы обазуют базис в трехмерном пространствое. Следовательно базисные переменные , а свободные переменные :

Запишем текущий опорный план:

Данный опорный план не является оптимальным, так как в последней строке есть отрицательные элементы. Самый большой по модулю отрицательный элемент (-3), следовательно в базис входит вектор x₂. Определяем, какой вектор выходит из базиса. Для этого вычисляем при . min(40:6, 28:2)=20/3 соответствует строке 1. Из базиса выходит вектор x₃. Сделаем исключение Гаусса для столбца x₂, учитывая, что ведущий элемент соответствует строке 1. Обнулим все элементы этого столбца, кроме ведущего элемента. Для этого сложим строки строки 2, 3, 4 со строкой 1, умноженной на -1/3, 1/6, 1/2, соответственно. Далее делим строку с ведущим элементом на ведущий элемент.

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

Запишем текущий опорный план:

Данный опорный план не является оптимальным, так как в последней строке есть отрицательный элемент (-3), следовательно в базис входит вектор x₁. Определяем, какой вектор выходит из базиса. Для этого вычисляем при . min(44/3:11/3, 62/3:5/3)=4 соответствует строке 2. Из базиса выходит вектор x₄. Сделаем исключение Гаусса для столбца x₁, учитывая, что ведущий элемент соответствует строке 2. Обнулим все элементы этого столбца, кроме ведущего элемента. Для этого сложим строки строки 1, 3, 4 со строкой 2, умноженной на 1/11, -5/11, 9/11, соответственно. Далее делим строку с ведущим элементом на ведущий элемент.

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

Запишем текущий опорный план:

Текущий опорный план является оптимальным, так как в строках 4 под переменными нет отрицательных элементов.

Решение можно записать так: .

Значение целевой функции в данной точке: F(X)=.

Пример 2. Найти максимум функции

при условиях

 

Р е ш е н и е. Матрица коэффициентов системы уравнений имеет вид:

Правая часть ограничений системы уравнений имеет вид:

Составляем симплексную таблицу. В столбец x₀ записывается правая часть ограничений. С правой стороны записывается матрица коэффициентов A. Последняя строка — это целевая функция, умноженная на −1:

Базисные векторы x₄, x₃, следовательно, все элементы в столбцах x₄, x₃, ниже горизонтальной линии должны быть нулевыми.

Обнулим все элементы столбца x₄, кроме ведущего элемента. Для этого сложим строку 3 со строкой 1, умноженной на 4. Обнулим все элементы столбца x₃, кроме ведущего элемента. Для этого сложим строку 3 со строкой 2, умноженной на 1.

Симплекс таблица примет вид:

 

Запишем текущий опорный план:

Данный опорный план не является оптимальным, так как в последней строке есть отрицательный элемент (-11), следовательно в базис входит вектор x₂. Определяем, какой вектор выходит из базиса. Для этого вычисляем при . Все следовательно целевая функция неограничена сверху. Т.е. задача линейного программирования неразрешима.

Примеры решения ЗЛП методом искусственного базиса

Пример 1. Найти максимум функции

при условиях

 

Р е ш е н и е. Так как количество базисных векторов должен быть 3, то добавляем искусственное переменное, а в целевую функцию добавляем это переменное, умноженное на −M, где M, очень большое число:

Матрица коэффициентов системы уравнений имеет вид:

Правая часть ограничений системы уравнений имеет вид:

Составляем симплексную таблицу. В столбец x₀ записывается правая часть ограничений. С правой стороны записывается матрица коэффициентов A. Последние две строки − это целевая функция, умноженная на −1 и разделенная на две части. Последняя строка − строка с исскуственными переменными:

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

Обнулим все элементы столбца кроме ведущего элемента. Для этого сложим строку 5 со строкой 3, умноженной на -1.

Симплекс таблица примет вид:

 

Запишем текущий опорный план:

Данный опорный план не является оптимальным, так как в последней строке есть отрицательные элементы. Самый большой по модулю отрицательный элемент (-5), следовательно в базис входит вектор Определяем, какой вектор выходит из базиса. Для этого вычисляем при соответствует строке 3. Из базиса выходит вектор Сделаем исключение Гаусса для столбца учитывая, что ведущий элемент соответствует строке 3. Обнулим все элементы этого столбца, кроме ведущего элемента. Для этого сложим строки строку 5 со строкой 3, умноженной на 1. Далее делим строку с ведущим элементом на ведущий элемент.

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

 

Запишем текущий опорный план:

Данный опорный план не является оптимальным, так как в последней строке есть отрицательные элементы. Самый большой по модулю отрицательный элемент (-3), следовательно в базис входит вектор Определяем, какой вектор выходит из базиса. Для этого вычисляем при соответствует строке 1. Из базиса выходит вектор x₂. Сделаем исключение Гаусса для столбца x₁, учитывая, что ведущий элемент соответствует строке 1. Обнулим все элементы этого столбца, кроме ведущего элемента. Для этого сложим строки строки 2, 3, 4 со строкой 1, умноженной на 3/2, -1/10, 3/2, соответственно. Далее делим строку с ведущим элементом на ведущий элемент.

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

 

Запишем текущий опорный план:

Данный опорный план не является оптимальным, так как в последней строке есть отрицательные элементы. Самый большой по модулю отрицательный элемент (-13/2), следовательно в базис входит вектор x₃. Определяем, какой вектор выходит из базиса. Для этого вычисляем при соответствует строке 3. Из базиса выходит вектор x₅. Сделаем исключение Гаусса для столбца x₃, учитывая, что ведущий элемент соответствует строке 3. Обнулим все элементы этого столбца, кроме ведущего элемента. Для этого сложим строки строки 1, 2, 4 со строкой 3, умноженной на 5/3, 25/9, 65/9, соответственно. Далее делим строку с ведущим элементом на ведущий элемент.

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

 

Запишем текущий опорный план:

Текущий опорный план является оптимальным, так как в строках 4−5 под переменными нет отрицательных элементов.

Решение исходной задачи можно записать так:

.

Значение целевой функции в данной точке:

.

Пример 2. Найти оптимальный план задачи линейного программирования:

 

Р е ш е н и е. Так как количество базисных векторов должен быть 3, то добавляем искусственные переменные, а в целевую функцию добавляем эти переменные, умноженные на −M, где M, очень большое число:

Матрица коэффициентов системы уравнений имеет вид:

Правая часть ограничений системы уравнений имеет вид:

Составляем симплексную таблицу. В столбец x₀ записывается правая часть ограничений. С правой стороны записывается матрица коэффициентов A. Последние две строки − это целевая функция, умноженная на −1 и разделенная на две части. Последняя строка − строка с исскуственными переменными:

Базисные векторы x₄, x₅, x₆, следовательно, все элементы в столбцах x₄, x₅, x₆, ниже горизонтальной линии должны быть нулевыми.

Обнулим все элементы столбца x₄, кроме ведущего элемента. Для этого сложим строку 4 со строкой 1, умноженной на -1. Обнулим все элементы столбца x₅, кроме ведущего элемента. Для этого сложим строку 5 со строкой 2, умноженной на -1. Обнулим все элементы столбца x₆, кроме ведущего элемента. Для этого сложим строку 5 со строкой 3, умноженной на -1.

Симплекс таблица примет вид:

 

Запишем текущий опорный план:

В строке 5 элементы, соответствующие переменным x₁, x₂, x₃, x₄, x₅, x₆ неотрицательны, а число находящийся в пересечении данной строки и столбца x₀ отрицательнo. Тогда исходная задача не имеет опорного плана. Следовательно она неразрешима.

matworld.ru

Пример решения задачи симплекс М-методом

Условие задачи

Найти оптимальные величины производства продукции видов А, Б и В. Затраты сырья на единицу продукции: А – 5, Б – 2, В – 4. Объем сырья – 2000 единиц. Затраты оборудования на единицу продукции: А – 4, Б – 5, В – 4. Объем оборудования – 1000 единиц. Прибыль от реализации единицы продукции: А – 10, Б – 8, В – 12. Критерий – максимум прибыли предприятия. Производство продукции А должно быть не менее 100 ед. Производство продукции Б должно быть не менее 50 ед.

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

1) Определение оптимального плана производства

Пусть x₁, x₂, x₃ — количество произведенной продукции вида А, Б, В, соответственно. Тогда математическая модель задачи имеет вид:

F = 10·x₁ + 8·x₂ + 12·x₃ –>max

Решаем симплекс методом.

Вводим дополнительные переменные x₄ ≥ 0, x₅ ≥ 0, x₆ ≥ 0, x₇ ≥ 0, чтобы неравенства преобразовать в равенства.

Чтобы выбрать начальный базис, вводим искусственные переменные x₈ ≥ 0, x₉ ≥ 0 и очень большое число M (M –> ∞). Решаем М методом.

F = 10·x₁ + 8·x₂ + 12·x₃ + 0·x₄ + 0·x₅ + 0·x₆ + 0·x₇– M·x₈– M·x₉ –>max

В качестве базиса возьмем x₄ = 2000; x₅ = 1000; x₈ = 100; x₉ = 50.

Данные заносим в симплекс таблицу

Симплекс таблица № 1

Целевая функция:

0 · 2000 + 0 · 1000 + (– M) · 100 + (– M) · 50 = – 150M

Вычисляем оценки по формуле:

Δ₁ = 0 · 5 + 0 · 4 + (– M) · 1 + (– M) · 0 – 10 = – M – 10
Δ₂ = 0 · 2 + 0 · 5 + (– M) · 0 + (– M) · 1 – 8 = – M – 8
Δ₃ = 0 · 4 + 0 · 4 + (– M) · 0 + (– M) · 0 – 12 = – 12
Δ₄ = 0 · 1 + 0 · 0 + (– M) · 0 + (– M) · 0 – 0 = 0
Δ₅ = 0 · 0 + 0 · 1 + (– M) · 0 + (– M) · 0 – 0 = 0
Δ₆ = 0 · 0 + 0 · 0 + (– M) · (–1) + (– M) · 0 – 0 = M
Δ₇ = 0 · 0 + 0 · 0 + (– M) · 0 + (– M) · (–1) – 0 = M
Δ₈ = 0 · 0 + 0 · 0 + (– M) · 1 + (– M) · 0 – (– M) = 0
Δ₉ = 0 · 0 + 0 · 0 + (– M) · 0 + (– M) · 1 – (– M) = 0

Поскольку есть отрицательные оценки, то план не оптимален. Наименьшая оценка:

Δ₁ = – M – 10

Вводим переменную x₁ в базис.

Определяем переменную, выходящую из базиса. Для этого находим наименьшее неотрицательное отношение для столбца x₁.

Наименьшее неотрицательное: Q₃ = 100. Выводим переменную x₈ из базиса. Для этого над строками таблицы выполняем линейные преобразования.

Из 1-й строки вычитаем 3-ю строку, умноженную на 5
Из 2-й строки вычитаем 3-ю строку, умноженную на 4

Получаем новую таблицу:

Симплекс таблица № 2

Целевая функция:

0 · 1500 + 0 · 600 + 10 · 100 + (– M) · 50 = – 50M + 1000

Вычисляем оценки по формуле:

Δ₁ = 0 · 0 + 0 · 0 + 10 · 1 + (– M) · 0 – 10 = 0
Δ₂ = 0 · 2 + 0 · 5 + 10 · 0 + (– M) · 1 – 8 = – M – 8
Δ₃ = 0 · 4 + 0 · 4 + 10 · 0 + (– M) · 0 – 12 = – 12
Δ₄ = 0 · 1 + 0 · 0 + 10 · 0 + (– M) · 0 – 0 = 0
Δ₅ = 0 · 0 + 0 · 1 + 10 · 0 + (– M) · 0 – 0 = 0
Δ₆ = 0 · 5 + 0 · 4 + 10 · (–1) + (– M) · 0 – 0 = – 10
Δ₇ = 0 · 0 + 0 · 0 + 10 · 0 + (– M) · (–1) – 0 = M
Δ₈ = 0 · (–5) + 0 · (–4) + 10 · 1 + (– M) · 0 – (– M) = M + 10
Δ₉ = 0 · 0 + 0 · 0 + 10 · 0 + (– M) · 1 – (– M) = 0

Поскольку есть отрицательные оценки, то план не оптимален. Наименьшая оценка:

Δ₂ = – M – 8

Вводим переменную x₂ в базис.

Определяем переменную, выходящую из базиса. Для этого находим наименьшее неотрицательное отношение для столбца x₂.

Наименьшее неотрицательное: Q₄ = 50. Выводим переменную x₉ из базиса и удаляем искусственные переменные. Выполняем линейные преобразования.

Из 1-й строки вычитаем 4-ю строку, умноженную на 2
Из 2-й строки вычитаем 4-ю строку, умноженную на 5

Получаем новую таблицу:

Симплекс таблица № 3

Целевая функция:

0 · 1400 + 0 · 350 + 10 · 100 + 8 · 50 = 1400

Вычисляем оценки по формуле:

Δ₁ = 0 · 0 + 0 · 0 + 10 · 1 + 8 · 0 – 10 = 0
Δ₂ = 0 · 0 + 0 · 0 + 10 · 0 + 8 · 1 – 8 = 0
Δ₃ = 0 · 4 + 0 · 4 + 10 · 0 + 8 · 0 – 12 = – 12
Δ₄ = 0 · 1 + 0 · 0 + 10 · 0 + 8 · 0 – 0 = 0
Δ₅ = 0 · 0 + 0 · 1 + 10 · 0 + 8 · 0 – 0 = 0
Δ₆ = 0 · 5 + 0 · 4 + 10 · (–1) + 8 · 0 – 0 = – 10
Δ₇ = 0 · 2 + 0 · 5 + 10 · 0 + 8 · (–1) – 0 = – 8

Поскольку есть отрицательные оценки, то план не оптимален. Наименьшая оценка:

Δ₃ = – 12

Вводим переменную x₃ в базис.

Определяем переменную, выходящую из базиса. Для этого находим наименьшее неотрицательное отношение для столбца x₃.

= 87.5

Наименьшее неотрицательное: Q₂ = 87.5. Выводим переменную x₅ из базиса

2-ю строку делим на 4.
Из 1-й строки вычитаем 2-ю строку, умноженную на 4

Вычисляем:

Получаем новую таблицу:

Симплекс таблица № 4

Целевая функция:

0 · 1050 + 12 · 175/2 + 10 · 100 + 8 · 50 = 2450

Вычисляем оценки по формуле:

Δ₁ = 0 · 0 + 12 · 0 + 10 · 1 + 8 · 0 – 10 = 0
Δ₂ = 0 · 0 + 12 · 0 + 10 · 0 + 8 · 1 – 8 = 0
Δ₃ = 0 · 0 + 12 · 1 + 10 · 0 + 8 · 0 – 12 = 0
Δ₄ = 0 · 1 + 12 · 0 + 10 · 0 + 8 · 0 – 0 = 0
Δ₅ = 0 · (–1) + 12 · 1/4 + 10 · 0 + 8 · 0 – 0 = 3
Δ₆ = 0 · 1 + 12 · 1 + 10 · (–1) + 8 · 0 – 0 = 2
Δ₇ = 0 · (–3) + 12 · 5/4 + 10 · 0 + 8 · (–1) – 0 = 7

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

Решение задачи: x₁ = 100; x₂ = 50; x₃ = 175/2 = 87.5; x₄ = 1050; x₅ = 0; x₆ = 0; x₇ = 0; F_max = 2450

Ответ: x₁ = 100; x₂ = 50; x₃ = 175/2 = 87.5; x₄ = 1050; x₅ = 0; x₆ = 0; x₇ = 0; F_max = 2450

То есть необходимо произвести x₁ = 100 единиц продукции вида А, x₂ = 50 единиц продукции вида Б и x₃ = 87,5 единиц продукции вида В. Максимальная прибыль при этом составит F_max = 2450 единиц.

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

1cov-edu.ru

Математическое программирование. Графический и симплекс метод. Примеры решения задач

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

Для производства двух видов изделий А и В используются три типа технологического оборудования. Для производства единицы изделия А оборудование первого типа используется в течении 1 часа, оборудование второго типа – 3 часа, оборудование третьего типа – 3 часа.

Для производства единицы изделия В оборудование первого типа используется в течении 2 часа, оборудование второго типа – 3 часа, оборудование третьего типа – 1 час.
На изготовление всех изделий предприятие может использовать оборудование первого типа не более чем 32 часа, оборудование второго типа – 60 часов, оборудование третьего типа – 50 часов.

Прибыль от реализации единицы готового изделия А составляет 4 денежные единицы, а изделия В – 2 денежные единицы.

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

2) Решить графическим методом

3)Решить симплекс-методом путем преобразования симплекс-таблиц

Решение

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

Запишем математическую модель задачи:

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

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

         График целевой функции (построен синим цветом) передвигается в направлении, обозначенном стрелкой (по-научному – в направлении своего градиента), до тех пор, пока не достигнет граничной точки многоугольника – в нашем случае это точка – (15 ; 5).  В этой точке целевая функция будет достигать максимума.

 

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

Симплекс-таблица составляется так:
         В графе Базис записываются вектора переменных, принимаемые за базисные. На первом этапе это – A3, A4, A5. Базисными будут переменные, каждая из которых входит только в одно уравнение системы, и нет такого уравнения, в которое не входила бы хотя бы одна из базисных переменных.
         В следующий столбец  записываются коэффициенты целевой функции, соответствующие каждой переменной. Столбец В – столбец свободных членов. Далее идут столбцы коэффициентов Аi при  i –й переменной.
         Под столбцом свободных членов записывается начальная оценка

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

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

         Преобразование симплекс-таблицы ведется следующим образом:

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

         Шаг 2: Для отрицательных оценок вычисляются величины:

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

Шаг 3: Третья строка таблицы делится на 3 и вычитается из первой и второй строк. В сущности, применяется метод исключения неизвестных, известный как метод Жордана – Гаусса.
        Таким образом, новыми базисными переменными становятся A3, A4, A1.

 

        Возвращаемся к шагу 1 и повторяем весь процесс.
Под столбцом свободных членов записывается начальная оценка

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


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

         Опять проверяется критерий оптимальности. Отрицательная оценка только одна – в столбце А2.

         Вычисляем:

         Разрешающим элементом будет второй элемент второго столбца – 2/3.

         Новыми базисными переменными становятся A3, A2, A1
Делим вторую строку на 2 и вычитаем из третьей.
Умножаем вторую строку на 5/2 и вычитаем из первой.

        На этот раз отрицательных оценок нет, т.е. критерий оптимальности выполнен.

Таким образом, получается искомое значение целевой функции F(15; 5; 7; 0; 0) = 70, т.е. возвращаясь к системе неравенств, получаем:

        Ответы, полученные различными методами, совпадают.

www.matem96.ru

Линейное программирование. Симплекс-метод | Решатель

Рассмотрим симплекс-метод для решения задач линейного программирования (ЛП). Он основан на переходе от одного опорного плана к другому, при котором значение целевой функции возрастает.
 

Алгоритм симплекс-метода следующий:
 

1. Исходную задачу переводим в канонический вид путем введения дополнительных переменных. Для неравенства вида ≤ дополнительные переменные вводят со знаком (+), если же вида ≥ то со знаком (—). В целевую функцию дополнительные переменные вводят с соответствующими знаками с коэффициентом, равным 0, т.к. целевая функция не должна при этом менять свой экономический смысл.
2. Выписываются вектора P_i из коэффициентов при переменных и столбца свободных членов. Этим действием определяется количество единичных векторов. Правило – единичных векторов должно быть столько, сколько неравенств в системе ограничений.
3. После этого исходные данные вводятся в симплекс-таблицу. В базис вносятся единичные вектора, и исключая их из базиса, находят оптимальное решение. Коэффициенты целевой функции записывают с противоположным знаком.
4. Признак оптимальности для задачи ЛП – решение оптимально, если в f – строке все коэффициенты положительны. Правило нахождения разрешающего столбца – просматривается f – строка и среди ее отрицательных элементов выбирается наименьшее. Вектор P_i его содержащий становится разрешающим. Правило выбора разрешающего элемента – составляются отношения положительных элементов разрешающего столбца к элементам вектора Р₀ и то число, которое дает наименьшее отношение становится разрешающим элементом, относительно которого будет произведен пересчет симплекс-таблицы. Строка, содержащая этот элемент называется разрешающей строкой. Если в разрешающем столбце нет положительных элементов, то задача не имеет решения. После определения разрешающего элемента переходят к пересчету новой симплекс – таблицы.
5. Правила заполнения новой симплекс – таблицы. На месте разрешающего элемента проставляют единицу, а другие элементы полагают равными 0. Разрешающий вектор вносят в базис, из которого исключают соответствующий нулевой вектор, а остальные базисные вектора записывают без изменений. Элементы разрешающей строки делят на разрешающий элемент, а остальные элементы пересчитывают по правилу прямоугольников.
6. Так поступают до тех пор, пока в f – строке все элементы не станут положительными.

 

Рассмотрим решение задачи с использованием рассмотренного выше алгоритма.
Дано:

Приводим задачу к каноническому виду:

Составляем вектора:

Заполняем симплекс – таблицу:

Правило прямоугольников:
Пересчитаем первый элемент вектора Р₀, для чего составляем прямоугольник из чисел: и получаем: .

Аналогичные расчеты выполним для всех остальных элементов симплекс – таблицы:

В полученном плане f – строка содержит один отрицательный элемент – (-5/3), вектора P₁. Он содержит в своем столбце единственный положительный элемент, который и будет разрешающим элементом. Сделаем пересчет таблицы относительно этого элемента:

Отсутствие отрицательных элементов в f – строке означает, что найден оптимальный план:
F* = 36/5, Х = (12/5, 14/5, 8, 0, 0).
 

Рекомендуемая литература

• Ашманов С. А. Линейное программирование, М: Наука, 1998г.,
• Вентцель Е.С. Исследование операций, М: Советское радио, 2001г.,
• Кузнецов Ю.Н., Кузубов В.И., Волошенко А.Б. Математическое программирование, М: Высшая школа, 1986г.

 
 

Решение линейного программирования на заказ

Заказать любые задания по этой дисциплине можно у нас на сайте. Прикрепить файлы и указать сроки можно на странице заказа.

reshatel.org

Решение задач симплекс методом. Пример работы программы

Решение задач симплекс методом. Пример работы программы

Разработка сайтов и программного обеспечения, системное администрирование, обучение программированию и работе с СУБД MySQL

in english

Главная → Проекты → Реализация метода искусственного базиса (М-метода) → Пример

Реализация симплекс-метода в случае произвольных свободных членов методом искусственного базиса (M-методом)

Исходные данные:

1.0*x₁+ 1.0*x₂ >= 4.0
1.0*x₁+ 2.0*x₂ >= 6.0
-1.0*x₁+ 2.0*x₂ 1.0*x₁+ 1.0*x₂

F(x)= 1.0*x₁+ 4.0*x₂

Введем выравнивающие и искусственные переменные:

1.0*x₁+ 1.0*x₂ -1.0*x₃ +1.0*y₁ = 4.0
1.0*x₁+ 2.0*x₂ -1.0*x₄ +1.0*y₂ = 6.0
-1.0*x₁+ 2.0*x₂ +1.0*x₅ = 12.0
1.0*x₁+ 1.0*x₂ +1.0*x₆ = 12.0

F(x)= 1.0*x₁+ 4.0*x₂ — M*(y₁ +y₂) → max

Начнем решение задачи:

Шаг №1

Базис	Св.члены	x1	x2	x3	x4	x5	x6	y1	y2	Оценка
y 1	4.0	1.0	1.0	-1.0	0.0	0.0	0.0	1.0	0.0	4.0
y 2	6.0	1.0	2.0	0.0	-1.0	0.0	0.0	0.0	1.0	3.0
x 5	12.0	-1.0	2.0	0.0	0.0	1.0	0.0	0.0	0.0	6.0
x 6	12.0	1.0	1.0	0.0	0.0	0.0	1.0	0.0	0.0	12.0
F (x)	0.0	-1.0	-4.0	0.0	0.0	0.0	0.0	0.0	0.0	max
M func	-10.0	-2.0	-3.0	1.0	1.0	0.0	0.0	-1.0	-1.0	max

Базис	Св.члены	x1	x2	x3	x4	x5	x6	y1	y2
y 1	1.0	0.5	0.0	-1.0	0.5	0.0	0.0	1.0	-0.5
x 2	3.0	0.5	1.0	0.0	-0.5	0.0	0.0	0.0	0.5
x 5	6.0	-2.0	0.0	0.0	1.0	1.0	0.0	0.0	-1.0
x 6	9.0	0.5	0.0	0.0	0.5	0.0	1.0	0.0	-0.5
F (x)	12.0	1.0	0.0	0.0	-2.0	0.0	0.0	0.0	2.0
M func	-1.0	-0.5	0.0	1.0	-0.5	0.0	0.0	-1.0	0.5

Шаг №2

Базис	Св.члены	x1	x2	x3	x4	x5	x6	y1	y2	Оценка
y 1	1.0	0.5	0.0	-1.0	0.5	0.0	0.0	1.0	-0.5	2.0
x 2	3.0	0.5	1.0	0.0	-0.5	0.0	0.0	0.0	0.5	6.0
x 5	6.0	-2.0	0.0	0.0	1.0	1.0	0.0	0.0	-1.0	беск
x 6	9.0	0.5	0.0	0.0	0.5	0.0	1.0	0.0	-0.5	18.0
F (x)	12.0	1.0	0.0	0.0	-2.0	0.0	0.0	0.0	2.0	max
M func	-1.0	-0.5	0.0	1.0	-0.5	0.0	0.0	-1.0	0.5	max

Базис	Св.члены	x1	x2	x3	x4	x5	x6	y1	y2
x 1	2.0	1.0	0.0	-2.0	1.0	0.0	0.0	2.0	-1.0
x 2	2.0	0.0	1.0	1.0	-1.0	0.0	0.0	-1.0	1.0
x 5	10.0	0.0	0.0	-4.0	3.0	1.0	0.0	4.0	-3.0
x 6	8.0	0.0	0.0	1.0	0.0	0.0	1.0	-1.0	0.0
F (x)	10.0	0.0	0.0	2.0	-3.0	0.0	0.0	-2.0	3.0
M func	0.0	0.0	0.0	0.0	0.0	0.0	0.0	0.0	0.0

F(x)=10 X=(2; 2; 0; 0; 10; 8)

Шаг №3

Базис	Св.члены	x1	x2	x3	x4	x5	x6	Оценка
x 1	2.0	1.0	0.0	-2.0	1.0	0.0	0.0	2.0
x 2	2.0	0.0	1.0	1.0	-1.0	0.0	0.0	беск
x 5	10.0	0.0	0.0	-4.0	3.0	1.0	0.0	3.3
x 6	8.0	0.0	0.0	1.0	0.0	0.0	1.0	беск
F (x)	10.0	0.0	0.0	2.0	-3.0	0.0	0.0	max

Базис	Св.члены	x1	x2	x3	x4	x5	x6
x 4	2.0	1.0	0.0	-2.0	1.0	0.0	0.0
x 2	4.0	1.0	1.0	-1.0	0.0	0.0	0.0
x 5	4.0	-3.0	0.0	2.0	0.0	1.0	0.0
x 6	8.0	0.0	0.0	1.0	0.0	0.0	1.0
F (x)	16.0	3.0	0.0	-4.0	0.0	0.0	0.0

F(x)=16 X=(0; 4; 0; 2; 4; 8)

Шаг №4

Базис	Св.члены	x1	x2	x3	x4	x5	x6	Оценка
x 4	2.0	1.0	0.0	-2.0	1.0	0.0	0.0	беск
x 2	4.0	1.0	1.0	-1.0	0.0	0.0	0.0	беск
x 5	4.0	-3.0	0.0	2.0	0.0	1.0	0.0	2.0
x 6	8.0	0.0	0.0	1.0	0.0	0.0	1.0	8.0
F (x)	16.0	3.0	0.0	-4.0	0.0	0.0	0.0	max

Базис	Св.члены	x1	x2	x3	x4	x5	x6
x 4	6.0	-2.0	0.0	0.0	1.0	1.0	0.0
x 2	6.0	-0.5	1.0	0.0	0.0	0.5	0.0
x 3	2.0	-1.5	0.0	1.0	0.0	0.5	0.0
x 6	6.0	1.5	0.0	0.0	0.0	-0.5	1.0
F (x)	24.0	-3.0	0.0	0.0	0.0	2.0	0.0

F(x)=24 X=(0; 6; 2; 6; 0; 6)

Шаг №5

Базис	Св.члены	x1	x2	x3	x4	x5	x6	Оценка
x 4	6.0	-2.0	0.0	0.0	1.0	1.0	0.0	беск
x 2	6.0	-0.5	1.0	0.0	0.0	0.5	0.0	беск
x 3	2.0	-1.5	0.0	1.0	0.0	0.5	0.0	беск
x 6	6.0	1.5	0.0	0.0	0.0	-0.5	1.0	4.0
F (x)	24.0	-3.0	0.0	0.0	0.0	2.0	0.0	max

Базис	Св.члены	x1	x2	x3	x4	x5	x6
x 4	14.0	0.0	0.0	0.0	1.0	0.3	1.3
x 2	8.0	0.0	1.0	0.0	0.0	0.3	0.3
x 3	8.0	0.0	0.0	1.0	0.0	0.0	1.0
x 1	4.0	1.0	0.0	0.0	0.0	-0.3	0.7
F (x)	36.0	0.0	0.0	0.0	0.0	1.0	2.0

F(x)=36 X=(4; 8; 8; 14; 0; 0)

Оптимальное решение найдено!

Реклама:

Метки: симплекс метод.

Комментарии:

имя:

e-mail (не публикуется):

комментарий:

© Ткачев Филипп, 2005—2018 Программист, веб-разработка и прикладное ПО. Все права защищены.

www.zoonman.ru