 |
АвтоАвтоматизацияАрхитектураАстрономияАудитБиологияБухгалтерияВоенное делоГенетикаГеографияГеологияГосударствоДомДругоеЖурналистика и СМИИзобретательствоИностранные языкиИнформатикаИскусствоИсторияКомпьютерыКулинарияКультураЛексикологияЛитератураЛогикаМаркетингМатематикаМашиностроениеМедицинаМенеджментМеталлы и СваркаМеханикаМузыкаНаселениеОбразованиеОхрана безопасности жизниОхрана ТрудаПедагогикаПолитикаПравоПриборостроениеПрограммированиеПроизводствоПромышленностьПсихологияРадиоРегилияСвязьСоциологияСпортСтандартизацияСтроительствоТехнологииТорговляТуризмФизикаФизиологияФилософияФинансыХимияХозяйствоЦеннообразованиеЧерчениеЭкологияЭконометрикаЭкономикаЭлектроникаЮриспунденкция
Задание 2. Для задачи линейного программирования, записанной в канонической форме, выбрать свободные переменные и выразить через них все остальные переменные
Для задачи линейного программирования, записанной в канонической форме, выбрать свободные переменные и выразить через них все остальные переменные. Построить ОДР или показать, что она не существует. В случае существования ОДР найти минимум целевой функции или показать, что задача не имеет решения.
Варианты задания 2 выдаются преподавателем.
Симплекс-метод для нахождения решения задачи линейного программирования
Основные понятия
Опорное решение – решение, лежащее в одной из вершин области допустимых решений (ОДР).
Стандартная форма записи уравнений ограничений – система уравнений, разрешенная относительно базисных переменных с коэффициентами при переменных, взятыми с обратными знаками относительно исходной системы.
Пример. Пять уравнений ограничений с четырьмя свободными переменными x 1, x 2, x 3, x 4, разрешенных относительно пяти базисных переменных y 1, y 2, y 3, y 4, y 5:
Здесь – aij = a ij (i = 1,…,5; j = 1,…,4)).
Стандартная таблица – таблица, составленная из коэффициентов стандартной формы записи уравнений ограничений. Первый столбец таблицы составлен из свободных членов, а остальные из коэффициентов при свободных переменных. Для удобства расчетов в стандартную таблицу добавляют строку коэффициентов для целевой функции также выраженную в стандартной форме:
L = с 0 – (g1x1 + g2x2 + g2x2 + g4 x 4), (– ci = g I, i = 1,…,4).
Пример. Для стандартной системы уравнений, приведенной выше, с добавлением строки для коэффициентов целевой функции стандартная таблица имеет вид:
| Свободный член | x 1 | x 2 | x 3 | x 4 | |
| L | с 0 | g1 | g2 | g3 | g4 |
| y 1 | b 1 | a11 | a12 | a13 | a14 |
| y 2 | b 2 | a21 | a22 | a23 | a24 |
| y 3 | b 3 | a31 | a32 | a33 | a34 |
| y 4 | b 4 | a41 | a42 | a43 | a44 |
| y 5 | b 5 | a51 | a52 | a53 | a54 |
Такую таблицу называют симплекс-таблицей.
Поиск по сайту: