Студопедия

Главная страница Случайная страница

Разделы сайта

АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника






Пример 3.4.






.

1. Система приведена к каноническому виду (см. раздел 2).

2. Ранг основной и расширенной матрицы r = 3, тогда в соответствии с теоремой Кронекера-Капелли система совместна и базис относительно переменных х 1, х 2, х 3 уже выделен. Свободные члены после выражения базисных переменных остаются положительными.

Целевая функция выражена через свободные переменные х 4 и х 5 и стремится к min.

3. Приравниваем свободные переменные х 4 и х 5 к нулю и получим начальное опорное решение

для которого . Все вышеперечисленные действия представляют собой 0-й шаг. Обращаем внимание, что свободные переменные равны нулю, а базисные переменные приняли положительные значения.

4. На 1-м шаге попытаемся уменьшить значение f (), что можно добиться только увеличением значения х 5, так как оно стоит со знаком «–». Увеличим значение х 5 так, чтобы х 1, х 2, х 3 не стали отрицательными, оставив х 4 = 0. Из 2-го уравнения системы следует, что х 5 можно увеличить до 2. Т. о., получаем новое решение = (5, 0, 1, 0, 2) и f () = – 2 уменьшилось.

На 2-м шаге за свободные переменные принимают х 2и х 4 (нулевые значения в ), а остальные переменные за новый базис х 1, х 3, х 5 (ненулевые значения в ). Для этого из 2-го уравнения системы выражают х 5 через х 2 и х 4. Базисные переменные х 1, х 3 и целевую функцию f () также выражаем через новые свободные переменные х 2и х 4.

 

.

Для уменьшения будем увеличивать х 4. Из системы видно, что при условии неотрицательности х 3 (х 2=0) значение х 4 можно увеличить до х 4= (третье уравнение). Тогда новое допустимое решение =(, 0, 0, , ) и f () = – .

3-й шаг. Свободные переменные х 2 и х 3, а базисные х 1, х 4, х 5. Из третьего уравнения выражаем х 4 через х 2 и х 3, а в первом и третьем уравнениях делаем преобразования с учетом выражения х 4 через х 2 и х 3. Кроме того, преобразовываем значение целевой функции с учетом выражения х 4 через х 2 и х 3. Получим:

Т. к. в последнее выражение целевой функции все переменные входят с положительными коэффициентами, то её наименьшее значение достигается при х 2 = 0, х 3 = 0. Это означает что решение = (, 0, 0, , ) является оптимальным, т.е. f min() = – .

Анализируя ход решения, т.е. минимизацию, можно сделать выводы:

1. Если все коэффициенты при свободных неизвестных в выражении для целевой функции положительны (неотрицательны), то значение , равное значению свободного члена (константы), является минимальным, а базисное решение – оптимальным.

2. Если в целевой функции имеется свободная переменная с отрицательным коэффициентом, а в системе при этом неизвестном все коэффициенты положительны, то задача решения не имеет.

3. Если в целевой функции имеется свободная переменная, коэффициент при которой отрицателен, и в системе уравнений при этой переменной также имеется хотя бы один отрицательный коэффициент, то оптимальное решение может быть найдено посредством проведения итераций.

 






© 2023 :: MyLektsii.ru :: Мои Лекции
Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав.
Копирование текстов разрешено только с указанием индексируемой ссылки на источник.