Решение симплекс-методом с помощью симплекс-таблиц - Математические методы и модели в экономике

Определим оптимальный план выпуска продукции, решив задачу линейного программирования (ЗЛП). Для этого сначала приведем модель к каноническому виду (система ограничений имеет вид уравнений). Это достигается введением дополнительных переменных. Решим симплекс-методом задачу с искусственным базисом (т. к. один знак неравенств-ограничений " ? ").

Запишем задачу в канонической форме:

345х1+450х2+437x4+x6 = 86370, 35х1 +40х2+25x3+30x4+20x5+x7 = 5300, 77х1 + 98х2+142x3+68x4+85x5+x8 = 21260, 143x1+112x2+131x3+122x4+81x5+x9 = 27430, 146x2+46x3+54x4+82x5+x10 = 9453, 8x1+4x2+6x3+7x4+5x5+x11 = 478, 4,7x1+6,4x2+3,8x3+5,1x4+4,5x5+x12 = 894,

Х2-x13 = 50,

Х3+x14 = 140,

;

Добавим в систему уравнений искусственные переменные Ri:

345х1+450х2+437x4+x6 = 86370, 35х1 +40х2+25x3+30x4+20x5+x7 = 5300, 77х1 + 98х2+142x3+68x4+85x5+x8 = 21260, 143x1+112x2+131x3+122x4+81x5+x9 = 27430, 146x2+46x3+54x4+82x5+x10 = 9453, 8x1+4x2+6x3+7x4+5x5+x11 = 478, 4,7x1+6,4x2+3,8x3+5,1x4+4,5x5+x12 = 894,

Х2-x13+R1 = 50,

Х3+x14 = 140,

; R1 ? 0.

Перенесем члены целевой функции влево

Z - 800х1 - 366х2 - 510х3 - 347х4 - 789х5 = 0.

Данная система является системой с базисом, в которой x6, x7, x8, x9, x10, x11, x12,x13, x14, R1 - базисные переменные, а x1, x2, x3, x4, x5 - свободные переменные, свободные члены всех уравнений неотрицательны. Следовательно, для решения задачи можно применить симплекс-метод. Решение симплексным методом произведем в симплексных таблицах.

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

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

БП	Х1	Х2	X3	X4	X5	X6	X7	X8	X9	X10	X11	X12	X13	R1	X14	Решение	Отношение
Z	-800	-366	-510	-347	-789	0	0	0	0	0	0	0	0	0	0	0	-
X6	345	450	0	437	0	1	0	0	0	0	0	0	0	0	0	86370	191,93
X7	35	40	25	30	20	0	1	0	0	0	0	0	0	0	0	5300	132,5
X8	77	98	142	68	85	0	0	1	0	0	0	0	0	0	0	21260	216,94
X9	143	112	131	122	81	0	0	0	1	0	0	0	0	0	0	27430	244,91
X10	0	146	46	54	82	0	0	0	0	1	0	0	0	0	0	9453	64,75
X11	8	4	6	7	5	0	0	0	0	0	1	0	0	0	0	478	119,5
X12	4,7	6,4	3,8	5,1	4,5	0	0	0	0	0	0	1	0	0	0	894	139,69
R1	0	1	0	0	0	0	0	0	0	0	0	0	-1	1	0	50	50
X14	0	0	1	0	0	0	0	0	0	0	0	0	0	0	1	140
Оц	0	-1	0	0	0	0	0	0	0	0	0	0	1	-1	0	-	-

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

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

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

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

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

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

БП	Х1	Х2	X3	X4	X5	X6	X7	X8	X9	X10	X11	X12	X13	R1	X14	Решение	Отношение
Z	-800	0	-510	-347	-789	0	0	0	0	0	0	0	-366	366	0	18300	-
X6	345	0	0	437	0	1	0	0	0	0	0	0	450	-450	0	63870	185,13
X7	35	0	25	30	20	0	1	0	0	0	0	0	40	-40	0	3300	94,29
X8	77	0	142	68	85	0	0	1	0	0	0	0	98	-98	0	16360	212,47
X9	143	0	131	122	81	0	0	0	1	0	0	0	112	-112	0	21830	152,66
X10	0	0	46	54	82	0	0	0	0	1	0	0	146	-146	0	2153	-
X11	8	0	6	7	5	0	0	0	0	0	1	0	4	-4	0	278	34,75
X12	4,7	0	3,8	5,1	4,5	0	0	0	0	0	0	1	6,4	-6,4	0	574	122,13
X2	0	1	0	0	0	0	0	0	0	0	0	0	-1	1	0	50	-
X14	0	0	1	0	0	0	0	0	0	0	0	0	0	0	1	140	-

Разрешающий столбец x1 выбирается по z-строке (максимальный по модулю из отрицательных значений z - строки). Разрешающая строкаx11, выбирается по минимальному элементу столбца "Отношение". x1 входит в базис, x11 выходит из базиса.

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

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

БП	Х1	Х2	X3	X4	X5	X6	X7	X8	X9	X10	X11	X12	X13	R1	X14	Решение	Отношение
Z	0	0	90	353	-289	0	0	0	0	0	100	0	34	-34	0	46100	-
X6	0	0	-258,75	135,12	-215,62	1	0	0	0	0	-43,12	0	277,5	-277,5	0	51881,25	-
X7	0	0	-1,25	-0,62	-1,88	0	1	0	0	0	-4,38	0	22,5	-22,5	0	2083,75	-
X8	0	0	84,25	0,62	36,88	0	0	1	0	0	-9,62	0	59,5	-59,5	0	13684,25	371,1
X9	0	0	23,75	-3,12	-8,38	0	0	0	1	0	-17,88	0	40,5	-40,5	0	16860,75	-
X10	0	0	46	54	82	0	0	0	0	1	0	0	146	-146	0	2153	26,26
X1	1	0	0,75	0,88	0,62	0	0	0	0	0	0,12	0	0,5	-0,5	0	34,75	55,6
X12	0	0	0,27	0,99	1,56	0	0	0	0	0	-0,59	1	4,05	-4,05	0	410,67	262,83
X2	0	1	0	0	0	0	0	0	0	0	0	0	-1	1	0	50	-
X14	0	0	1	0	0	0	0	0	0	0	0	0	0	0	1	140	-

Разрешающий столбецx5 (выбираем по z-строке).

Разрешающая строкаx10, выбирается по минимальному элементу столбца "Отношение". x5 входит в базис, x10 выходит из базиса. Заполним следующую таблицу "Итерация 3". Ее мы получим из таблицы "Итерация 2". Превратим разрешающий столбец х5 в единичный (с единицей вместо разрешающего элемента и нулями вместо остальных элементов). Произведем пересчет всех элементов таблицы.

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

БП	Х1	Х2	X3	X4	X5	X6	X7	X8	X9	X10	X11	X12	X13	R1	X14	Решение
Z	0	0	252,12	543,32	0	0	0	0	0	3,52	100	0	548,56	-548,56	0	53691,14
X6	0	0	-137,79	277,12	0	1	0	0	0	2,63	-43,12	0	661,42	-661,42	0	57542,72
X7	0	0	-0,2	0,61	0	0	1	0	0	0,02	-4,38	0	25,84	-25,84	0	2132,98
X8	0	0	63,56	-23,66	0	0	0	1	0	-0,45	-9,62	0	-6,16	6,16	0	12716,06
X9	0	0	28,45	2,39	0	0	0	0	1	0,1	-17,88	0	55,41	-55,41	0	17080,64
X5	0	0	0,56	0,66	1	0	0	0	0	0,01	0	0	1,78	-1,78	0	26,26
X1	1	0	0,4	0,46	0	0	0	0	0	-0,01	0,12	0	0,61	-0,61	0	18,34
X12	0	0	-0,6	-0,04	0	0	0	0	0	-0,02	-0,59	1	1,27	-1,27	0	369,65
X2	0	1	0	0	0	0	0	0	0	0	0	0	-1	1	0	50
X14	0	0	1	0	0	0	0	0	0	0	0	0	0	0	1	140

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

Z = 53691,14; x1 = 18,34; x2 = 50; x3 = 0; x4= 0; x5 = 26,26.

Вывод: Оптимальное решение исходной задачи свидетельствует о том, что для получения максимального дохода в объеме 53691,14 у. д.е. при данных запасах ресурсов необходимо производить продукцию 1-го вида в количестве 18,34, 2-го вида в количестве 50, 5-го вида в количестве 26,26 штук, а 3-ий и 4-ый вид производить не надо вовсе.

Похожие статьи

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

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

• Симплексный метод решения задач ЛП - Решение оптимизационных экономических задач методами линейного программирования

  Вид сырья Запас сырья Количество единиц сырья, идущих на изготовление единицы продукции P1 P2 P3 P4 S1 4 1 1 1 3 S2 18 2 4 6 1 Прибыль от единицы...

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

  В разделе 1 курсовой работы требуется: Определить количество закупаемого заданным филиалом фирмы сырья у каждого АО, (xj), максимизируя прибыль филиала....

• Теоретическое обоснование математического моделирования - Математические методы и модели в экономике

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

• Основные методы решения задач, Решение задачи с помощью математического аппарата - Формирование оптимального штата фирмы

  Условие задачи. Пусть имеются n кандидатов для выполнения этих работ. Назначение кандидата i на работу j связано с затратами CIj (i, j = 1,2,..., n)....

• Геометрическая интерпретация - Математические методы и модели в экономике

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

• Проверка решения двойственной задачи табличным Симплекс-методом - Методика решения двойственных задач линейного программирования

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

• Симплекс - метод - Интегральное и дифференциальное исчисление

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

• Симплекс-метод - Приложение интегрального и дифференциального исчисления к решению прикладных задач

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

• Частотно-матричный метод, Близость (на практике) - Математические модели, используемые в системе оптимизации доставки товаров автотранспортом

  Подход к постановке задачи аналогичен предыдущему, но в качестве исходной модели рассматривается матрица инциденций Q = [ Q (i, j)]. Столбцам матрицы...

• Метод конечных элементов - МАтематическое моделирование в экономике

  - Метод конечных элементов: триангуляция - Метод конечных элементов ( МКЭ ) -- численный метод решения задач прикладной механики. - Широко используется...

• Особенности аппроксимации функции предпочтений ЛПР с помощью аппарата нейро-нечеткого вывода, Исследование эффективности методов - Многокритериальная оптимизация на основе нейросетевой, нечеткой и нейро-нечеткой аппроксимации функции предпочтений лица, принимающего решения

  Используется адаптивная нейро-нечеткая система вывода ANFIS, функционально эквивалентная системе нечеткого вывода Сугено. Вывод осуществляется за два...

• Методы построения решений по математическим моделям - Математическое моделирование в электромеханике

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

• Отличительные особенности исследования операций в экономике - Применение экономико-математических методов и моделей в управлении производством (на примере КУП "Спецкоммунтранс")

  Из перечисленного обзора типов ММ, составляющих предмет ИСО, можно выделить следующие особенности ММ ИСО [3]. - Системный подход, заставляющий...

• Решение транспортной задачи. Нахождение опорного плана тремя методами, Метод минимального элемента - Математическое моделирование в менеджменте и маркетинге

  A 25 40 50 30 45 20 7 3 4 8 6 60 5 7 2 3 5 45 1 4 10 2 6 70 3 4 2 7 8 Допустим, стоимость доставки единицы груза из каждого пункта отправления в...

• Метод конечных разностей, Применение для интерполяции/экстраполяции - МАтематическое моделирование в экономике

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

• Построение модели с помощью метода деревьев решений - Моделирование вероятности банкротства

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

• Решение транспортной задачи методом потенциалов - Математическая модель решения транспортной задачи

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

• Элементы матричного анализа - Методы решения системы линейных уравнений

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

• Методы оптимальных решений

  Решение: Строим на плоскости х1Ох2 многоугольник решений. Для этого в неравенствах системы ограничений и условиях неотрицательности переменных знаки...

• Оптимальное решение модели. - Методика решения задачи целочисленного программирования

  Рис. 1 Шаг 1. Исходную задачу 1 заносим в дерево задач. В качестве исходного допустимого решения берем: x1=x2=x3=0. Соответствующее значение целевой...

• Математические и инструментальные методы экономики - О новой парадигме математических методов исследования

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

• Моделирование системы в условиях неопределенности - Модели и методы решения проблемы выбора в условиях неопределенности

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

• Нахождение функции максимального роста ВРП - Математическая модель роста экономики Краснодарского края

  Построим функцию роста валового регионального продукта: Таблица 11-Данные для функции роста ВРП Год (t) Y (миллион рублей) 1 372930 2 483951 3 648211 4...

• Применение математической модели на экономике Краснодарского края, Нахождение функций роста экономики региона - Математическая модель роста экономики Краснодарского края

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

• Об эффективности математических методов в экономике

  Об эффективности математических методов в экономике В настоящее время проблемы математического образования и понимания эффективности математики как...

• Модель БЭТ - Анализ удельной поверхности активированного угля, основанный на использовании метода тепловой десорбции газа-адсорбата (азота) с поверхности в динамических условиях с помощью специального адсорбера, прибора для текстурных измерений "Термосорб" серии М

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

• Решить графически задачу нелинейного программирования, Математическая модель задачи нелинейного программирования (ЗНП) - Методика решения двойственных задач линейного программирования

  Математическая модель задачи нелинейного программирования (ЗНП) (*) Для ЗНП в отличие от Задачи Линейного Программирования (ЗЛП) нет единого метода...

• Определение коэффициентов передаточной функции по заданным динамическим каналам методом площадей. Сравнение расчетной и аналитической функции (экспериментальной) - Моделирование математической модели теплообменника

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

• Инженерные методы решения задач математического моделирования - Математическое моделирование в электромеханике

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

• Особенности постановки и решения общей задачи линейного программирования - Определение оптимальной стратегии рыночного поведения с использованием макроэкономических методов и моделей

  Второй раздел курсовой работы посвящен особенностям постановки и решения общей задачи линейного программирования, а именно, транспортной задаче (ТЗЛП)....

• Неопределенность цели - Математические модели неопределенностей систем управления и методы, используемые для их исследования

  При управлении подвижными объектами (такими, например, как мобильные роботы, подводные аппараты и т. п.) часто имеет место неопределенность цели, когда...

• Нестационарная неопределенность, Нелинейная неопределенность, Неопределенность внешних условий - Математические модели неопределенностей систем управления и методы, используемые для их исследования

  Модель "вход - выход" для нестационарной системы управления можно представить в следующем виде [2] . Где коэффициенты матриц возмущения и ограничены...

• Непараметрическая неопределенность, Аддитивная неопределенность, Дробно-рациональная неопределенность, Мультипликативная неопределенность - Математические модели неопределенностей систем управления и методы, используемые для их исследования

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

• Методы решения задач календарного планирования, Точные методы. - Особенности математического моделирования задач, связанных с календарным планированием производственных процессов

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

• Задание №5, Проверить ряд на наличие выбросов методом Ирвина, сгладить методом простой скользящее средней с интервалом сглаживания 3, методом экспоненциального сглаживания (а=0,1), представить результаты графически, определить для ряда трендовую модель в виде полинома первой степени (линейную модель), дайте точечный и интервальный прогноз на три шага вперед. - Математические модели в экономике

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

• Задание №1, Объем выпуска продукции Y зависит от количества вложенного труда x как функция, Задание №2, Даны зависимости спроса D=200-2p и предложения S=100+3p от цены., Задание №3, Найти решение матричной игры (оптимальные стратегии и цену игры) . - Математические модели в экономике

  Объем выпуска продукции Y зависит от количества вложенного труда x как функция . Цена продукции v, зарплата p. Другие издержки не учитываются. Найти...

• Пример решения задачи симплекс-методом, Условие задачи - Математические методы и модели в экономике

  Рассмотрим алгоритм симплексного метода на примере решения задачи планирования товарооборота предприятия торговли. Требуется определить оптимальную...

• Введение - Математические методы и модели в экономике

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

• Теоремы двойственности и их использование в задачах ЛП - Решение оптимизационных экономических задач методами линейного программирования

  Исходная задача: При ограничениях: Двойственной является следующая задача: При ограничениях: Число неизвестных в двойственной задаче равно 2....

Решение симплекс-методом с помощью симплекс-таблиц - Математические методы и модели в экономике

Предыдущая | Следующая