КАТЕГОРИИ:
АстрономияБиологияГеографияДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРиторикаСоциологияСпортСтроительствоТехнологияФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника
|
Рассмотрите пример решения задачи линейного программирования симплекс-методом
Пример решения задачи линейного программирования.Рассмотрим задачу линейного программирования в следующем виде: найти максимум линейной формы 4х1 + 3х2 при ограничениях х1 ≤4000, х2 ≤ 6000, х1 +2/3х2 ≤6000, х1,х2 ≥ 0. Каноническая форма задачи линейного программирования будет иметь вид 4x1 + 3x2 + 0x3 + 0x4 + 0x5 → max; 1х1 + 0х2 + 1х3 + 0x4 +0x5 = 4000; 0x1 +1х2 +0 х3 +1 x4+0 x5 = 6000;
Составим исходную симплекс-таблицу (табл. 10.2). Таблица 10.2
Поскольку -4 < -3 < 0, то в качестве направляющего выбираем первый столбец. Составив отношение вида , определяем направляющую строку, Для этого находим минимальное отношение Следовательно, направляющая строка - первая, направляющий элемент — а11=1. Применив первый шаг симплексного преобразования, получим новую таблицу (табл. 10.3). Таблица 10.3 На данном этапе в качестве направляющего столбца выбираем второй, направляющая строка - третья, т.к. Применим следующий шаг симплексного преобразования. В результате получим табл. 10.4
Так как то направляющий столбец А3, направляющая строка - вторая, направляющий элемент а23= 3/2 • Выполним очередной шаг преобразования, получим еще одну таблицу (табл. 10.5).
Таблица 10.5 Поскольку в индексной строке все элементы положительны, это означает, что найдено оптимальное решение х10= 2000, х20 = 6000, х30 = 2000. Искомое значение целевой функции равно 4 х1 + Зх2= 26000.
|