Симплексный метод решения задач ЛП - Решение оптимизационных экономических задач методами линейного программирования
Вид сырья |
Запас сырья |
Количество единиц сырья, идущих на изготовление единицы продукции | |||
P1 |
P2 |
P3 |
P4 | ||
S1 |
4 |
1 |
1 |
1 |
3 |
S2 |
18 |
2 |
4 |
6 |
1 |
Прибыль от единицы продукции |
9 |
14 |
15 |
5 |
Решим прямую задачу линейного программирования симплексным методом, с использованием симплексной таблицы.
Определим максимальное значение целевой функции F(X) = 9x1 + 14x2 + 15x3 + 5x4 при следующих условиях ограничений.
X1 + x2 + x3 + x4?4
2x1 + 4x2 + 6x3 + x4?18
Для построения первого опорного плана систему неравенств приведем к системе уравнений путем введения дополнительных переменных (Переход к канонической форме).
В 1-м неравенстве смысла (?) вводим базисную переменную x5. В 2-м неравенстве смысла (?) вводим базисную переменную x6.
- 1x1 + 1x2 + 1x3 + 1x4 + 1x5 + 0x6 = 4 2x1 + 4x2 + 6x3 + 1x4 + 0x5 + 1x6 = 18
Матрица коэффициентов A = a(ij) этой системы уравнений имеет вид:
Базисные переменные это переменные, которые входят только в одно уравнение системы ограничений и притом с единичным коэффициентом.
Решим систему уравнений относительно базисных переменных:
X5, x6,
Полагая, что Свободные переменные равны 0, получим первый опорный план:
X1 = (0,0,0,0,4,18)
Базисное решение называется допустимым, если оно неотрицательно.
Базис |
B |
X1 |
X2 |
X3 |
X4 |
X5 |
X6 |
X5 |
4 |
1 |
1 |
1 |
1 |
1 |
0 |
X6 |
18 |
2 |
4 |
6 |
1 |
0 |
1 |
F(X0) |
0 |
-9 |
-14 |
-15 |
-5 |
0 |
0 |
Переходим к основному алгоритму симплекс-метода.
Итерация №0.
1. Проверка критерия оптимальности.
Текущий опорный план неоптимален, так как в индексной строке находятся отрицательные коэффициенты.
2. Определение новой базисной переменной.
В качестве ведущего выберем столбец, соответствующий переменной x3, так как это наибольший коэффициент по модулю.
3. Определение новой свободной переменной.
Вычислим значения DI по строкам как частное от деления: bI / aI3
И из них выберем наименьшее:
Min (4 : 1 , 18 : 6 ) = 3
Следовательно, 2-ая строка является ведущей.
Разрешающий элемент равен (6) и находится на пересечении ведущего столбца и ведущей строки.
Базис |
B |
X1 |
X2 |
X3 |
X4 |
X5 |
X6 |
Min |
X5 |
4 |
1 |
1 |
1 |
1 |
1 |
0 |
4 |
X6 |
18 |
2 |
4 |
6 |
1 |
0 |
1 |
3 |
F(X1) |
0 |
-9 |
-14 |
-15 |
-5 |
0 |
0 |
0 |
4. Пересчет симплекс-таблицы.
Формируем следующую часть симплексной таблицы.
Вместо переменной x в план 1 войдет переменная x3 .
Строка, соответствующая переменной x3 В плане 1, получена в результате деления всех элементов строки x6 плана 0 на разрешающий элемент РЭ=6
На месте разрешающего элемента в плане 1 получаем 1.
В остальных клетках столбца x3 Плана 1 записываем нули.
Таким образом, в новом плане 1 заполнены строка x3 И столбец x3 .
Все остальные элементы нового плана 1, включая элементы индексной строки, определяются по правилу прямоугольника.
Для этого выбираем из старого плана четыре числа, которые расположены в вершинах прямоугольника и всегда включают разрешающий элемент РЭ.
НЭ = СЭ - (А*В)/РЭ
СТЭ - элемент старого плана, РЭ - разрешающий элемент (6), А и В - элементы старого плана, образующие прямоугольник с элементами СТЭ и РЭ.
Представим расчет каждого элемента в виде таблицы:
B |
X 1 |
X 2 |
X 3 |
X 4 |
X 5 |
X 6 |
4-(18 * 1):6 |
1-(2 * 1):6 |
1-(4 * 1):6 |
1-(6 * 1):6 |
1-(1 * 1):6 |
1-(0 * 1):6 |
0-(1 * 1):6 |
18 : 6 |
2 : 6 |
4 : 6 |
6 : 6 |
1 : 6 |
0 : 6 |
1 : 6 |
0-(18 * -15):6 |
-9-(2 * -15):6 |
-14-(4 * -15):6 |
-15-(6 * -15):6 |
-5-(1 * -15):6 |
0-(0 * -15):6 |
0-(1 * -15):6 |
Получаем новую симплекс-таблицу:
Базис |
B |
X1 |
X2 |
X3 |
X4 |
X5 |
X6 |
X5 |
1 |
2/3 |
1/3 |
0 |
5/6 |
1 |
-1/6 |
X3 |
3 |
1/3 |
2/3 |
1 |
1/6 |
0 |
1/6 |
F(X1) |
45 |
-4 |
-4 |
0 |
-21/2 |
0 |
21/2 |
Итерация №1.
1. Проверка критерия оптимальности.
Текущий опорный план неоптимален, так как в индексной строке находятся отрицательные коэффициенты.
2. Определение новой базисной переменной.
В качестве ведущего выберем столбец, соответствующий переменной x2, так как это наибольший коэффициент по модулю.
3. Определение новой свободной переменной.
Вычислим значения DI по строкам как частное от деления: bI / aI2
И из них выберем наименьшее:
Min (1 : 1/3 , 3 : 2/3 ) = 3
Следовательно, 1-ая строка является ведущей.
Разрешающий элемент равен (1/3) и находится на пересечении ведущего столбца и ведущей строки.
Базис |
B |
X1 |
X2 |
X3 |
X4 |
X5 |
X6 |
Min |
X5 |
1 |
2/3 |
1/3 |
0 |
5/6 |
1 |
-1/6 |
3 |
X3 |
3 |
1/3 |
2/3 |
1 |
1/6 |
0 |
1/6 |
41/2 |
F(X2) |
45 |
-4 |
-4 |
0 |
-21/2 |
0 |
21/2 |
0 |
4. Пересчет симплекс-таблицы.
Формируем следующую часть симплексной таблицы.
Вместо переменной x в план 2 войдет переменная x2 .
Строка, соответствующая переменной x2 В плане 2, получена в результате деления всех элементов строки x5 плана 1 на разрешающий элемент РЭ=1/3
На месте разрешающего элемента в плане 2 получаем 1.
В остальных клетках столбца x2 Плана 2 записываем нули.
Таким образом, в новом плане 2 заполнены строка x2 И столбец x2 .
Все остальные элементы нового плана 2, включая элементы индексной строки, определяются по правилу прямоугольника.
Представим расчет каждого элемента в виде таблицы:
B |
X 1 |
X 2 |
X 3 |
X 4 |
X 5 |
X 6 |
1 : 1/3 |
2/3 : 1/3 |
1/3 : 1/3 |
0 : 1/3 |
5/6 : 1/3 |
1 : 1/3 |
-1/6 : 1/3 |
3-(1 * 2/3):1/3 |
1/3-(2/3 * 2/3):1/3 |
2/3-(1/3 * 2/3):1/3 |
1-(0 * 2/3):1/3 |
1/6-(5/6 * 2/3):1/3 |
0-(1 * 2/3):1/3 |
1/6-(-1/6 * 2/3):1/3 |
45-(1 * -4):1/3 |
-4-(2/3 * -4):1/3 |
-4-(1/3 * -4):1/3 |
0-(0 * -4):1/3 |
-21/2-(5/6 * -4):1/3 |
0-(1 * -4):1/3 |
21/2-(-1/6 * -4):1/3 |
Получаем новую симплекс-таблицу:
Базис |
B |
X1 |
X2 |
X3 |
X4 |
X5 |
X6 |
X2 |
3 |
2 |
1 |
0 |
21/2 |
3 |
-1/2 |
X3 |
1 |
-1 |
0 |
1 |
-11/2 |
-2 |
1/2 |
F(X2) |
57 |
4 |
0 |
0 |
71/2 |
12 |
1/2 |
1. Проверка критерия оптимальности.
Среди значений индексной строки нет отрицательных. Поэтому эта таблица определяет оптимальный план задачи.
Окончательный вариант симплекс-таблицы:
Базис |
B |
X1 |
X2 |
X3 |
X4 |
X5 |
X6 |
X2 |
3 |
2 |
1 |
0 |
21/2 |
3 |
-1/2 |
X3 |
1 |
-1 |
0 |
1 |
-11/2 |
-2 |
1/2 |
F(X3) |
57 |
4 |
0 |
0 |
71/2 |
12 |
1/2 |
Оптимальный план можно записать так:
X2 = 3
X3 = 1
F(X) = 14*3 + 15*1 = 57
Похожие статьи
-
Решим прямую задачу линейного программирования симплексным методом, с использованием симплексной таблицы. Определим максимальное значение целевой...
-
Приведем систему ограничений к каноническому виду, для этого необходимо неравенства преобразовать в равенства, с добавлением дополнительных переменных....
-
Известно оптимальное решение X*=(0;0;1;1) задачи линейного программирования: Составьте двойственную задачу и найдите ее оптимальное решение по теореме...
-
Необходимость введения нового ограничения может возникнуть, например, когда первоначально для сокращения затрат машинного времени некоторые интуитивно...
-
Решение симплекс-методом с помощью симплекс-таблиц - Математические методы и модели в экономике
Определим оптимальный план выпуска продукции, решив задачу линейного программирования (ЗЛП). Для этого сначала приведем модель к каноническому виду...
-
Математическая модель транспортной задачи: F = ??cIjXIj, (1) При условиях: ?xIj = aI, i = 1,2,..., m, (2) ?xIj = bJ, j = 1,2,..., n, (3)...
-
Ограничение чувствительность задача программирование Вариации правых частей ограничений приводят к изменению области допустимых решений ЗЛП, в действии...
-
Элементы матричного анализа - Методы решения системы линейных уравнений
Вектором, как на плоскости, так и в пространстве, называется направленный Отрезок , то есть такой Отрезок , один из концов которого выделен и называется...
-
В разделе 1 курсовой работы требуется: Определить количество закупаемого заданным филиалом фирмы сырья у каждого АО, (xj), максимизируя прибыль филиала....
-
Это раздел математического программирования, изучающий методы решения таких экстремальных задач, в которых результаты (эффективность) возрастают или...
-
Как известно решение задач симплексным методом применяется очень часто. Это связано с тем, что симплексный метод подходит для решения широкого круга...
-
Задача о загрузке рюкзака (задача о ранце) - Метод динамического программирования для решения задач
Постановка задачи. Пусть имеются N видов грузов с номерами. Единица груза j-го вида имеет все aJ. Если груз j-го вида берется в количестве xJ, то его...
-
Исходная задача: При ограничениях: Двойственной является следующая задача: При ограничениях: Число неизвестных в двойственной задаче равно 2....
-
Линейное программирование, Общая задача линейного программирования - Экономико-математические методы
Термин "линейное программирование" впервые появился в 1951 г. в работах американских ученых (Дж. Данциг, Т. Купманс), а первые исследования по линейному...
-
Некоторые особенности решения задач нелинейного программирования - Экономико-математические методы
Для решения ЗНП существенно знать: 1) выпукло или не выпукло множество допустимых решений задачи; 2) является ли целевая функция выпуклой или вогнутой...
-
Необходимо найти минимальное значение целевой функции F = 4x1+18x2 > min, при системе ограничений: X1+4x2?14(1) X1+6x2?15(2) X1+x2?5(3)...
-
Вариации коэффициентов целевой функции ЗЛП приводят к изменению направления вектора градиента. Так как при этом не затрагивается допустимое множество, то...
-
В начале пятилетнего периода работы предприятию выделена сумма в C руб. для приобретения нового оборудования. Стоимость одного комплекта оборудования...
-
Большое число экономических и планово-производственных задач связано с распределением каких-либо, как правило, ограниченных ресурсов (сырья, рабочей...
-
Задачей линейного программирования (ЛП) называется задача минимизации или максимизации линейного функционала при линейных ограничениях. В литературе...
-
Исследуем на экстремум функцию: 1. С помощью необходимого существования экстремума, т. е. из системы Найдем координаты стационарных (критических) точек:...
-
Так как целевая функция не является линейной, то эта задача является задачей нелинейного программирования. Найдем ее решение, используя геометрическую...
-
Математическая модель задачи нелинейного программирования (ЗНП) (*) Для ЗНП в отличие от Задачи Линейного Программирования (ЗЛП) нет единого метода...
-
Литература - Решение оптимизационных экономических задач методами линейного программирования
1. Карпелович Ф. И., Садовский Л. Е. Элементы линейной алгебры и линейного программирования. - М.: Физматгиз, 1963. 2. Коротков М., Гаврилов М. "Основы...
-
Экономико-математические методы и моделирование в землеустройстве позволяют решать большой круг задач, связанных с оптимизацией территориальной...
-
Системы массового обслуживания -- это такие системы, в которые в случайные моменты времени поступают заявки на обслуживание, при этом поступившие заявки...
-
Динамическое программирование Динамическое программирование -- один из разделов оптимального программирования, в котором процесс принятия решения и...
-
Пусть имеется оптимизационная задача вида: (1) (2) (3) - задан(4) Здесь предполагается, что FJ(xJ,yJ)>0 для всех допустимых значений xJ,yJ. В этом случае...
-
Симплекс - метод - Интегральное и дифференциальное исчисление
Другой способ решения задач линейного программирования - симплекс-метод. Он, в отличие от геометрического, является полностью аналитическим, что...
-
Решение смешанной задачи для уравнения теплопроводности методом конечных разностей
Решение смешанной задачи для уравнения теплопроводности методом конечных разностей 1. Цель работы Ознакомление с методами решения смешанных задач для...
-
Комментарии к третьему разделу курсовой работы В третьем разделе курсовой работы студенту предлагается определить оптимальную стратегию заказа в условиях...
-
РЕШЕНИЕ ЗАДАЧИ О КОММИВОЯЖЕРЕ МЕТОДОМ ВЕТВЕЙ И ГРАНИЦ. ПРИМЕРЫ - Задача коммивояжера
Рассмотрим конкретный пример реализации метода ветвей и границ для решения задачи о коммивояжере. Итак, требуется найти легчайший простой основный...
-
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 Допустим, стоимость доставки единицы груза из каждого пункта отправления в...
-
Ранг матрицы. - Методы решения системы линейных уравнений
Как было сказано Выше , минором матрицы порядка s называется определитель матрицы, образованной из элементов исходной матрицы, находящихся на пересечении...
-
Определители (детерминанты) - Методы решения системы линейных уравнений
Определение. Определителем квадратной матрицы А= называется число, которое может быть вычислено по элементам матрицы по формуле: Det A = , где (1) М1к -...
-
Матрицы и определители - Методы решения системы линейных уравнений
Определение. Матрицей размера mn, где m - число строк, n - число столбцов, называется таблица чисел, расположенных в определенном порядке. Эти числа...
-
Решение транспортной задачи методом потенциалов - Математическая модель решения транспортной задачи
Этот метод позволяет автоматически выделять циклы с отрицательной ценой и определять их цены. Пусть имеется транспортная задача с балансовыми условиями...
-
Оптимальное решение модели. - Методика решения задачи целочисленного программирования
Рис. 1 Шаг 1. Исходную задачу 1 заносим в дерево задач. В качестве исходного допустимого решения берем: x1=x2=x3=0. Соответствующее значение целевой...
-
Метод дифференциальных рент для решения транспортной задачи - Формирование оптимального штата фирмы
Для решения транспортных задач используется несколько методов. Рассмотрим решение с помощью метода дифференциальных рент. При нахождении решения...
-
Иногда необходимо управлять сложными комплексами взаимосвязанных работ, направленных на достижение определенных целей. Примерами таких комплексов в...
Симплексный метод решения задач ЛП - Решение оптимизационных экономических задач методами линейного программирования