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

Для производства двух видов изделий А и В используются три типа технологического оборудования. Для производства единицы изделия А оборудование первого типа используется в течении 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 и повторяем весь процесс.
Под столбцом свободных членов записывается начальная оценка

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


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

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

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

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

2x 1 +5x 2 +3x 3 +8x 4 →min

Ограничивающие условия:

3x 1 +6x 2 -4x 3 +x 4 ≤12
4x 1 -13x 2 +10x 3 +5x 4 ≥6
3x 1 +7x 2 +x 3 ≥1

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

Так как наша задача - задача минимизации, то нам необходимо преобразовать ее к задаче на поиск максимума. Для этого изменим знаки коэффициентов целевой функции на противоположные. Элементы первого неравенства записываем без изменений, добавив в него дополнительную переменную x 5 и изменив знак "≤" на "=". Т. к. второе и третье неравенства имеют знаки "≥" необходимо поменять знаки их коэффициентов на противоположные и внести в них дополнительные переменные x 6 и x 7 соответственно. В результате получем эквивалентную задачу:

3x 1 +6x 2 -4x 3 +x 4 +x 5 =12
-4x 1 +13x 2 -10x 3 -5x 4 +x 6 =-6
-3x 1 -7x 2 -x 3 +x 7 =-1

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

					Своб член
F
X5
X6
X7

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

	X1	X2	X6	X4	Своб член
F	0.8	8.9	0.3	6.5	-1.8
X5	4.6	0.8	-0.4	3	14.4
X3	0.4	-1.3	-0.1	0.5	0.6
X7	-2.6	-8.3	-0.1	0.5	-0.4

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

	X1	X7	X6	X4	Своб член
F	-1.988	1.072	0.193	7.036	-2.229
X5	4.349	0.096	-0.41	3.048	14.361
X3	0.807	-0.157	-0.084	0.422	0.663
X2	0.313	-0.12	0.012	-0.06	0.048

Так как в столбце свободных членов нет отрицательных элементов, то найдено допустимое решение.В строке F имеются отрицательные элементы, это означает что полученое решение не оптимально. Определим ведущий столбец. Для этого найдем в строке F максимальный по модулю отрицательный элемент - это -1.988 Ведущей строкой будет та для которой отношение свободного члена к соответствующему элементу ведущего столбца минимально. Ведущей строкой является X2, а ведущий элемент: 0.313.

	X2	X7	X6	X4	Своб член
F	6.351	0.31	0.269	6.655	-1.924
X5	-13.895	1.763	-0.577	3.882	13.694
X3	-2.578	0.152	-0.115	0.577	0.539
X1	3.195	-0.383	0.038	-0.192	0.153

Так как в строке F нет отрицательных элементов, то найдено оптимальное решение. Так как исходной задачей был поиск минимума, то оптимальным решением будет свободный член строки F, взятый с противоположным знаком. F=1.924
при значениях переменных равных: x 3 =0.539, x 1 =0.153. Переменные x 2 и x 4 не входят в базис, поэтому x 2 =0 x 4 =0.

Для разрешения выполнения апплета на вашем компьютере надо сделать следующее - нажать кнопку Пуск>Панельуправления>Программы>Java. В окне Java Control Panel выбираем вкладку Security (Безопастность) нажимаем кнопку Edit Site List, кнопку add и вставляем в свободное поле путь к этой страницы из адресной строки браузера. Далее нажимаем кнопки ОК, после этого перезагружаем компьютер.

Для запуска апплета нажмите на кнопку "Simplex". Если над этой строкой не видна кнопка "Simplex", то на компьютере не установлена Java.

После нажатия на кнопку « Simplex » выводится первое окно для ввода числа переменных и числа ограничений задачи на симплекс-метод.

После нажатия на кнопку « ok » выводится окно для ввода остальных данных задачи на симплекс-метод: режима отображения (десятичные дроби или обыкновенные), тип критерия задачи min или max , ввод коэффициентов целевой функции и коэффициентов системы ограничений со знаками « ≤ », « ≥ » или « = », ограничения вида х i ≥ 0 вводить не надо, их учитывает в своем алгоритме.

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

Замеченные ошибки и комментарии по работе апплета присылайте на [email protected] или звоните 8 962 700 77 06, за что мы будем Вам очень благодарны.

Программа М-метод

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

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

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

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

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

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

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

итерация 0

БП						Решение	Отношение

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

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

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

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

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

2) Вычисление z-строки таблицы "Итерация 1". На месте -6 в первой строке (z-строке) в столбце х 2 таблицы "Итерация 0" должен быть 0 в первой строке таблицы "Итерация 1". Для этого все элементы строки х 2 таблицы "Итерация 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 2 появился ноль 0 , цель достигнута. Элементы разрешающего столбца х 2 выделены красным цветом.

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

4) Вычисление строки s 2 таблицы "Итерация 1". На месте 3 в s 2 строке таблицы "Итерация 0" должен быть 0 в таблице "Итерация 1". Для этого все элементы строки х 2 таблицы "Итерация 1" 0 1 0 0 1 20 умножим на -3, получим 0 -3 0 0 -3 -60 и сложим эту строку с s 2 - строкой таблицы "Итерация 0" 1 3 0 1 0 72, получим строку 1 0 0 1 -3 12. В столбце х 2 получен нужный 0. Столбец х 2 в таблице "Итерация 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

						Решение	Отношение

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

Итерация 2

						Решение	Отношение

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

Итерация 3

						Решение	Отношение

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

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

2) Решим задачу с искусственным базисом (хотя бы один знак неравенств-ограничений " ≥ " или " = ").

Запишем задачу в канонической форме (в виде системы уравнений, что требует симплекс-метод), для этого введем две переменные х 3 ≥ 0 и х 4 ≥ 0 получим:

Система ограничений предлагает только одну допустимую базисную переменную x 4 , только она входит только в одно уравнение в третье с коэффициентом 1, поэтому в первое и второе уравнения добавляем искусственные переменные R 1 ≥ 0 и R 2 ≥ 0 Чтобы можно было примененить симплекс-метод система уравнений-ограничений должна быть системой с базисом, т.е. в каждом уравнении должна быть переменная с коэффициентом 1, которая входит только в одно уравнение системы, в нашем случае это R 1 , R 2 и x 4 . Получили, так называемую, М-задачу:

Данная система является системой с базисом, в которой R 1 , R 2 и x 4 базисные переменные, а x 1 , x 2 и x 3 свободные переменные, свободние члены всех уравнений неотрицательны. Следовательно, для решения задачи можно применить симплекс-метод. Запишем начальную симплекс-таблицу:

итерация 0

							Решение	Отношение
		-16

В таблицу для задач с искусственным базисом добавлена строка «Оценка». Она получается суммированием соответствующих коэффициентов строк с искусственными переменными (R) с обратным знаком. Она будет присутствовать в таблице до тех пор, пока хотя бы одна из искусственных переменных есть в базисе. По наибольшему по модулю отрицательному коэффициенту строки "Оценка" определяется разрешающий столбец пока она есть в таблице. Когда строка "Оценка" выйдет из таблицы (в базисе нет искусственных переменных) разрешающий столбец будет определяться по z-строке, как и в задаче с начальным базисом. В данной таблице разрешающий столбец х 2 , он выбран по наибольшей по модулю отрицательной оценке (-7). Разрешающая строка R 2 выбрана по наименьшему отношению столбца "Решение" к соответствующим положительным элементам разрешающего столбца, как и в задаче без искусственных переменных. Это значит, что на следующей итерации переменная х 2 из свободной перейдет в базисную, а переменная R 2 из базисной – в свободную. Запишем следующую симплекс-таблицу:

Разрешающий столбец х 1 , разрешающая строка R 1 , R 1 выходит из базиса, x 1 входит в базис. После этого в базисе не остается искусственных переменных, поэтому строки «Оценка» в следующей таблице нет:

итерация 2

							Решение	Отношение

Далее разрешающий столбец выбирается по z-строке. В z-строке все коэффициенты неотрицательны кроме коэффициента при искусственной переменной R 1 , который не влияет на оптимальность, когда искусственные переменные вышли из базиса. Следовательно, получено оптимальное решение x 1 = 6/5; x 2 = 3/5; z max = 72/5.

Особые случаи применения симплекс-метода

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

2) Если в разрешающем столбце симплекс-таблицы все коэффициенты меньше или равны нуль, то нельзя выбрать разрешающую строку, в этом случае решение неограничено.

3) Если ограничения задачи линейного программирования несовместны (т.е. они не могут выполняться одновременно), то задача не имеет допустимых решений. Такая ситуация не может возникнуть, если все неравенства, составляющие систему ограничений, имеют тип " ≤ " с неотрицательными правыми частями, т.к. в этом случае дополнительные переменные могут составить допустимое решение. Для других типов ограничений использются искусственные переменные. Если задача имеет решение, то в оптимальной таблице в базисе нет искусственных переменных (R i). Если они там есть, то задача не имеет решений.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Для реализации трех групп товаров коммерческое предприятие располагает тремя видами ограниченных материально-денежных ресурсов в количестве b 1 = 240, b 2 = 200, b 3 = 160 единиц. При этом для продажи 1 группы товаров на 1 тыс. руб. товарооборота расходуется ресурса первого вида в количестве a 11 = 2 единицы, ресурса второго вида в количестве a 21 = 4 единицы, ресурса третьего вида в количестве a 31 = 4 единицы. Для продажи 2 и 3 групп товаров на 1 тыс. руб. товарооборота расходуется соответственно ресурса первого вида в количестве a 12 = 3, a 13 = 6 единицы, ресурса второго вида в количестве a 22 = 2, a 23 = 4 единицы, ресурса третьего вида в количестве a 32 = 6, a 33 = 8 единиц. Прибыль от продажи трех групп товаров на 1 тыс. руб. товарооборота составляет соответственно c 1 = 4, c 2 = 5, c 3 = 4 (тыс. руб.). Определить плановый объем и структуру товарооборота так, чтобы прибыль торгового предприятия была максимальной.

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

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

Пусть x 1 , x 2 , x 3 - количество реализованных товаров, в тыс. руб., 1, 2, 3 - ей групп, соответственно. Тогда математическая модель задачи имеет вид:

F = 4·x 1 + 5·x 2 + 4·x 3 ->max

0}}}{~}" title="delim{lbrace}{matrix{4}{1}{{2x_1 + 3x_2 + 6x_3= 0}}}{~}">

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

Вводим дополнительные переменные x 4 ≥ 0, x 5 ≥ 0, x 6 ≥ 0, чтобы неравенства преобразовать в равенства.

В качестве базиса возьмем x 4 = 240; x 5 = 200; x 6 = 160.

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

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

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

0 · 240 + 0 · 200 + 0 · 160 = 0

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

Δ 1 = 0 · 2 + 0 · 4 + 0 · 4 - 4 = - 4
Δ 2 = 0 · 3 + 0 · 2 + 0 · 6 - 5 = - 5
Δ 3 = 0 · 6 + 0 · 4 + 0 · 8 - 4 = - 4
Δ 4 = 0 · 1 + 0 · 0 + 0 · 0 - 0 = 0
Δ 5 = 0 · 0 + 0 · 1 + 0 · 0 - 0 = 0
Δ 6 = 0 · 0 + 0 · 0 + 0 · 1 - 0 = 0

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

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

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

= 26.667

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

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

Вычисляем:

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

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

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

0 · 160 + 0 · 440/3 + 5 · 80/3 = 400/3

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

Δ 1 = 0 · 0 + 0 · 8/3 + 5 · 2/3 - 4 = - 2/3
Δ 2 = 0 · 0 + 0 · 0 + 5 · 1 - 5 = 0
Δ 3 = 0 · 2 + 0 · 4/3 + 5 · 4/3 - 4 = 8/3
Δ 4 = 0 · 1 + 0 · 0 + 5 · 0 - 0 = 0
Δ 5 = 0 · 0 + 0 · 1 + 5 · 0 - 0 = 0
Δ 6 = 0 · (-1)/2 + 0 · (-1)/3 + 5 · 1/6 - 0 = 5/6

Поскольку есть отрицательная оценка Δ 1 = - 2/3, то план не оптимален.

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

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

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

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

Вычисляем:

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

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

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

0 · 160 + 0 · 40 + 4 · 40 = 160

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

Δ 1 = 0 · 0 + 0 · 0 + 4 · 1 - 4 = 0
Δ 2 = 0 · 0 + 0 · (-4) + 4 · 3/2 - 5 = 1
Δ 3 = 0 · 2 + 0 · (-4) + 4 · 2 - 4 = 4
Δ 4 = 0 · 1 + 0 · 0 + 4 · 0 - 0 = 0
Δ 5 = 0 · 0 + 0 · 1 + 4 · 0 - 0 = 0
Δ 6 = 0 · (-1)/2 + 0 · (-1) + 4 · 1/4 - 0 = 1

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

Решение задачи:

Ответ

x 1 = 40; x 2 = 0; x 3 = 0; x 4 = 160; x 5 = 40; x 6 = 0; F max = 160

То есть необходимо реализовать товар первого вида в объеме 40 тыс. руб. Товар 2-го и 3-го видов реализовывать не надо. При этом максимальная прибыль составит F max = 160 тыс. руб.

Решение двойственной задачи

Двойственная задача имеет вид:

Z = 240·y 1 + 200·y 2 + 160·y 3 ->min

Title="delim{lbrace}{matrix{4}{1}{{2y_1 + 4y_2 + 4y_3>=4} {3y_1 + 2y_2 + 6y_3>=5} {6y_1 + 4y_2 + 8y_3>=4} {y_1, y_2, y_3>= 0}}}{~}">

Вводим дополнительные переменные y 4 ≥ 0, y 5 ≥ 0, y 6 ≥ 0, чтобы неравенства преобразовать в равенства.

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

Из последней симплекс таблицы № 3 прямой задачи, находим решение двойственной задачи:

Z min = F max = 160;
y 1 = Δ 4 = 0; y 2 = Δ 5 = 0; y 3 = Δ 6 = 1; y 4 = Δ 1 = 0; y 5 = Δ 2 = 1; y 6 = Δ 3 = 4;