c. Заполним последнюю строку, вычислив оценки j' = < cБ', Aj' > - - cj,где cБ', Aj' - соответствующие столбцы новой симплекс-таблицы, и значение целевой функции f(x)= < cБ', xБ' >.
Получим вторую симплекс-таблицу с новым базисом.
Таблица 3 - Результат первой итерации
| cБ' | Базисные перемен. | с1=1 | с2=2 | с3=0 | с4=0 | Значения базисных перем. | Уравнения |
| x1 | x2 | x3 | x 4 | ||||
| c2=2 | x2 | –1/2 | 1 | 1/2 | 0 | 2 | p1' =p1/2 |
| c4=0 | x4 | 4 | 0 | -1 | 1 | 8 | p2' =p2 - p1 |
| оценки j' | –2 | 0 | 1 | 0 | f(x')=4 | ||
Новый базисный план x' = (0, x2,0, x4) = (0, 2, 0, 8).
Поскольку оценка 1= -2 < 0, то план x'не оптимален. Для перехода к новому базисному плану (соседней угловой точки) проведем еще одну итерацию симплекс - метода.
Так как 1 < 0, то в базис вводится переменная x1.Первый столбец, содержащий x1 - ведущий.
Находим отношения компонент базисного плана к соответствующим положительным элементам ведущего столбца и в качестве ведущей строки берем строку с наименьшим отношением. В таблице 2 в ведущем столбце только второй элемент больше нуля (= 4), следовательно, вторая строка будет ведущей, а расположенная в ней базисная переменная x4подлежит исключению из базиса.
Выделяем ведущий столбец и ведущую строку и на их пересечении находим ведущий элемент (= 4).
Строим новую (третью) симплекс-таблицу, заменяя в ней базисную переменную x4 на x1, и снова преобразуя строки таблицы таким образом, чтобы ведущий элемент стал равным единице, а остальные элементы ведущего столбца обратились в ноль. Для этого ведущую (вторую) строку делим на 4, а к первой строке прибавляем полученную вторую строку, деленную на 2. Последнюю строку вычисляем по формулам для симплексных оценок j'' = < cБ'', Aj'' > - cj,где cБ'', Aj'' - соответствующие столбцы новой симплекс-таблицы. Значение целевой функции на новом базисном плане находим по формуле f(x'')= < cБ'', xБ'' >.
Таблица 4 - Результат второй итерации
| cБ'' | Базисн. перемен. | с1=1 | с2=2 | с3=0 | с4=0 | Значения базисных перем. | уравнения |
| x1 | x2 | x3 | x 4 | ||||
| c2=2 | x2 | 0 | 1 | 3/8 | 1/8 | 3 | p1''=p1'+p2''/2 |
| c1=1 | x1 | 1 | 0 | -1/4 | 1/4 | 2 | p2'' = p2'/4 |
| оценки j'' | 0 | 0 | 1/2 | 1/2 | f(x'')= 8 | ||
Новый базисный план x'' = (x1, x2,0, 0) = (2, 3, 0, 0). Поскольку все оценки неотрицательны, то план x'' - оптимальный план.
Таким образом, x* = (2, 3, 0, 0), f(x*) = 8.
Рассмотренные способы решения задач линейного программирования широко используются на практике. Однако следует отметить, что математическая модель всегда беднее реальной экономической системы. Она описывает эту систему лишь приблизительно, выделяя одни свойства и пренебрегая другими. Для компенсации указанного недостатка в математической экономике разрабатывается несколько типов моделей, каждый из которых призван отразить какую-то одну определённую сторону экономической действительности с тем, чтобы при решении конкретной экономической задачи можно было подобрать такую модель, которая лучше всего к ней подходит.
1. Ашманов С.А. Линейное программирование. – М.: Наука, 1981.
2. Кузнецов Ю.Н., Кузубов В.И., Волощенко А.Б. Математическое программирование. – М.: Высшая школа, 1980.
3. Калихман И.Л. Линейная алгебра и программирование. – М.: Высшая школа, 1967.
4. Нит И.В. Линейное программирование. – М.: Изд-во МГУ, 1978.
5. Юдин Д.Б., Гольштейн Е.Г. Линейное программирование. Теория и конечные методы. – М.: Физматиз, 1963.
6. Тарасенко Н.В. Математика-2. Линейное программирование: курс лекций. – Иркутск: изд-во БГУЭП, 2003.
7. Математическое программирование в примерах и задачах: Учеб. пособие. – 2-е изд., испр. и доп. – М.: Высш. шк., 1993. – 336 с.
8. www.yandex.ru
9. www.mathematica.ru
10. www.monax.ru