![]() |
![]() |
Мастерская программиста Гирича Семёна Николаевича Решение задач линейного программирования |
|||||||||||
![]() |
|||||||||||||
|
|||||||||||||
![]() |
4.3. Пример решения ЦЗЛП с применением метода Гомори |
Задача: Вариант №4 Математическая модель задачи: Целевая функция: Система
ограничений: x1,x2 >=0; - условие неотрицательности переменных. Решение задачи с использованием метода симплекс-таблиц. Математическая модель задачи: Целевая функция: Система ограничений: x1,x2, >=0; - условие неотрицательности переменных. Система неравенств приведена к каноническому виду: Целевая функция: Система ограничений: Векторный анализ системы ограничений: Расширенная целевая функция: Вектора:
Базис: Расширенная целевая функция: Заполним первую таблицу: Таблица №1
Невозможно выбрать столбец замещения, так как нет положительных dj! Выберем столбец таким образом. Чтобы избавиться от недопустимого решения, т.е. от отрицательных значений в столбце свободных членов (Р0). Замещаемый базисный вектор: P3 (1-я строка) Новый базисный вектор: P1 (1-й столбец) Заменяем базисный вектор P3 на P1. Таблица №2
Невозможно выбрать столбец замещения, так как нет положительных dj! Выберем столбец таким образом. Чтобы избавиться от недопустимого решения, т.е. от отрицательных значений в столбце свободных членов (Р0). Замещаемый базисный вектор: P5 (3-я строка) Новый базисный вектор: P2 (2-й столбец) Заменяем базисный вектор P5 на P2. Таблица №3
Макс. целая часть дробного свободного члена при базисном векторе P2 (3-я строка). Составим уравнение ограничения и добавим в таблицу новый базисный вектор по новому уравнению и новой переменной. Добавляем базисный вектор: P6 (6-й столбец) Таблица №4
Невозможно выбрать столбец замещения, так как нет положительных dj! Выберем столбец таким образом. Чтобы избавиться от недопустимого решения, т.е. от отрицательных значений в столбце свободных членов (Р0). Замещаемый базисный вектор: P6 (4-я строка) Новый базисный вектор: P5 (5-й столбец) Заменяем базисный вектор P6 на P5. Таблица №5
Невозможно выбрать столбец замещения, так как нет положительных dj! Получено оптимальное решение! Из таблицы получим значения переменных целевой функции:
Целевая функция: S min = 6*5+1*6 И в результате: S min = 36; Задача решена. |
|
![]() |
![]() |
![]() |
|||||
© 2011 Семён Гирич, |
|
![]() ![]() |
|||||
![]() |
![]() |
![]() |