Методы оптимальных решений
Решение:
Строим на плоскости х1Ох2 многоугольник решений. Для этого в неравенствах системы ограничений и условиях неотрицательности переменных знаки неравенств заменим на знаки точных равенств.
Каждую из четырех первых прямых строим по двум точкам. Соответствующую полуплоскость определяем по тому, принадлежит ей или нет точка начала координат (0; 0).
, - точка 1 -
, - точка 2 -
- область решения - верхняя полуплоскость;
, - точка 1 -
, - точка 2 -
- область решения - нижняя полуплоскость;
, - точка 1 -
, - точка 2 -
- область решения - нижняя полуплоскость;
, - точка 1 -
, - точка 2 -
- область решения - верхняя полуплоскость;
- ось,
- область решения - правая полуплоскость;
- ось,
- область решения - верхняя полуплоскость;
Построим полученные прямые, отметим стрелочками соответствующие полуплоскости допустимых значений переменных и их пересечение.
Областью допустимых решений задачи является четырехугольник ОABС, координаты точек которого удовлетворяют условию неотрицательности переменных и неравенствам системы ограничений задачи.
Х2 |
(V) | |||
(IV) | ||||
(III) | ||||
Z | ||||
B | ||||
A | ||||
1 | ||||
C |
Х1 | |||
-2 |
О |
0 |
1 |
(VI) |
-1 | ||||
(II) |
Z=0 | |||
(I) |
Для нахождения точек экстремума построим начальную прямую (по двум точкам: и ) и вектор-градиент, координаты которого являются частными производными целевой функции.
Для нахождения максимального значения целевой функции задачи перемещаем начальную прямую параллельно самой себе в направлении, вектора до последней точки пересечения ее с областью допустимых решений. Из рисунка следует, что опорной прямой по отношению к области допустимых решений она становится в точке В, где функция принимает максимальное значение. Для определения координат точки В - пересечения прямых (III) и (IV) - решим систему уравнений этих прямых:
В результате получили оптимальное решение ЗЛП на максимум:
Решить задачу линейного программирования симплекс-методом
Решение:
Задача обладает исходным опорным планом: , . Первый опорный план заносим в симплексную таблицу 1, состоящую из коэффициентов системы ограничений и свободных членов. Последняя строка заполняется по указанной в таблице формуле при.
Так как в этой оценочной строке находятся отрицательный элемент, то первый опорный план в задаче не оптимальный. Найдем разрешающий элемент:
; .
Значит, разрешающий элемент равен 4 в столбце. Выделим его в круг.
Переходим к новому опорному плану, формируя следующую симплексную таблицу 2. Вместо вектора в таблицу 2 войдет базисным вектор. Строка, соответствующая вектору, в таблице 2, получена делением всех элементов строки таблицы 1 на разрешающий элемент 4. На месте разрешающего элемента получаем 1. В остальных клетках столбца таблицы 2 получаем нули с помощью элементарных преобразований над строками матрицы. С помощью этих преобразований рассчитываются все строки таблицы 2, за исключением оценочной, которая вычисляется по указанной формуле.
Получили второй опорный план: , .
Базис |
СБ |
9 |
0 |
8 |
0 |
-1 |
0 | |
Таблица 1 |
0 |
2 |
1 |
4 |
0 |
2 |
0 | |
0 |
8 |
0 |
16 |
1 |
-2 |
0 | ||
0 |
3 |
0 |
5 |
0 |
0 |
1 | ||
-9 |
0 |
-8 |
0 |
1 |
0 | |||
Таблица 2 |
8 |
1/2 |
1/4 |
1 |
0 |
1/2 |
0 | |
0 |
0 |
-4 |
0 |
0 |
-10 |
0 | ||
0 |
1/2 |
-5/4 |
0 |
0 |
-5/2 |
1 | ||
-5 |
2 |
0 |
0 |
5 |
0 |
Так как в полученной оценочной строке таблицы 2 все коэффициенты неотрицательные, то второй опорный план является оптимальным.
Искомый оптимельный план: , .
Решить транспортную задачу
В следующих вариантах для транспортной задачи, исходные данные которой приведены в таблице, найти оптимальный план.
Пункты назначения
Пункты Отправления |
Запасы | ||||
4 |
5 |
2 |
8 |
6 |
115 |
3 |
1 |
9 |
7 |
3 |
185 |
9 |
6 |
7 |
2 |
1 |
120 |
Потребности |
70 |
220 |
40 |
30 |
60 |
Решение:
Проверяем необходимое и достаточное условие разрешимости задачи:
, .
Как видно, суммарная потребность в грузе равна его запасам у поставщиков. Следовательно, модель транспортной задачи является закрытой и задача разрешима. Решаем ее методом потенциалов.
Все исходные данные заносим в следующую таблицу 1.
Таблица 1
4 |
5 |
2 |
1 |
0 |
Запасы | |
0 |
|
|
|
|
|
115 |
-4 |
|
|
|
|
|
185 |
1 |
|
|
|
|
|
120 |
Потребности |
70 |
220 |
40 |
30 |
60 |
420 |
Построим первый опорный план методом минимальной стоимости.
В клетку с минимальным тарифом направляем максимально возможный груз, равный. Строка выходит из рассмотрения.
Среди оставшихся тарифов минимальный элемент в клетке. Направляем в нее груз, равный. При этом столбец выходит из рассмотрения. задача полуплоскость потенциал оптимальность
Продолжая аналогичным образом рассуждения, получаем первый опорный план, который является допустимым, так как все грузы с пунктов поставки вывезены, и потребности всех пунктов назначения удовлетворены.
Проверяем невырожденность плана.
Число базисных переменных в невырожденном плане равно. Первый опорный план является невырожденным, так как число занятых клеток равно 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 руб.
Полученный оптимальный план данной задачи является единственным. Признаком этого является отсутствие нулевых оценок свободных клеток.
Похожие статьи
-
Математическая модель транспортной задачи: F = ??cIjXIj, (1) При условиях: ?xIj = aI, i = 1,2,..., m, (2) ?xIj = bJ, j = 1,2,..., n, (3)...
-
A 25 40 50 30 45 20 7 3 4 8 6 60 5 7 2 3 5 45 1 4 10 2 6 70 3 4 2 7 8 Допустим, стоимость доставки единицы груза из каждого пункта отправления в...
-
РЕШЕНИЕ ЗАДАЧИ О КОММИВОЯЖЕРЕ МЕТОДОМ ВЕТВЕЙ И ГРАНИЦ. ПРИМЕРЫ - Задача коммивояжера
Рассмотрим конкретный пример реализации метода ветвей и границ для решения задачи о коммивояжере. Итак, требуется найти легчайший простой основный...
-
Условие задачи. Пусть имеются n кандидатов для выполнения этих работ. Назначение кандидата i на работу j связано с затратами CIj (i, j = 1,2,..., n)....
-
Решение транспортной задачи методом потенциалов - Математическая модель решения транспортной задачи
Этот метод позволяет автоматически выделять циклы с отрицательной ценой и определять их цены. Пусть имеется транспортная задача с балансовыми условиями...
-
Метод дифференциальных рент для решения транспортной задачи - Формирование оптимального штата фирмы
Для решения транспортных задач используется несколько методов. Рассмотрим решение с помощью метода дифференциальных рент. При нахождении решения...
-
Элементы матричного анализа - Методы решения системы линейных уравнений
Вектором, как на плоскости, так и в пространстве, называется направленный Отрезок , то есть такой Отрезок , один из концов которого выделен и называется...
-
Геометрическая интерпретация и графическое решение ЗЛП - Экономико-математические методы
Геометрическая интерпретация экономических задач дает возможность наглядно представить их структуру, выявить особенности и открывает пути исследования...
-
Исходная задача: При ограничениях: Двойственной является следующая задача: При ограничениях: Число неизвестных в двойственной задаче равно 2....
-
Задача о загрузке рюкзака (задача о ранце) - Метод динамического программирования для решения задач
Постановка задачи. Пусть имеются N видов грузов с номерами. Единица груза j-го вида имеет все aJ. Если груз j-го вида берется в количестве xJ, то его...
-
Решение симплекс-методом с помощью симплекс-таблиц - Математические методы и модели в экономике
Определим оптимальный план выпуска продукции, решив задачу линейного программирования (ЗЛП). Для этого сначала приведем модель к каноническому виду...
-
Метод северо-западного угла - Математическое моделирование в менеджменте и маркетинге
Этап I. Поиск первого опорного плана . 1. Используя метод северо-западного угла, построим первый опорный план транспортной задачи. План начинается...
-
Теория: Применяется, как правило, для задач линейного программирования, содержащих не более 2 переменных. Суть геометрического метода сводится к...
-
Решим прямую задачу линейного программирования симплексным методом, с использованием симплексной таблицы. Определим максимальное значение целевой...
-
В разделе 1 курсовой работы требуется: Определить количество закупаемого заданным филиалом фирмы сырья у каждого АО, (xj), максимизируя прибыль филиала....
-
Необходимо найти минимальное значение целевой функции F = 4x1+18x2 > min, при системе ограничений: X1+4x2?14(1) X1+6x2?15(2) X1+x2?5(3)...
-
РЕШЕНИЕ ЗАДАЧИ О КОММИВОЯЖЕРЕ МЕТОДОМ ВЕТВЕЙ И ГРАНИЦ: ОСНОВНАЯ СХЕМА - Задача коммивояжера
Пусть - конечное множество и - вещественно-значная функция на нем; требуется найти минимум этой функции и элемент множества, на котором этот минимум...
-
Некоторые особенности решения задач нелинейного программирования - Экономико-математические методы
Для решения ЗНП существенно знать: 1) выпукло или не выпукло множество допустимых решений задачи; 2) является ли целевая функция выпуклой или вогнутой...
-
Пример решения транспортной задачи - Экономико-математические методы
На четырех строительных площадках В1, В2, В3, В4 монтируется в день соответственно 20,120,20 60 м3 сборных плит перекрытий. Производство этих плит...
-
Алгоритм решения ТЗ методом потенциалов - Экономико-математические методы
Построить опорный план по одному из правил. Проверить план на невырожденность. Если полученный план вырожденный, формально заполняют нулями некоторые из...
-
Динамическое программирование Динамическое программирование -- один из разделов оптимального программирования, в котором процесс принятия решения и...
-
В этом случае лучшим считается вариант, у которого суммарная величина отдельных целевых функций принимает максимальное значение: F Max = = max...
-
Календарный производственный программирование однооперационный Все существующие методы решения задач календарного планирования3 по степени достижения...
-
Введение - Решение оптимизационных экономических задач методами линейного программирования
Линейное программирование является составной частью раздела математики, который изучает методы нахождения условного экстремума функции многих переменных...
-
Большое число экономических и планово-производственных задач связано с распределением каких-либо, как правило, ограниченных ресурсов (сырья, рабочей...
-
Оптимальное решение модели. - Методика решения задачи целочисленного программирования
Рис. 1 Шаг 1. Исходную задачу 1 заносим в дерево задач. В качестве исходного допустимого решения берем: x1=x2=x3=0. Соответствующее значение целевой...
-
Второй раздел курсовой работы посвящен особенностям постановки и решения общей задачи линейного программирования, а именно, транспортной задаче (ТЗЛП)....
-
Вариации коэффициентов целевой функции ЗЛП приводят к изменению направления вектора градиента. Так как при этом не затрагивается допустимое множество, то...
-
Известно оптимальное решение X*=(0;0;1;1) задачи линейного программирования: Составьте двойственную задачу и найдите ее оптимальное решение по теореме...
-
Решение задачи графическим методом - Математическое моделирование в менеджменте и маркетинге
Необходимо найти максимальное значение целевой функции L(x)= 2x1+2x2 > max, при системе ограничений: 6x1+8x2?48, (1) 8x1+11x2?88, (2)...
-
Вид сырья Запас сырья Количество единиц сырья, идущих на изготовление единицы продукции P1 P2 P3 P4 S1 4 1 1 1 3 S2 18 2 4 6 1 Прибыль от единицы...
-
Это раздел математического программирования, изучающий методы решения таких экстремальных задач, в которых результаты (эффективность) возрастают или...
-
При решении экономических задач часто анализировать ситуации, в которых сталкиваются интересы двух или более конкурирующих сторон, преследующих различные...
-
Как известно решение задач симплексным методом применяется очень часто. Это связано с тем, что симплексный метод подходит для решения широкого круга...
-
Необходимость введения нового ограничения может возникнуть, например, когда первоначально для сокращения затрат машинного времени некоторые интуитивно...
-
Неопределенность - это фундаментальное свойство природы, а еще более (и точнее) - свойство, характеризующее неточность, незамкнутость, неокончательность,...
-
Пусть имеется оптимизационная задача вида: (1) (2) (3) - задан(4) Здесь предполагается, что FJ(xJ,yJ)>0 для всех допустимых значений xJ,yJ. В этом случае...
-
Параметрическое линейное программирование - Методы линейного программирования
Представляет собой один из разделов математического программирования, изучающий задачи, в которых целевая функция или ограничения зависят от одного или...
-
Транспортные задачи, имеющие некоторые усложнения в постановке - Экономико-математические методы
Транспортная задача с избытком запасов: Для отыскания оптимального плана вводят фиктивный (n+1)-й пункт назначения Bn+1 с потребностью bn+1 и полагают...
-
Изучение теоретических вопросов анализа чувствительности оптимального решения ЗЛП к вариациям некоторых параметров задачи и введению нового ограничения....
Методы оптимальных решений