Методы оптимальных решений

Размещено на http://www.allbest.ru/

КОНТРОЛЬНАЯ РАБОТА

МЕТОДЫ ОПТИМАЛЬНЫХ РЕШЕНИЙ

Решить графически задачу линейного программирования

Решение:

Строим на плоскости х₁Ох₂ многоугольник решений. Для этого в неравенствах системы ограничений и условиях неотрицательности переменных знаки неравенств заменим на знаки точных равенств.

Каждую из четырех первых прямых строим по двум точкам. Соответствующую полуплоскость определяем по тому, принадлежит ей или нет точка начала координат (0; 0).

, - точка 1 -

, - точка 2 -

- область решения - верхняя полуплоскость;

, - точка 1 -

, - точка 2 -

- область решения - нижняя полуплоскость;

, - точка 1 -

, - точка 2 -

- область решения - нижняя полуплоскость;

, - точка 1 -

, - точка 2 -

- область решения - верхняя полуплоскость;

- ось ,

- область решения - правая полуплоскость;

- ось ,

- область решения - верхняя полуплоскость;

Построим полученные прямые, отметим стрелочками соответствующие полуплоскости допустимых значений переменных и их пересечение.

Областью допустимых решений задачи является четырехугольник ОABС, координаты точек которого удовлетворяют условию неотрицательности переменных и неравенствам системы ограничений задачи.

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

Для нахождения максимального значения целевой функции задачи перемещаем начальную прямую параллельно самой себе в направлении, вектора до последней точки пересечения ее с областью допустимых решений. Из рисунка следует, что опорной прямой по отношению к области допустимых решений она становится в точке В, где функция принимает максимальное значение. Для определения координат точки В - пересечения прямых (III) и (IV) - решим систему уравнений этих прямых:

В результате получили оптимальное решение ЗЛП на максимум:

Решить задачу линейного программирования симплекс-методом

Решение:

Задача обладает исходным опорным планом: , . Первый опорный план заносим в симплексную таблицу 1, состоящую из коэффициентов системы ограничений и свободных членов. Последняя строка заполняется по указанной в таблице формуле при .

Так как в этой оценочной строке находятся отрицательный элемент, то первый опорный план в задаче не оптимальный. Найдем разрешающий элемент:

; .

Значит, разрешающий элемент равен 4 в столбце . Выделим его в круг.

Переходим к новому опорному плану, формируя следующую симплексную таблицу 2. Вместо вектора в таблицу 2 войдет базисным вектор . Строка, соответствующая вектору , в таблице 2, получена делением всех элементов строки таблицы 1 на разрешающий элемент 4. На месте разрешающего элемента получаем 1. В остальных клетках столбца таблицы 2 получаем нули с помощью элементарных преобразований над строками матрицы. С помощью этих преобразований рассчитываются все строки таблицы 2, за исключением оценочной, которая вычисляется по указанной формуле.

Получили второй опорный план: , .

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

Искомый оптимельный план: , .

Решить транспортную задачу

В следующих вариантах для транспортной задачи, исходные данные которой приведены в таблице, найти оптимальный план.

Пункты назначения

Решение:

Проверяем необходимое и достаточное условие разрешимости задачи:

, .

Как видно, суммарная потребность в грузе равна его запасам у поставщиков. Следовательно, модель транспортной задачи является закрытой и задача разрешима. Решаем ее методом потенциалов.

Все исходные данные заносим в следующую таблицу 1.

Таблица 1

Построим первый опорный план методом минимальной стоимости.

В клетку с минимальным тарифом направляем максимально возможный груз, равный . Строка выходит из рассмотрения.

Среди оставшихся тарифов минимальный элемент в клетке . Направляем в нее груз, равный . При этом столбец выходит из рассмотрения. задача полуплоскость потенциал оптимальность

Продолжая аналогичным образом рассуждения, получаем первый опорный план, который является допустимым, так как все грузы с пунктов поставки вывезены, и потребности всех пунктов назначения удовлетворены.

Проверяем невырожденность плана.

Число базисных переменных в невырожденном плане равно . Первый опорный план является невырожденным, так как число занятых клеток равно 7.

Проверяем условие оптимальности.

Для этого находим потенциалы по занятым клеткам таблицы 1 из систему уравнений:

(1).

Так как число неизвестных больше числа уравнений (m+n>m+n-1), то один из потенциалов принимаем равным нулю (). Рассчитанные потенциалы заносим в таблицу 1 и определяем оценки свободных клеток по формулам:

(2).

Заносим их в левые нижние углы свободных клеток таблицы.

Так как все оценки , то первый опорный план транспортной задачи является оптимальным.

Значение целевой функции:

.

Оптимальный план:

,

Анализ плана.

Из первого пункта поставки необходимо 70 ед. груза направить в 1-й, 5 ед. - во 2-й и 40 ед. - в 3-й пункт назначения; из второго пункта поставки все 185 ед. груза направить во 2-й пункт назначения; из третьего пункта поставки 30 ед. груза направить во 2-й, 30 ед. - в 4-й и 60 ед. в 5-й пункт назначения. Потребности потребителей удовлетворены полностью, и весь груз вывезен. Общая стоимость доставки груза потребителям будет минимальной и составит 870 руб.

Полученный оптимальный план данной задачи является единственным. Признаком этого является отсутствие нулевых оценок свободных клеток.

Размещено на Allbest.ru