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

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

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

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

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

Спасибо за ваши закладки и рекомендации

Решение задач симплекс-методом: примеры онлайн

Задача 1. Компания производит полки для ванных комнат двух размеров — А и В. Агенты по продаже считают, что в неделю на рынке может быть реализовано до 550 полок. Для каждой полки типа А требуется 2 м2 материала, а для полки типа В — 3 м2 материала. Компания может получить до 1200 м2 материала в неделю. Для изготовления одной полки типа А требуется 12 мин машинного времени, а для изготовления одной полки типа В — 30 мин; машину можно использовать 160 час в неделю. Если прибыль от продажи полок типа А составляет 3 денежных единицы, а от полок типа В — 4 ден. ед., то сколько полок каждого типа следует выпускать в неделю?

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

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

Сырьё	Затраты сырья на единицу продукции			Запас сырья
А1	А2	А3
I	3,5	7	4,2	1400
II	4	5	8	2000
Прибыль от ед. прод.	1	3	3

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

Решение задачи линейного программирования с экономическим анализом (pdf, 163 Кб)
Задача 4. Решить задачу линейного программирования симплексным методом:
Задача 5. Решить задачу линейного программирования симплекс-методом:

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

Задача 7. Решить задачу модифицированным симплекс-методом.
Для производства двух видов изделий А и Б используется три типа технологического оборудования. На производство единицы изделия А оборудование первого типа используется а1=4 часов, оборудование второго типа а2=8 часов, а оборудование третьего типа а3=9 часов. На производство единицы изделия Б оборудование первого типа используется б1=7 часов, оборудование второго типа б2=3 часов, а оборудование третьего типа б3=5 часов.
На изготовление этих изделий оборудование первого типа может работать не более чем t1=49 часов, оборудование второго типа не более чем t2=51 часов, оборудование третьего типа не более чем t3=45 часов.
Прибыль от реализации единицы готового изделия А составляет АЛЬФА=6 рублей, а изделия Б – БЕТТА=5 рублей.
Составить план производства изделий А и Б, обеспечивающий максимальную прибыль от их реализации.

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

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

• в виде симплексной таблицы (метод жордановых преобразований); базовой форме записи;
• модифицированным симплекс-методом; в столбцовой форме; в строчечной форме.

• Шаг №1
• Шаг №2
• Видеоинструкция
• Оформление Word
• Также решают

Инструкция . Выберите количество переменных и количество строк (количество ограничений). Полученное решение сохраняется в файле Word и Excel . При этом ограничения типа x_i≥0 не учитывайте. Если в задании для некоторых x_i отсутствуют ограничения, то ЗЛП необходимо привести к КЗЛП, или воспользоваться этим сервисом. При решении автоматически определяется использование М-метода (симплекс-метод с искусственным базисом) и двухэтапного симплекс-метода.

Вместе с этим калькулятором также используют следующие:
Графический метод решения ЗЛП

Решение матричной игры
С помощью сервиса в онлайн режиме можно определить цену матричной игры (нижнюю и верхнюю границы), проверить наличие седловой точки, найти решение смешанной стратегии методами: минимакс, симплекс-метод, графический (геометрический) метод, методом Брауна.

Задачи динамического программирования
Распределить 5 однородных партий товара между тремя рынками так, чтобы получить максимальный доход от их продажи. Доход от продажи на каждом рынке G(X) зависит от количества реализованных партий товара Х и представлен в таблице.

Объем товара Х (в партиях)	Доход G(X)
	1	2	3
0	0	0	0
1	28	30	32
2	41	42	45
3	50	55	48
4	62	64	60
5	76	76	72

1. Составление первого опорного плана. Переход к канонической форме задачи линейного программирования путем введения неотрицательных дополнительных балансовых переменных.
2. Проверка плана на оптимальность. Если найдется хотя бы один коэффициент индексной строки меньше нуля, то план не оптимальный, и его необходимо улучшить.
3. Определение ведущих столбца и строки. Из отрицательных коэффициентов индексной строки выбирается наибольший по абсолютной величине. Затем элементы столбца свободных членов симплексной таблицы делит на элементы того же знака ведущего столбца.
4. Построение нового опорного плана. Переход к новому плану осуществляется в результате пересчета симплексной таблицы методом Жордана—Гаусса.

Базис	B	x1	x2	x3	x4	min
x3	20	5	2	1	0	20:5=4
x4	6	1	1	0	1	6:1=6
F(X1)	-8	-5	0	0	0

Если необходимо найти экстремум целевой функции, то речь идет о поиске минимального значения ( F(x) → min , см. пример решения минимизации функции) и максимального значения ( F(x) → max , см. пример решения максимизации функции) Экстремальное решение достигается на границе области допустимых решений в одной из вершин угловых точек многоугольника, либо на отрезке между двумя соседними угловыми точками. Основная теорема линейного программирования . Если целевая функция ЗЛП достигает экстремального значения в некоторой точке области допустимых решений, то она принимает это значение в угловой точке. Если целевая функция ЗЛП достигает экстремального значения более чем в одной угловой точке, то она принимает это же значение в любой из выпуклой линейной комбинации этих точек. Суть симплекс-метода. Движение к точке оптимума осуществляется путем перехода от одной угловой точки к соседней, которая ближе и быстрее приближает к X_опт. Такую схему перебора точек, называемую симплекс-метод, предложил Р. Данцигом.
Угловые точки характеризуются m базисными переменными, поэтому переход от одной угловой точки к соседней возможно осуществить сменой в базисе только одной базисной переменной на переменную из небазиса.
Реализация симплекс-метода в силу различных особенностей и постановок задач ЛП имеет различные модификации. Построение симплекс-таблиц продолжается до тех пор, пока не будет получено оптимальное решение. Как с помощью симплекс-таблицы определить, что решение задачи линейного программирования является оптимальным?
Если последняя строка (значения целевой функции) не содержит отрицательных элементов, следовательно, найдет оптимальный план. Замечание 1 . Если одна из базисных переменных равна нулю, то крайняя точка, соответствующая такому базисному решению — вырожденная. Вырожденность возникает, когда имеется неоднозначность в выборе направляющей строки. Можно вообще не заметить вырожденности задачи, если выбрать другую строку в качестве направляющей. В случае неоднозначности нужно выбирать строку с наименьшим индексом, чтобы избежать зацикливания. Замечание 2 . Пусть в некоторой крайней точке все симплексные разности неотрицательные D_k³ 0 (k = 1..n+m),т.е. получено оптимальное решение и существует такой А_k – небазисный вектор, у которого D_k = 0. Тогда максимум достигается по крайней мере в двух точках, т.е. имеет место альтернативный оптимум. Если ввести в базис эту переменную x_k, значение целевой функции не изменится. Замечание 3 . Решение двойственной задачи находится в последней симплексной таблице. Последние m компонент вектора симплексных разностей( в столбцах балансовых переменных) – оптимальное решение двойственной задачи. Значение целевых функций прямой и двойственной задачи в оптимальных точках совпадают. Замечание 4 . При решении задачи минимизации в базис вводится вектор с наибольшей положительной симплексной разностью. Далее применяется тот же алгоритм, что и для задачи максимизации. Если задано условие «Необходимо, чтобы сырье III вида было израсходовано полностью», то соответствующее условие представляет собой равенство.

Аналитическое введение в симплекс-метод

Симплексный метод является универсальным методом линейного программирования. Итак, если мы решаем ЗЛП в канонической форме, то система ограничений — это обычная система линейных уравнений. При решении задач ЛП получаются системы линейных уравнений, имеющие, как правило, бесконечно много решений. Например, пусть дана система
Здесь число уравнений равно 2, а неизвестных — 3, уравнений меньше. Выразим x₁ и x₂ через x₃ :
Это общее решение системы. если переменной x₃ придавать произвольные числовые значения, то будем находить частные решения системы. Например, x₃=1 → x₁=1 → x₂=6. Имеем (1, 6, 1) — частное решение. Пусть x₃=2 → x₁=-3, x₂= 1, (-3, 1, 2) — другое частное решение. Таких частных решений бесконечно много. Переменные x₁ и x₂ называются базисными, а переменная x₃ — не базисная, свободная. Совокупность переменных x₁ и x₂ образует базис: Б (x₁, x₂). Если x₃ = 0, то полученное частное решение (5, 11, 0) называется базисным решением, соответствующим базису Б (x₁, x₂). Базисным называется решение, соответствующее нулевым значениям свободных переменных.
В качестве базисных можно было взять и другие переменные: (x₁, x₃) или (x₂, x₃).
Как переходить от одного базиса Б(x₁, x₂) к другому базису Б(x₁, x₃)?
Для этого надо переменную x₃ перевести в базисные, а x₂ — в небазисные т. е. в уравнениях надо x₃ выразить через x₂ и подставить в 1-е: Базисное решение, соответствующее базису Б (x₁, x₃), таково: (-19/5; 0; 11/5). Если теперь от базиса Б (x₁, x₃) нам захочется перейти к базису Б (x₂, x₃), то
Базисное решение, соответствующее базису Б (x₂, x₃): (0;19/4; 7/8).
Из трех найденных базисных решений решение, соответствующее базису Б (x₁, x₃) — отрицательное x₁ < 0, нас в ЗЛП интересуют только неотрицательные решения. Если задача ЛП имеет решение, то оно достигается на множестве базисных неотрицательных решений системы ограничений канонической формы. Поэтому идея симплекс-метода и состоит в последовательном переходе от одного базиса к другому, лучшему с точки зрения значения целевой функции. Пример . Решить задачу ЛП. Функцию F= x₂ — x₁ → min необходимо минимизировать при заданной системе ограничений:
-2x₁ + x₂ + x₃ = 2
x₁ + x₂ + x₅ = 5
x₁ — 2x₂ + x₄ = 12
x_i ≥ 0, i = 1, 5 Эти ограничения могут рассматриваться как произошедшие из неравенств, а переменные x₃, x₅, x₄ — как дополнительные.
Запишем ограничения, выбрав базис из переменных Б< x₃, , x₄, x₅>: Этому базису соответствует базисное неотрицательное решение
x₁ = 0, x₂ = 0, x₃ = 2, x₄ = 2, x₅ = 5 или (0, 0, 2, 2, 5).
Теперь нужно выразить F через небазисные переменные, в нашем случае это уже сделано: F= x₂ — x₁.
Проверим, достигла ли функция F своего минимального значения. Для этого базисного решения F= 0 — 0 = 0 — значение функции равно 0. Но его можно уменьшить, если x₁ будет возрастать, т. к. коэффициент в функции при x₁ отрицателен. Однако при увеличении x₁ значения переменных x₄, x₅ уменьшаются (смотрите второе и третье равенство системы ограничений). Переменная x₁ не может быть увеличена больше чем до 2, иначе x₄ станет отрицательной (ввиду равенства 2), и не больше, чем до 5, иначе x₅ — отрицателен. Итак, из анализа равенств следует, что переменную x₁ можно увеличить до 2, при этом значение функции уменьшится.
Перейдем к новому базису Б₂, введя переменную x₁ в базис вместо x₄.
Б₂x₁, x₃, x₅>.
Выразим эти базисные переменные через небазисные. Для этого сначала выразим x₁ из второго уравнения и подставим в остальные, в том числе и в функцию. Имеем:

F = -2 — x₂ + x₄.
Базисное решение, соответствующее базису Б₂x₁, x₃, x₅>, имеет вид (2, 0, 6, 0, 3), и функция принимает значение F= -2 в этом базисе.
Значение функции можно и дальше уменьшать, увеличивая x₂. Однако, глядя на систему, x₂ можно увеличивать лишь до 1, т. к. иначе из последнего равенства x₅ = 3 — 3x₂ + x₄ следует, что при x₂ > 1 x₅ станет отрицательной. А у нас все переменные в ЗЛП предполагаются неотрицательными. Остальные уравнения системы не дают ограничений на x₂. Поэтому увеличим x₂ до 1, введя его в базис вместо x₅: Б₃x₁, x₂, x₃>.
Выразим x₂ через x₅ и подставим во все уравнения:

Базисное решение, соответствующее базису Б₃х₁, х₂, х₃>, выписывается (4, 1, 9, 0, 0), и функция принимает значение F= -3. Заметим, что значение F уменьшилось, т. е. улучшилось по сравнению с предыдущим базисом.
Посмотрев на вид целевой функции , заметим, что улучшить, т. е. уменьшить значение F нельзя и только при x₄ = 0, x₅ = 0 значение F= -3. как только x₄, x₅ станут положительными, значение F только увеличится, т. к. коэффициенты при x₄, x₅ положительны. Значит, функция F достигла своего оптимального значения F* = -3. Итак, наименьшее значение F, равное -3, достигается при x₁* = 4, x₂* = 1, x₃* = 9, x₄* = 0, x₅* = 0. На этом примере очень наглядно продемонстрирована идея метода: постепенно переходя от базиса к базису, при этом всегда обращая внимание на значения целевой функции, которые должны улучшиться, мы приходим к такому базису, в котором значение целевой функции улучшить нельзя, оно оптимально. Заметим, что базисов конечное число, поэтому количество шагов, совершаемых нами до того нужного базиса, конечно.

Подробный разбор симплекс-метода

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

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

§1. Постановка задачи линейного программирования

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

Общая задача линейного программирования (далее – ЛП) имеет вид:

§2. Каноническая форма задачи ЛП

Каноническая форма задачи ЛП:

Замечание: Любая задача ЛП сводится к канонической.

Алгоритм перехода от произвольной задачи ЛП к канонической форме:

1. Неравенства с отрицательными умножаем на (-1).
2. Если неравенство вида (≤), то к левой части добавляем – добавочную переменную, и получаем равенство.
3. Если неравенство вида (≥), то из левой части вычитаем , и получаем равенство.
4. Делаем замену переменных:

• Если , то
• Если — любой, то , где

§3. Угловые точки. Базисные/свободные переменные. Базисные решения

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

Иными словами, невозможно найти две точки в области, интервал проходящий через которые содержит (т.е. – не внутренняя точка).

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

§4. Симплекс-метод

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

Необходимые условия для применения симплекс-метода:

1. Задача должна иметь каноническую форму.
2. У задачи должен быть явно выделенный базис.

Замечание: Базисный вектор имеет размерность (m*1), где m – количество уравнений в системе ограничений.

Для удобства вычислений и наглядности обычно пользуются симплекс-таблицами:

• В первой строке указывают «наименование» всех переменных.
• В первом столбце указывают номера базисных переменных, а в последней ячейке – букву Z (это строка функционала).
• В «середине таблицы» указывают коэффициенты матрицы ограничений — aij.
• Последний столбец – вектор правых частей соответствующих уравнений системы ограничений.
• Крайняя правая ячейка – значение целевой функции. На первой итерации ее полагают равной 0.

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

Замечание: Коэффициенты в строке функционала берутся со знаком “-”.

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

1. Выбираем переменную, которую будем вводить в базис. Это делается в соответствии с указанным ранее принципом: мы должны выбрать переменную, возрастание которой приведет к росту функционала. Выбор происходит по следующему правилу:

• Если задача на минимум – выбираем максимальный положительный элемент в последней строке.
• Если задача на максимум – выбираем минимальный отрицательный.

Замечание: Хотя мы и берем минимальное отрицательное число в задаче на максимум, этот коэффициент показывает направление роста функционала, т.к. строка функционала в симплекс-таблице взята со знаком “-”. Аналогичная ситуация с минимизацией.

Определение: Столбец симплекс-таблицы, отвечающий выбранному коэффициенту, называется ведущим столбцом.

2. Выбираем переменную, которую будем вводить в базис. Для этого нужно определить, какая из базисных переменных быстрее всего обратится в нуль при росте новой базисной переменной. Алгебраически это делается так:

• Вектор правых частей почленно делится на ведущий столбец
• Среди полученных значений выбирают минимальное положительное (отрицательные и нулевые ответы не рассматривают)

Замечание: Фактически, мы выражаем старые базисные переменные из каждого уравнения системы ограничений через остальные переменные и смотрим, в каком уравнении возрастание новой базисной переменной быстрее всего даст 0. Попадание в такую ситуацию означает, что мы «наткнулись» на новую вершину. Именно поэтому нулевые и отрицательные элементы не рассматриваются, т.к. получение такого результата означает, что выбор такой новой базисной переменной будет уводить нас из области, вне которой решений не существует.

3. Ищем элемент, стоящий на пересечении ведущих строки и столбца.

Определение: Такой элемент называется ведущим элементом.

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

5. Далее начинается процесс вычисления нового базисного решения. Он происходит с помощью метода Жордана-Гаусса.

• Новая Ведущая строка = Старая ведущая строка / Ведущий элемент
• Новая строка = Новая строка – Коэффициент строки в ведущем столбце * Новая Ведущая строка

6. После этого проверяем условие оптимальности. Если полученное решение неоптимально – повторяем весь процесс снова.

§5. Интерпретация результата работы симплекс-метода

1. Оптимальность

Условие оптимальности полученного решения:

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

Однако, стоит отметить, что заданный функционал может не и достигать максимума/минимума в заданной области. Алгебраический признак этого можно сформулировать следующим образом:

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

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

3. Альтернативные решения

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

Алгебраический признак существования альтернативы:

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

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

Эпилог

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

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

Спасибо за внимание!

Если уже сейчас Вы мучаетесь с реализацией симплекс-метода, советую почитать книгу А. Таха Введение в исследование операций — там все неплохо разобрано и в теории, и на примерах; а также посмотрите примеры решения задач matburo.ru — это поможет с реализацией в коде.

• Математика
• Линейное программирование
• Симплекс-метод
• Оптимизация

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

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

Спасибо за ваши закладки и рекомендации

Истоки симплексного метода и его суть

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

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

При этом на переменные, влияющие на значение критерия, накладываются линейные ограничения в виде уравнений или неравенств. По существу, симплекс-метод – это усовершенствованный графический методрешения задач ЛП в многомерном пространстве.

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

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

Последовательность действий можно описать следующим образом:

• путем преобразований система ограничений приводится к необходимой, так называемой базисной, форме;
• находится так называемое опорное решение, служащее «точкой отсчета»;
• последовательно перебираются вершины симплекса. Если в данной точке значение критерия больше (или меньше) предыдущего, то процесс продолжается. Когда значение критерия уже нельзя улучшить, значит, решение найдено.

Практический пример применения симплексного метода

Решим симплексным методом задачу. Максимизируем функцию $$L=X+Z \rightarrow \max$$ при ограничениях $$ \left\< \begin Y-X+Z=1,\\ X-2Z+T=2. \end \right. $$ У нас есть четыре переменные – $X, Y, Z, T$ – причем критерий зависит лишь от двух переменных. Примем $Т$ и $Y$ за базисные переменные и выразим их через остальные две свободные переменные. Получим: $$L=X+Z \rightarrow \max,$$ $$ \left\< \begin Y=1+X-Z,\\ T=2-X+2Z. \end \right. $$ При $X$ и $Z$ равных нулю, базисные переменные равны $Y=1, T=2$. Значение критерия $L=0$. Значит, точка $(1,0,0,2)$ является базисным решением. Начнем перебор вершин симплекса. Увеличить критерий можно увеличив $Z$ до единицы. Тогда при $Z=1, X=0$ базисные переменные примут значения $Y=0, T=4$. Новое допустимое решение – это точка $(0,0,1,4)$, критерий равен $L=1$. Теперь выразим $Z$ и $T$ через $Y$ и $X$: $$L=1-Y+2X \rightarrow \max,$$ $$ \left\< \begin Z=1-Y+Z,\\ T=4-2Y+X. \end \right. $$ Увеличить $L$ можно только увеличив $X$. Однако $X$ можно увеличивать бесконечно, исходня из системы уравнений. Следовательно, критерий $L$ будет принимать неограниченно большие значения, решения задачи симплекс-методом не существует. В этом случае говорят, что имеет случай бесконечного симплекса. Другие примеры решения задач линейного программирования вы найдете в разделе: Задачи линейного программирования с решениями (десятки примеров!).

Спасибо за ваши закладки и рекомендации

• Решение линейного программирования на заказ
• Учебники по линейному программированию