Графический метод и симплекс-метод решения задач линейного программирования
Информация - Экономика
Другие материалы по предмету Экономика
?ок таблицы.
a.Все элементы ведущей строки делим на ведущий элемент и записываем в той же строке новой симплекс- таблицы.
Полученную строку p1 назовем разрешающей.
b.К оставшейся второй строке прибавим разрешающую строку, умноженную на такое число, чтобы элемент, стоящий в ведущем столбце обратился в ноль.
p2 = p2 + (- 2) p1 = p2 - p1.
c.Заполним последнюю строку, вычислив оценки ?j = .
Получим вторую симплекс-таблицу с новым базисом.
Таблица 3 - Результат первой итерации
cББазисные перемен.с1=1с2=2с3=0с4=0Значения базисных перем.Уравненияx1x2x3x 4c2=2x2-1/211/202p1 =p1/2c4=0x440-118p2 =p2 - p1оценки ?j-2010f(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 = .
Таблица 4 - Результат второй итерации
cББазисн. перемен.с1=1с2=2с3=0с4=0Значения базисных перем.уравненияx1x2x3x 4c2=2x2013/81/83p1=p1+p2/2c1=1x110-1/41/42p2 = p2/4оценки ?j001/21/2f(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