Решение задачи о диете симплекс методом
Пример №1. Бройлерное хозяйство птицеводческой фермы насчитывает 20 000 цыплят, которые выращиваются до 8-недельного возраста и после соответствующей обработки поступают в продажу.
Недельный расход корма в среднем (за 8 недель) составляет 500г = 0.5 кг.
Для того, чтобы цыплята достигли к 8-й неделе необходимого веса, кормовой рацион должен удовлетворять определённым требованиям по питательности.
Этим требованиям могут соответствовать смеси различных видов кормов, или ингредиентов.
В таблице приведены данные, характеризующие содержание (по весу) питательных веществ в каждом из ингредиентов и удельную стоимость каждого ингредиента. Смесь должна содержать:
- не менее 0.8% кальция (от общего веса смеси)
- не менее 22% белка (от общего веса смеси)
- не более 5% клетчатки (от общего веса смеси )
Требуется определить количество (в кг) каждого из трёх ингредиентов, образующих смесь минимальной стоимости, при соблюдении требований к общему расходу кормовой смеси и её питательности.
| Ингредиент | Содержание питательных веществ (кг/ингредиента) | Стоимость (руб./кг) | ||
| Кальций | Белок | Клетчатка | ||
| Известняк Зерно Соевые бобы | 0.38 0.001 0.002 | – 0.09 0.5 | – 0.02 0.08 | 0.04 0.15 0.40 |
Математическая формулировка задачи. Введём следующие обозначения:
X 1 – содержание известняка в смеси (кг);
Х2 – содержание зерна в смеси (кг);
Х3 – содержание соевых бобов в смеси (кг);
Общий вес смеси, еженедельно расходуемый на кормление цыплят: 20 000 х 0.5 = 10 000 кг.
Ограничения, связанные с содержанием кальция, белка и клетчатки в кормовом рационе, имеют вид:
0.38X1 + 0.001Х2 + 0.002Х3 ≥ 0.008 х 10 000,
0.09Х2 + 0.50Х3 ≥ 0.22 х 10 000,
0.02Х2+ 0.08Х3 ≤ 0.05 х 10 000.
Окончательный вид математической формулировки задачи:
min f(X) = 0.04 x1 + 0.15Х2 +0,40Х3
при ограничениях
Х1+Х2+Х3= 10 000
0.38Х1 + 0.001Х2 + 0.002Х3 ≥ 80
0.09Х2+ 0.50Х3 ≥ 2200
0.02Х2+ 0.08Х3 ≤ 500
Xj > 0, j = 1, 2, 3.
Перейти к решению симплекс-методом
Задача о составлении рациона (задача о диете, задача о смесях)
Пример №1. Имеется два вида продукции П1 и П2, содержащие питательные вещества S1, S2, S3, S4 (жиры, белки, углеводы, витамины). Содержание числа единиц питательных веществ в единице каждого вида продукции и необходимый минимум питательных веществ приведены в табл. 2.
Таблица 2
Питательные вещества | Число единиц питательных веществ в единице продукции | Необходимый минимум питательных веществ | |
| П1 | П2 | ||
| S1 | 1 | 2 | 10 |
| S2 | 3 | 2 | 8 |
| S3 | 2 | 1 | 9 |
| S4 | 2 | 2 | 11 |
Стоимость единицы продукции П1 и П2 соответственно равна 3 и 4 д.е.
Решение. Обозначим через х1 и х2 – количество продукции П1 и П2, входящей в дневной рацион. Тогда общая стоимость рациона составит (д.е.)
F = 3×1 + 4×2. (5)
С учетом необходимого минимума питательных веществ составим систему ограничений. Рацион включает (x1 + 2×2) единиц питательного вещества S1, (3×1 + 2×2) единиц питательного вещества S2, (2×1 + x2) единиц питательного вещества S3 и (2×1 + 2×2) единиц питательного вещества S4. Так как содержание питательных веществ S1, S2, S3, S4 в рационе должно быть не менее 10, 8, 9, 11 единиц, соответственно, то получим систему ограничений неравенств:
x1+2×2 ≥ 10 (6)
3×1+2×2 ≥ 8
2×1+x2 ≥ 9
2×1+2×2 ≥ 11
x1 ≥ 0, x2 ≥ 0
Итак, экономико-математическая модель задачи: составить дневной рацион , удовлетворяющий системе ограничений (6), при котором функция (5) принимает минимальное значение.
Сформулируем данную задачу в общей постановке.
Обозначим через xj (j = 1, 2,…, n) – количество единиц j-го продукта в дневном рационе. В рационе используется n видов продуктов. Каждый продукт содержит m питательных веществ в количестве не менее bi (i = 1,2,…,m) единиц, aij – число единиц питательного вещества si в единице продукта j-го вида. Известна стоимость cj единицы j-го продукта. Необходимо составить рацион нужной питательности при минимальных затратах на него.
Экономико-математическая модель примет вид:
F=c1x1+c2x2+…+cnxn→(min) (7)
(8)
Замечание 1. Целевую функцию (7) и систему ограничений неравенств можно записать, используя знак ∑ (суммы).
(9)
(10)
Замечание 2. В задаче составления рациона (диеты, кормовой смеси) могут использоваться ограничения не только по необходимому минимуму питательных веществ, но и по минимальному общему весу смеси.
Например. Некоторая фирма имеет возможность купить n различных видов сырья и приготавливать различные виды смесей (продуктов). Каждый вид сырья содержит разное количество питательных веществ. Установлено, что продукция должна удовлетворять некоторым минимальным требованиям с точки зрения питательности (полезности). Необходимо определить количество каждого j-го вида сырья, образующего смесь минимальной стоимости при соблюдении требований к общему расходу смеси и её питательность.
Экономико-математическая модель задачи будет иметь вид:
,
при ограничениях: на общий расход смеси
на питательность смеси
на не отрицательность переменных
xj≥0, j=1,2,…n,
где xj – количество j-го сырья в смеси;
n – количество видов сырья;
m – количество питательных веществ;
aij – количество i-го питательного вещества, содержащегося в единице j-го вида сырья;
b1 – минимальное количество i-го питательного вещества, содержащегося в единице смеси;
cj – стоимость единицы сырья j;
q – минимальный общий вид смеси.
Пример №3. В заводской лаборатории создается антифрикционный сплав (оловянистый баббит), который должен содержать: олова – не меньше 15%, сурьмы – не меньше 15%, свинца – около 70%. Есть четыре сплава, процентный состав и цены на которые приведенные в таблице:
| Элементы | Сплав | |||
| 1 | 2 | 3 | 4 | |
| Олово | 12 | 20 | 12 | 20 |
| Сурьма | 12 | 18 | 18 | 14 |
| Свинец | 76 | 62 | 70 | 66 |
| Цена на 1 кг | 3,5 | 5,2 | 4,0 | 4,6 |
Рассчитать количество элементов для сплава каждого вида, необходимое для 1 кг смеси, которая бы обеспечила минимальные затраты.
Решение
Составим экономико-математическую модель задачи.
Обозначим через
x1 – количество сплава 1, кг
x2 – количество сплава 2, кг
x3 – количество сплава 3, кг
x4 – количество сплава 4, кг
Система ограничений по содержанию
12×1 + 20×2 + 12×3 + 20×4 ≥ 15(x1 + x2 + x3 + x4)
12×1 + 18×2 + 18×3 + 14×4 ≥ 15(x1 + x2 + x3 + x4)
76×1 + 62×2 + 70×3 + 66×4 = 70(x1 + x2 + x3 + x4)
Ограничение по количеству
x1 + x2 + x3 + x4 = 1 (кг)
Целевая функция
3,5×1 + 5,2×2 + 4×3 + 4,6×4 → min
Ответ: x1 = 0,25; x2 = 0; x3 = 0,375; x4 = 0,375 (решение можно получить через калькулятор или средствами Excel).
Пример №4. Для сохранения здоровья и работоспособности человек должен в сутки потреблять не менее 63 усл.ед. белков, не менее 147 усл.ед. жиров и не менее 126 усл.ед. углеводов. Для простоты допустим, что имеется всего два вида продуктов и ; стоимость единицы каждого из них равна соответственно 12 и 9 ден.ед. Содержание названных питательных веществ в различных продуктах неодинаково. Предположим, что в единице продукта содержится 9 усл.ед. белков, 7 усл.ед. жиров 9 усл.ед. углеводов; а в единице продукта содержится соответственно 3, 21, 10 усл.ед. тех же питательных веществ. Требуется:
- составить экономико-математическую модель задачи, позволяющую сформировать из продуктов и суточную диету, которая с одной стороны содержала бы белков, жиров и углеводов не менее минимально научно обоснованных норм и вместе с тем требовала бы минимальных затрат;
- решить задачу графическим способом.
Решение.
x1 – продукт 1, x2 – продукт 2,
Целевая функция: 12×1+9×2 → min
Система ограничений:
9×1+3×2 ≥ 63
7×1+21×2 ≥ 147
9×1+10×2 ≥ 126
Задача о смесях
Постановка задачи: N ингредиентов – y1, y2, y3, y4. В результате смешивания этих ингредиентов в пропорциях g11:g12:g13:g14, g21:g22:g23:g24, g31:g32:g33:g34 и g41:g42:g43:g44 получают смесь n сортов x1, x2, x3, x4. Цена его реализации соответственно s1, s2, s3, s4.
Экономико-математическая модель задачи
Компоненты | Сорта | Объем ресурсов | |||
x1 | x2 | x3 | x4 | ||
N1 | g11/Σg1i | g21/Σg2i | g31/Σg3i | g41/Σg4i | y1 |
N2 | g12/Σg1i | g22/Σg2i | g32/Σg3i | g42/Σg4i | y2 |
N3 | g13/Σg1i | g23/Σg2i | g33/Σg3i | g43/Σg4i | y3 |
N4 | g14/Σg1i | g24/Σg2i | g34/Σg3i | g44/Σg4i | y4 |
Цена | s1 | s2 | s3 | s4 | |
Σg1i = g11 + g12 + g13 + g14
Целевая функция
F(x) = s1x1 + s2x2 + s3x3 + s4x4 → max
Ограничения
x1g11/Σg1i + x2g21/Σg2i + x3g31/Σg3i + x4g41/Σg4i ≤ y1
x1g12/Σg1i + x2g22/Σg2i + x3g32/Σg3i + x4g42/Σg4i ≤ y2
x1g13/Σg1i + x2g23/Σg2i + x3g33/Σg3i + x4g43/Σg4i ≤ y3
x1g14/Σg1i + x2g24/Σg2i + x3g34/Σg3i + x4g44/Σg4i ≤ y4
Перейти к составлению условий онлайн
Пример. Завод выпускает 4 вида полуфабрикатов Bi в количествах: В1 – 400 т, В2 – 250 т, В3 – 350 т и В4 – 100 т.
В результате смешения этих компонентов получают 3 вида продукции Aj. Пропорции смешиваемых полуфабрикатов следующие: для А1 – 2:3:5:2, для А2 – 3:1:2:1, для A3 – 2:2:1:3. Стоимость 1 т продукции Aj составляет: А1 – 12 руб., А2 – 10 руб., А3 – 15 руб.
Составить оптимальный план выпуска продукции по критерию:
а) максимальной стоимости выпущенной продукции;
б) максимального использования полуфабрикатов
Задача об оптимальном составе бетонной смеси
Для приготовления b0 кг бетонной смеси c заданными свойствами используются три вещества Аj (j = 1, 2, 3). В xj кг каждого вещества Аj содержится aijxj кг химического элемента Bi (i = 1, 2). Содержание элемента Bi в смеси должно находиться в пределах от bi1 до bi2 кг. Стоимость 1 кг каждого вещества Aj составляет cj руб.
Требуется определить такой состав для приготовления бетонной смеси, при котором общая стоимость израсходованных веществ была бы минимальной.
| A1 | A2 | A3 | Нижняя граница | Верхняя граница |
| a11 | a12 | a13 | b1 | b1 |
| a21 | a22 | a23 | b2 | b2 |
| c1 | c2 | c3 |
Источник
Решение задач линейного программирования, связанных с минимизацией целевой функции, имеет некоторые особенности, которые мы рассмотрим здесь на примере задачи об оптимальной диете. Пусть в некоторой упрощённой ситуации фермеру-животноводу необходимо спланировать закупку кормов, и при этом на рынке имеется два вида подходящих ему кормов и по цене соответственно 3 и 4 денежные единицы за единицу веса. Фермер проконсультировался со специалистом по питанию животных и получил следующие рекомендации: в сутки каждое животное должно получать не менее 5 единиц углеводов, 3 единиц белков и 4 единиц витаминов (в некоторых соответствующих единицах). После этого фермер изучил состав питательных веществ кормов и , и выписал результат в виде таблицы (в тех же единицах):
Перед фермером возникла задача: в каком объёме закупать корма и , чтобы реализовать рекомендации специалиста и при этом потратить минимум денег?
Экономическое описание задачи у нас имеется, составим математическую модель. Обозначим ( , ) – объёмы закупок кормов и в сутки на каждое животное. Аналогично предыдущему разделу мы получаем задачу линейного программирования: найти пару чисел ( , ), удовлетворяющую ограничениям
(5.1)
и минимизирующую целевую функцию
. (5.2)
В этой задаче – только две неизвестные, поэтому имеется графический способ решения. Он проводится по схеме, объяснённой выше, и разобран здесь не будет.
Решение симплекс-методом осуществляется примерно так же, как и в предыдущем примере, поэтому разъясняться будут только его особенности для данного примера.
Итак, вначале мы заменяем все неравенства равенствами (теперь нам надо вычитать переменные, т.к. знак неравенств – другой):
(5.3)
, ,
Тем самым, от задачи (5.1)-(5.2) мы переходим к равносильной ей задаче (5.3)-(5.2).
Начинаем аналогичные шаги нашей игры. Выражение базисных переменных , , первого шага через свободные , будет следующим:
(5.4)
Значит, базисное решение на первом шаге имеет вид (0, 0, -5, -3, -4) и не является допустимым!Не имеет никакого смысла вычислять значение целевой функции на нём и рассуждать, можно ли его улучшить (как мы это делали раньше). Для начала нам нужно добиться, чтобы базисное решение стало допустимым, т.е. чтобы все его компоненты стали неотрицательными. Из рассмотрения правых частей (5.4) ясно, что для этого можно увеличивать или (или оба одновременно, но мы опять будем изменять лишь одну переменную). В данном случае имеет смысл увеличивать , т.к. коэффициент при в целевой функции (5.2) меньше (не будем забывать, что в нынешнем примере мы минимизируем целевую функцию). Итак, пусть и . Тогда условия допустимости примут вид . Естественно, мы возьмём самое наименьшее из возможных значений = . Далее становится новой базисной переменной, а на замену ей выходит переменная (значение 4 возникло из уравнения для в (5.4)). Итак, базисные переменные второго шага – , , ; а свободные переменные – , . Выражаем базисные переменные через свободные (сначала − из последнего равенства в (5.4), а затем подставляем в остальные равенства этой системы):
(5.5)
И вот уже базисное решение второго шага получается допустимым – (4, 0, 7, 1, 0), и мы можем изучать его на оптимальность. Для этого выразим целевую функцию через свободные переменные второго шага (подставив в (5.2) выражение для из первого уравнения системы (5.5)):
Видно, что мы ещё не достигли оптимума: в выражении для целевой функции имеется отрицательный коэффициент при одной из свободных переменных, увеличивая которую, мы сможем ещё уменьшить целевую функцию. Ясно, что в случае рассматриваемых задач на минимум условие завершения работы симплекс-метода состоит в том, что в выражении для целевой функции через свободные переменные все коэффициенты неотрицательны.Если это так, тосоответствующее базисное решение – оптимально.
У нас сейчас имеется коэффициент (-2) при , поэтому положим и =0. Аналогично изложенному выше, мы, с одной стороны, стремимся как можно сильнее увеличить (тем самым, как можно сильнее уменьшить Z ), но, с другой, нас ограничивают условия допустимости . Значит, берём .
Опуская детали, укажем, что на следующем шаге имеем следующее выражение базисных переменных этого шага , , через свободные переменные , :
При этом выражение для целевой функции будет таким: . Теперь очевидно, что базисное решение (2, 1, 2, 0, 0) даёт самое наименьшее возможное значение целевой функции . (В самом деле, для данного базисного решения и любое его изменение означает изменение , в сторону увеличения (т.к. они неотрицательны!) и увеличение целевой функции .) Окончательно, в исходной формулировке решение даёт пара чисел ; таким образом, нашему фермеру целесообразно закупать ежесуточно для каждого животного две единицы веса корма и одну единицу веса корма . Задача решена.
Раздел 6
Двойственная задача линейного программирования на примере задачи торга
Вернёмся к экономическому примеру раздела 2 − заводу, выпускающему два вида продукции. Мы рассматривали задачу линейного программирования, связанную с выбором оптимального плана. Сейчас мы определим некоторую связанную с ней задачу, которую назовём двойственной по отношению к исходной.
Представим себе, что на календаре – 90-е годы, экономический кризис; и представим некоторую фирму, оптом скупающую у предприятий сырье с целью выгодной перепродажи за границу. И вот её представители начинают переговоры с рассматриваемым нами заводом. Их цель: скупить (по возможности дёшево) всё наше сырьё. Мы также отстаиваем свою выгоду. Начинается торг. Пусть − обсуждаемые цены за единицу сырья , , . Пусть на наших складах хранится запас сырья на месяц, и переговоры ведутся именно об этих объёмах. Тогда, с учётом запаса сырья в расчёте на одни сутки, мы получаем, что цель фирмы-перекупщика в ходе торга – это
(6.1)
(т.е. минимизация цены суточного запаса трёх видов сырья). Наш завод имеет дело со следующей альтернативой: либо использовать сырьё для производства и получить прибыль с конечной продукции, либо продать всё сырье перекупщику. Разумеется, мы выберем второй вариант только в том случае, если он будет нам более выгоден. Запишем это требование математически. Для этого обратимся к матрице технологических коэффициентов:
Отсюда видно, что если мы используем 1 ед. сырья , 1 ед. сырья и 2 ед. сырья в производстве (одной единицы продукции , разумеется), то получим прибыль в 2 денежные единицы (по условию). Значит, перекупщик должен предложить нам не меньше за всё это сырьё, т.е. мы потребуем, чтобы выполнялось неравенство . Аналогично, рассматривая выгодность сделки по отношению к второму виду продукции, получаем неравенство . (Очевидно, что равенства нас устраивают, т.к. мы получаем ту же самую прибыль безо всяких усилий!). Итак, в совокупности наши условия на переговорах имеют вид:
(6.2)
Задача линейного программирования (6.1)-(6.2) называется, по определению, двойственной по отношению к исходной задаче (2.1)-(2.2) из раздела 2.
Правило построения двойственной задачи может быть усмотрено из следующей таблицы:
(6.3)
Сравнивая данную таблицу с формулировками задач (2.1)-(2.2) и (6.1)-(6.2), мы видим, что в исходной задаче ограничения и целевая функция записываются «по строкам», а в двойственной – «по столбцам». При этом в исходной задаче все ограничения – неравенства « » и целевая функция максимизируется, а в двойственной задаче все ограничения – « » и целевая функция минимизируется. Ясно, что исходная задача однозначно восстанавливается по двойственной. Таким образом, имеются естественные пары взаимно-двойственных задач.
Раздел 7
Источник
В 1982 г. Джорджу Стиглеру была присуждена Нобелевская премия за труды по теории экономического регулирования (совсем не проблемы линейного программирования!)
Еще в 1945 г. без помощи линейного программирования ДЖОРДЖ СТИГЛЕР. составил “самый дешевый набор продуктов”, явившийся фактически прообразом потребительской корзины.
Пытался найти наиболее дешевый рацион, удовлетворяющий 9 диетическим требования, сформулированным в 1943 году. В наборе продуктов было 77 наименований, от пшеничной муки до клубничного джема.
Подводя итоги своей работы в 1945 «Затраты на питание» : «По всей видимости не существует универсального метода нахождения минимума линейной функции при «соблюдении линейных ограничений.
Разработав в конце 40-х годов симплекс-метод, Георг Данциг совершил переворот. 70 лет назад решение задачи составления рациона вызывало затруднения у лучших экономистов мира, теперь доступно для начинающих студентов.
Задача о диете=Задача о смеси
Найти самую дешевую допустимую смесь.
3.3. Симплексный метод
Основная идея симплекс-метода
Ограничения ЗЛП в канонической форме приводятся к виду
x1 b1 a 1,r 1 xr 1 a 1,r 2 xr 2 a 1n xn
x b a x a x a x (*)
2 2 2,r 1 r 1 2,r 2 r 2 2n n
xr br a r,r 1 xr 1 a r,r 2 xr 2 a rn xn
Переменные (неизвестные) x1 , x2 , , xr называются базисными, а весь набор x1 , x2 , , xr – базисом, остальные переменные называются свободными. Базисное решение
называется допустимым, если оно неотрицательно.
Система ограничений (*) называется системой приведенной к единичному базису.
Отметим важнейшие условия наличия единичного базиса:
•от каждого уравнения в него входит одна и только одна неизвестная;
•каждая переменная из этого набора входит с коэффициентом +1 и отсутствует в остальных уравнениях;
•все значения bi >=0
23/23
3.3. Симплексный метод
Основная идея симплекс-метода
Подставляя в ЦФ | вместо базисных переменных их | ||||||||
выражения через свободные переменные из | |||||||||
системы | c x | (**) | |||||||
F c c x | r 1 | c | x | 2 | n | ||||
1 | r 2 | n | |||||||
Полагая все свободные переменные равными нулю, найдем значения базисных переменных
. | Получим | x b , x | b , , x | b | ||
x1 , x2 | , , xr | 2 | r | |||
1 1 | 2 | r | ||||
Если все значения bi >=0, то набор | b1,b2 , ,br ,0,…0 | является допустимым | ||||
решением ЗЛП. | ||||||
Такое допустимое решение называется базисным или опорным Значение ЦФ при этом равно F=c0
Основная идея симплекс-метода. Решение задачи при помощи симплекс-метода подразумевает ряд шагов, состоящих в том, что от данного базиса B’ переходим к
другому базису B’’ с таким расчетом, чтобы значение целевой функции F увеличивалось или, по крайней мере, не уменьшалось.FB’<=FB’’
24/23
3.3. Симплексный метод
Основная идея симплекс-метода
Геометрическая интерпретация.
Аналитическому переходу от одного базиса к другому соответствует переход от одной вершины многогранника (множества допустимых решений) к другой, в которой целевая функция имеет не меньшее значение. Этот факт основан на том, что вершинам многоугольника множества допустимых решений соответствуют базисные решения системы ограничений.
25/23
3.3. Симплексный метод
Исходные условия применения симплексного метода
1. ЗЛП записана в канонической форме
2. Её ограничения линейно независимы
3. Известно опорное решение, в котором:
имеется не более m ненулевых переменных |
• задача содержит n переменных и m ограничений |
все ограничения выполняются (область D не пуста!) |
4. m переменных, называемых базисными (среди которых все ненулевые)
выражены через:
n–m переменных, называемых свободными (каждая равна нулю)
свободный член ограничения bi положителен
5.Результат этой процедуры записан в начальную (первую, исходную) симплексную таблицу
Применение линейного программирования в математических моделях | 26/23 |
© Н.М. Светлов, 2007-2011 |
3.3 x1 0, x2 0) | |
z = max(x1+x2|0.1×1+0.2×2 | 5, x1–2×2 20, |
. Каноническая форма: |
max x1+x2 0.1×1+0.2×2+x3 = 5 x1–2×2 +x4 = 20
x1 0, x2 0, x3 0, x4 0
Симплекс-метод ЛП
Запись задачи в виде уравнений
x1 + a1,m+1xm+1 + … + a1sxs+…+ a1nxn = b1; x2 + a2,m+1xm+1 + … + a2sxs+…+ a2nxn = b2;
…
xm + am,m+1xm+1 + … + amsxs+…+ amnxn = bm.
тождественна записи в виде матриц
1 0 | .. 0 | a1,m+1 | .. a1s | .. a1n | x1 | b1 | |
0 1 | .. | a2,m+1 | .. a2s | .. a2n | x2 | = | b2 |
. . .. . . | .. . .. . | .. | .. | ||||
0 0 | .. | 1 | am,m+1 | .. ams .. amn | xn | bm | |
В симплекс-таблице будем записывать только коэффициенты матриц!
ПетрГУ, А.П.Мощевикин, 2004 г. | Теория принятия решений |
z = max(x1+x2|0.1×1+0.2×2 5, x1–2×2 20, x1 0, x2 0)
Каноническая форма:
max x1+x2 0.1×1+0.2×2+x3 = 5 x1–2×2 +x4 = 20
x1 0, x2 0, x3 0, x4 0
x1 | x2 | x3 |
x3 | 0,1 | 0,2 |
x4 | 1 | -2 |
F | -1 | -1 |
Смысл записей в симплекс-таблице:
F=0-(-1* x1-1*x2) x3 = 5- 0.1×1- 0.2×2
x4 = 20- x1+2×2
Полагая x1 = 0, x2 = 0,
F=0-(-1* x1-1*x2)=0 x3 = 5- 0.1×1-0.2×2 =5
x4 = 20- x1+2×2=20
29/23
Базисное решение
Разрешающий столбец: | ||||||
В таблице | ||||||
выделены | ||||||
столбец с наибольшим по модулю отрицательнжирнымом cj | ||||||
• если отрицательного cj нет, | шрифтом | |||||
достигнут оптимум | ||||||
Разрешающая строка: | ||||||
для всех положительных
aij в выбранном столбце считаем bi /aij
• если положительных нет, ц.ф. не ограничена
выбираем строку, где это значение минимально
x1 | x2 | x3 | x4 | b | вспом |
x3 | 0,1 | 0,2 | 1 | 5 | 50 |
x4 | 1 | -2 | 1 | 20 | 20 |
F | -1 | -1 |
Применение линейного программирования в математических моделях | 30/23 |
© Н.М. Светлов, 2007-2011 |
Выполняем обыкновенные жордановы исключения во всей таблице:
для строк i i’ : aijнов = aij – ai’jaij’ /ai’j’ , где
i’ и j’ – координаты ведущих (разрешающих) строки и столбца
для строки i =i’ : aijнов = aij /ai’j’
После 1 – ой итерации
x1 | x2 | x3 | x4 | b |
x3 | 0,4 | 1 | -0,1 | 3 |
x1 | 1 | -2 | 1 | 20 |
F | -3 | 1 | 20 |
= | старый | (элемент ведущего |
новый элемент | столбца)·(элемент ведущей строки) | |
элемент- | ведущий элемент | |
Светлов,
Источник