Математическое программирование задачи с решением

Оглавление:

Математическое программирование задачи с решением

Прежде чем изучать готовые решения задач по математическому программированию, нужно знать теорию, поэтому для вас я подготовила краткую теорию по предмету «математическое программирование», после которой подробно решены задачи.

Эта страница подготовлена для школьников и студентов.

Если что-то непонятно вы всегда можете написать мне в воцап и я вам помогу!

Жордановы исключения

К оглавлению…

Пусть дана система линейных уравнений

Математическое программирование задачи с решением

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

Решение задач по математическому программированию

с матрицей Решение задач по математическому программированию коэффициенты и свободные члены этой системы определяются по формулам

Решение задач по математическому программированию

Если же Решение задач по математическому программированию. го принимаем Решение задач по математическому программированию. Таким образом, Решение задач по математическому программированию— е уравнения в системах (1.1) и (1.2) одинаковы, а коэффициенты при Решение задач по математическому программированию во всех уравнениях системы (1.2), кроме Решение задач по математическому программированию — го, равны нулю.

Системы (1.1) и (1.2) одновременно совместны или несовместны. В случае совместности эти системы равносильны (их решения совпадают).

Для определения элемента Решение задач по математическому программированию матрицы Решение задач по математическому программированию применяется правило прямоугольника

Рассмотрим четыре элемента матрицы Решение задач по математическому программированию (элемент, подлежащий преобразованию), Решение задач по математическому программированию (разрешающий элемент) и элементы Решение задач по математическому программированию и Решение задач по математическому программированию. Для нахождения элемента Решение задач по математическому программированию следует из элемента Решение задач по математическому программированию вычесть произведение элементов Решение задач по математическому программированию и Решение задач по математическому программированию расположенных в противоположных вершинах прямоугольника, делённое на разрешающий элемент Математическое программирование задачи с решением

Решение задач по математическому программированию

Аналогичным образом можно преобразовать систему (1.2), приняв за разрешающий элемент матрицы Решение задач по математическому программированию элемент Решение задач по математическому программированию, причём Решение задач по математическому программированию.

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

Возможно эта страница вам будет полезна:

Предмет математическое программирование

Задача №1.1.

Найти решение системы:

Решение задач по математическому программированию

Систему решить методом Жордано-Гаусса: 1) аналитически; 2) с помощью MS Excel.

Решение:

Запишем систему в виде жордановой таблицы.

Решение задач по математическому программированию

1 шаг. Разрешающий столбец — 1; разрешающая строка — 3; разрешающий элемент Решение задач по математическому программированию. Применим правило прямоугольника.

Решение задач по математическому программированию

2 шаг. Делим элементы разрешающей строки па -3 и опять применяем правило прямоугольника:

Решение задач по математическому программированию

3 шаг. В качестве разрешающего элемента выбираем Решение задач по математическому программированию. Делим элементы четвёртой строки на 4 и проводим ещё один шаг жордановых исключений:

Решение задач по математическому программированию

4 шаг. Умножаем первую (разрешающую) строку на -1. Разрешающий столбец — третий.

Математическое программирование задачи с решением

Система имеет единственное решение

Решение задач по математическому программированию

Используем для решения системы MS Excel:

Решение задач по математическому программированию
Решение задач по математическому программированию

Задача №1. 2.

Решить систему уравнений.

Решение задач по математическому программированию

Систему решить методом Жордано-Гаусса с помощью MS Excel.

Решение:

Решение задач по математическому программированию

Пусть

Решение задач по математическому программированию

тогда

Решение задач по математическому программированию

Возможно эта страница вам будет полезна:

Примеры решения задач по математическому программированию

Постановка задачи математического программировании

К оглавлению…

Рассмотрим оптимизационные задачи, решаемые методами линейного программирования (ЛП), в которых оптимизируемая функция Решение задач по математическому программированию является линейной, а ограничения Решение задач по математическому программированию задаются линейными неравенствами. Ограничения задают выпуклые линейные многогранники в конечном линейном пространстве. Целевые функции также линейны.

Задача линейного программирования (ЗЛП) записывается следующим образом: найти переменные Решение задач по математическому программированию, при которых целевая функция

Решение задач по математическому программированию

была бы максимальной (минимальной), не нарушая следующих условий:

Решение задач по математическому программированию

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

Решение задач по математическому программированию

где Решение задач по математическому программированию — количество дополнительных переменных и условие неотрицательности искомых переменных Решение задач по математическому программированию.

В результате решения задачи находится некий план (программа) работы некоторого предприятия. Отсюда и появилось слово «программирование». Слово линейное указывает на линейный характер зависимости, как в целевой функции, так и в системе ограничений. Задача обязательно носит экстремальный характер, т.е. состоит в отыскании максимума или минимума (экстремума) целевой функции. Допустимым решением (планом) задачи линейного программирования называется любой Решение задач по математическому программированию-мерный вектор Решение задач по математическому программированию удовлетворяющий системе ограничений и условиям неотрицательности. Множество всех допустимых решений задачи образуют область допустимых решений (сокращенно ОДР).

Элементы линейной алгебры и геометрии выпуклых множеств

Система Решение задач по математическому программированию линейных уравнений с Решение задач по математическому программированию переменными имеет вид

Решение задач по математическому программированию

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

Будем полагать, что в системе (2.1) все Решение задач по математическому программированию уравнений системы независимы, т.е. Решение задач по математическому программированию и соответственно Решение задач по математическому программированию.

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

Среди бесконечного множества решений системы выделяют так называемые базисные решения.

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

В задачах линейного программирования особый интерес представляют допустимые базисные решения, или, как их еще называют, опорные планы. Число базисных решений является конечным, так как оно равно числу групп основных переменных, не превосходящему Решение задач по математическому программированию. Базисное решение, в котором хотя бы одна из основных переменных равна нулю, называется вырожденным.

Выпуклые множества точек:

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

Решение задач по математическому программированию

Например, многоугольник на рис. 2.1, а — выпуклый, а многоугольник на рис. 2.1, б не является выпуклым (он расположен по обе стороны от прямой Решение задач по математическому программированию).

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

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

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

Теорема 2.1. Пересечение (общая часть) любого числа выпуклых множеств есть выпуклое множество.

Среди точек выпуклого множестваможно выделить внутренние, граничные и угловые точки. Точка множества называется внутренней, если в некоторой ее окрестности содержатся точки только данного множества. Точка множества называется граничной, если в любой ее окрестности содержатся как точки, принадлежащие данному множеству, так и точки, не принадлежащие ему. Точка множества называется угловой (или крайней), если она не является внутренней ни для какого отрезка, целиком принадлежащего данному множеству.

Решение задач по математическому программированию

На рис. 2.2 приведены примеры различных точек многоугольника: внутренней (точки Решение задач по математическому программированию), граничной (точка Решение задач по математическому программированию) и угловых (точки Решение задач по математическому программированиюРешение задач по математическому программированию). Точка Решение задач по математическому программированию — угловая, так как для любого отрезка, целиком принадлежащего многоугольнику, например, отрезка Решение задач по математическому программированию, она не является внутренней; точка Математическое программирование задачи с решением — внутренняя для отрезка Математическое программирование задачи с решением, но этот отрезок не принадлежит целиком многоугольнику.

Множество точек называется замкнутым, если включает все свои граничные точки. Множество точек называется ограниченным, если существует шар (круг) радиуса конечной длины с центром в любой точке множества, который полностью содержит в себе данное множество; в противном случае множество называется неограниченным.

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

Выпуклое замкнутое множество точек пространства (плоскости), имеющее конечное число угловых точек, называется выпуклым многогранником (,многоугольником•), если оно ограниченное, и выпуклой многогранной (многоугольной) областью, если оно неограниченное.

Множество всех точек Решение задач по математическому программированию образует Решение задач по математическому программированию -мерное точечное (векторное) пространство. При Решение задач по математическому программированию точки и фигуры «Решение задач по математическому программированию-мерного пространства» не имеют реального геометрического смысла и все исследования объектов этого пространства необходимо проводить в аналитической форме.

Тем не менее оказывается целесообразным и в этом случае использовать геометрические понятия для облегчения представлений об объектах Решение задач по математическому программированию — мерного пространства.

Геометрический смысл решений неравенств, уравнений и их систем

Теорема 2.2. Множество решений неравенства с двумя переменными

Решение задач по математическому программированию

является одной из двух полуплоскостей, на которые вся плоскость делится прямой

Решение задач по математическому программированию

включая и эту прямую, а другая полуплоскость с той же прямой есть множество решений неравенства

Решение задач по математическому программированию

Учитывая, что множество точек, удовлетворяющих уравнению

Решение задач по математическому программированию

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

Теорема 2.3. Множество всех решений линейного неравенства с Решение задач по математическому программированию переменными

Решение задач по математическому программированию

является одним из полупространств, на которые все пространство делится плоскостью или гиперплоскостью (2.2), включая и эту плоскость (гиперплоскость).

Рассмотрим множество решений систем неравенств:

Теорема 2.4. Множество решений совместной системы Решение задач по математическому программированию линейных неравенств с двумя переменными

Решение задач по математическому программированию

является выпуклым многоугольником (или выпуклой многоугольной областью).

При построении областей решений систем неравенств могут встретиться и другие случаи: множество решений — выпуклая многоугольная область (рис. 2.3, а); одна точка (рис. 2.3, б); пустое множество, когда система неравенств несовместна (рис. 2.3, в).

Решение задач по математическому программированию

Теорема 2.5. Множество решений совместной системы от линейных неравенств с Решение задач по математическому программированию переменными является выпуклым многогранником (выпуклой многогранной областью) в Решение задач по математическому программированию-мерном пространстве.

Рассмотрим множество допустимых решений системы Решение задач по математическому программированию линейных уравнений с Решение задач по математическому программированию переменными.

Теорема 2.6. Множество всех допустимых решений совместной системы Решение задач по математическому программированию линейных уравнений с Решение задач по математическому программированию переменными (Решение задач по математическому программированию) является выпуклым многогранником (выпуклой многогранной областью) в Решение задач по математическому программированию-мерном пространстве.

Возможно эта страница вам будет полезна:

Заказать работу по математическому программированию

Графический метод решения ЗЛП

К оглавлению…

Методы решения задач линейного программирования относятся к вычислительной математике. Задачу линейного программрования можно решать аналитическими и графическими методами. Аналитические методы, которые представляют собой последовательность вычислений по некоторым правилам, являются основой для решения задачи на компьютере. Их единственный недостаток заключается в том, что в отличие от графических методов, они совершенно не наглядны. Графические же методы достаточно наглядны, но они пригодны лишь для решения таких задач, что даёт возможность представлять задачу на плоскости.

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

Решение задач по математическому программированию

Такая задача может быть решена графически (геометрически) ввиду того, что в этом случае легко строить ОДР (область допустимых решений).

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

1) Построить ОДР.

2) Построить вектор нормали Решение задач по математическому программированию целевой функции (он указывает па направление возрастания целевой функции).

3) Построить нижнюю и верхнюю опорные прямые Решение задач по математическому программированию и Решение задач по математическому программированию, т. е. крайние линии уровня целевой функции, имеющие общие точки с ОДР.

4) Определить координаты экстремальных точек Решение задач по математическому программированиюРешение задач по математическому программированию.

Примечания.

1) Если ОДР — пустое множество, то задача не имеет решения ввиду несовместности системы ограничений.

2) Если ОДР неограничена по направлению вектора Решение задач по математическому программированию, то сама целевая функция неограничена сверху в этой области, и принимаем Решение задач по математическому программированию. Если ОДР неограничена в направлении, противоположном Решение задач по математическому программированию, то принимаем Решение задач по математическому программированию.

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

Возможно эта страница вам будет полезна:

Помощь по математическому программированию

Задача №2.1.

Найти все базисные решения системы уравнений.

Решение задач по математическому программированию

Решение:

Запишем систему в таблицу. Жордановы исключения будем выполнять в пакете MS Excel (Таблицы 2.1 — 2.4).

Решение задач по математическому программированию

Эквивалентная система:

Решение задач по математическому программированию

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

Б, = (1,2, 0, 0).

В данном случае Решение задач по математическому программированию, поэтому всего базисных решений может 2 4!

быть не более Решение задач по математическому программированию. Другими базисами могут оказаться следующие группы переменных:

Решение задач по математическому программированию

Для того чтобы найти второе базисное решение Решение задач по математическому программированию, вернемся к таблице 2.3. Вычеркнем из неё первую строку (первая и третья строки пропорциональны) и примем за разрешающий третий столбец. Получим таблицы 2.3 — 2.6.

Решение задач по математическому программированию

Сделав шаг жордановых исключений, перейдём к базису Решение задач по математическому программированию и при Решение задач по математическому программированию (таблица 2.7) получим ещё одно базисное решение Решение задач по математическому программированию:

Решение задач по математическому программированию

Преобразовывая последовательно шагами жордановых исключений таблицы 2.5, 2.1 получим другие базисные решения:

Базисные переменные Решение задач по математическому программированию. Свободные переменные Решение задач по математическому программированию. Базисное решение

Решение задач по математическому программированию
Решение задач по математическому программированию

Базисные переменные Решение задач по математическому программированию. Свободные переменные Решение задач по математическому программированию. Базисное решение

Решение задач по математическому программированию
Решение задач по математическому программированию

Базисные переменные Решение задач по математическому программированию. Свободные переменные Решение задач по математическому программированию. Базисное решение

Решение задач по математическому программированию
Математическое программирование задачи с решением

Базисные переменные Решение задач по математическому программированию. Свободные переменные Решение задач по математическому программированию. Базисное решение

Решение задач по математическому программированию
Решение задач по математическому программированию

Задача №2.2.

Записать в форме стандартной задачи линейного программирования следующую задачу:

Решение задач по математическому программированию

Решение:

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

Эти преобразования удобнее проводить одновременно, приписав к жордановой таблице снизу строку для целевой функции (Решение задач по математическому программированию—строку). В процессе жордановых исключений эту строку не следует делать разрешающей, но преобразовывать её элементы нужно по обычным правилам. В результате целевая функция, как и базисные переменные, окажется выраженной через свободные переменные.

В условиях данной задачи разрешающие элементы можно выбрать произвольно

Решение задач по математическому программированию

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

Решение задач по математическому программированию

Задача №2.3.

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

Решение задач по математическому программированию

Решение:

а) Область допустимых решений, которую обозначим буквой Решение задач по математическому программированию, построим следующим образом. Построим прямые с уравнениями:

Решение задач по математическому программированию
Решение задач по математическому программированию

Прямые пронумерованы. Помер прямой имеется также на рисунке 2.4.

б) Каждое неравенство, фигурирующее в системе ограничений, определяет полуплоскость, причем эта полуплоскость содержит точку, координаты которой удовлетворяют соответствующему строгому неравенству.

Первые два и четвертое неравенства системы ограничений удовлетворяются координатами точки Решение задач по математическому программированию.

Поэтому три полуплоскости содержат начало координат системы Решение задач по математическому программированию.

На соответствующую полуплоскость указывают стрелки, идущие от каждой прямой. Жирной линией выделим границу ОДР выпуклый шестиугольник Решение задач по математическому программированию. Последние неравенства Решение задач по математическому программированию, означающие неотрицательность переменных задачи, определяют первую четверть плоскости Решение задач по математическому программированию.

в) Строим теперь нормальный вектор целевой функции Решение задач по математическому программированию. Его направление указывает направление возрастания целевой функции Решение задач по математическому программированию.

Прямая с уравнением Решение задач по математическому программированию представляет собой «нулевую» линию уровня функции Решение задач по математическому программированию. Эта прямая проходит через начало координат и перпендикулярна нормальному вектору Решение задач по математическому программированию Передвигаем эту прямую параллельно себе, или перпендикулярно Решение задач по математическому программированию, и фиксируем два ее крайних положения.

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

г) Определим координаты точек Решение задач по математическому программированию и Решение задач по математическому программированию. На чертеже видно, что точка Решение задач по математическому программированию лежит на прямых 3) и 7), а Решение задач по математическому программированию — на 2) и 4). Именно поэтому пронумерованы уравнения прямых и их изображения. Теперь легко составить системы уравнений для определения координат этих точек. Запишем это так:

Решение задач по математическому программированию

Вычислим значения целевой функции в точках Решение задач по математическому программированию и Решение задач по математическому программированию:

Решение задач по математическому программированию

Возможно эта страница вам будет полезна:

Задачи математического программирования

Симплекс-метод. Краткие теоретические сведении

К оглавлению…

Симплекс-метод. Максимум или минимум целевой функции может быть достигнут в одной из угловых точек области допустимых планов.

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

Однако количество угловых точек области допустимых планов растет очень резко с ростом числа переменных и особенно числа ограничений. Число перебираемых вершин можно сократить, если производить перебор не беспорядочно, а с учетом изменений целевой функции, т.е. добиваясь того, чтобы каждое следующее решение было «лучше» (или, по крайней мере, «не хуже»), чем предыдущее (было ближе к оптимальному решению).

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

Симплекс-метод — один из первых специализированных методов оптимизации, нацеленный на решение задач линейного программирования. Он был предложен американцем Г. Данцигом в 1951 г. Симплекс-метод состоит в продвижении по выпуклому многограннику ограничений от вершины к вершине, при котором на каждом шаге значение целевой функции улучшается до тех пор, пока не будет достигнут оптимум.

Задача №3.1.

Найти какой-либо опорный план задачи (математически).

Решение задач по математическому программированию

Решить задачу в Excel, используя «Поиск решения».

Решение:

Задача записана в канонической форме, но 2 свободных члена отрицательны, поэтому, прежде чем записать задачу в форме таблицы, умножим первое и второе уравнение на (-1).

Математическое программирование задачи с решением

Для первого шага жорданова исключения возьмём разрешающим, например, четвёртый столбец — в нём есть положительные элементы. Разрешающая строка определится по минимальному из отношений: 4/1 и 7/1.

В данном случае

Решение задач по математическому программированию

что соответствует первой строке, которая и будет разрешающей.

Решение задач по математическому программированию

Сделаем ещё 2 шага жордановых исключений, получим:

Решение задач по математическому программированию
Решение задач по математическому программированию

Базис выделен. Ему соответствует начальный опорный план

Решение задач по математическому программированию

Был найден опорный план в базисе Решение задач по математическому программированию. Если исходную таблицу преобразовать с другими разрешающими элементами, то получится другой базис — следовательно, и другой опорный план.

Решение задачи в процедуре EXCEL «Поиск решения».

1) Ввод данных в таблицу EXCEL (рис. 3.1).

Решение задач по математическому программированию

Для переменных задачи отведены ячейки B3:F3. Эти ячейки называются рабочими или изменяемыми ячейками.

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

В ячейку G4 вводится формула для вычисления целевой функции задачи Решение задач по математическому программированию (рис. 3.2):

Решение задач по математическому программированию

В ячейку G7 вводится формула для вычисления ограничения 1: Решение задач по математическому программированию, в ячейку G8 вводится формула для вычисления ограничения 2: Решение задач по математическому программированию а в ячейку G9 — вычисления ограничения 3: Решение задач по математическому программированию. Обе формулы вводятся с помощью функции СУММПРОИЗВ0:

Решение задач по математическому программированию

Окончательно после ввода формул и данных экран имеет вид (рис. 3.4):

2) Работа в окне «Поиск решения»»

В меню «Данные» выбираем процедуру «Поиск решения» В появившемся окне (рис. 3.5) нужно установить адрес целевой ячейки G4, значение целевой ячейки: максимальное, адреса изменяемых ячеек B3:F3.

Решение задач по математическому программированию

Чтобы ввести ограничения задачи, нажать кнопку «Добавить». В появившемся диалоговом (рис. 3.6) окне слева ввести адрес G7 (ограничение 1), затем выбрать знак <= и в правой — адрес ячейки Н7.

Решение задач по математическому программированию

После ввода нажать кнопку «Добавить» и аналогично ввести второе и третье ограничение. Снова нажать кнопку <<Добавить» и ввести ограничение: В3:3 >-0 (соответствующее ограничению Решение задач по математическому программированию).

После ввода последнего ограничения нажать ОК. В опции «Выбрать метод решения» выбрать «Поиск решения линейных задач симплекс-методом». Окно «Поиска решений» будет иметь вид (рис. 3.7):

Решение задач по математическому программированию

Для решения задачи в окне «Поиск решения» нажать кнопку «Найти решение». Если решение найдено появляется окно (рис. 3.8):

Решение задач по математическому программированию

Оптимальное решение задачи линейного программирования:

Решение задач по математическому программированию

Был найден оптимальный план в базисе

Решение задач по математическому программированию

Различные технико-экономические и экономические задачи производственного менеджмента, от оптимальной загрузки станка и раскройки стального листа или полотна ткани

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

Возможно эта страница вам будет полезна:

Задача линейного программирования

Задача №3.2.

Задача распределения ресурсов.

Если финансы, оборудование, сырьё и даже людей полагать ресурсами, то значительное число задач в экономике можно рассматривать как задачи распределения ресурсов. Достаточно часто математической моделью таких задач является задача линейного программирования.

Рассмотрим следующий пример.

Требуется определить, в каком количестве надо выпускать продукцию четырёх типов Прод1, Прод2, ПродЗ, Прод4, для изготовления которой требуются ресурсы трёх видов: трудовые, сырьё, финансы. Количество ресурсов каждого вида, необходимое для выпуска единицы продукции данного типа, называется нормой расхода. Нормы расхода, а также прибыль, получаемая от реализации единицы каждого типа продукции, приведены в таблице 2. Там же приведено наличие располагаемого ресурса.

Решение задач по математическому программированию

Составить математическую модель, решить задачу симплекс-методом, применяя процедуру Excel «Поиск решения».

Решение:

Введём следующие обозначения:

Решение задач по математическому программированию — количество выпускаемой продукции Решение задач по математическому программированию— го типа, Решение задач по математическому программированию; Решение задач по математическому программированиюj — количество располагаемого ресурса Решение задач по математическому программированию — го вида, Решение задач по математическому программированию; Решение задач по математическому программированию— норма расхода Решение задач по математическому программированию— го ресурса для выпуска единицы продукции Решение задач по математическому программированию — го типа;

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

Как видно из таблицы 2, для выпуска единицы Прод1 требуется 6 единиц сырья, значит, для выпуска всей продукции Прод1 требуется 6Решение задач по математическому программированию единиц сырья, где Решение задач по математическому программированию — количество выпускаемой продукции Прод1. С учётом того, что для других видов продукции зависимости аналогичны, ограничение по сырью будет иметь вид:

Решение задач по математическому программированию

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

Аналогично можно составить ограничения для остальных ресурсов и написать зависимость для целевой функции. Тогда математическая модель задачи будет иметь вид:

Решение задач по математическому программированию

Решение задачи в пакете EXCEL с поиощью «Поиск решения». 1) Ввод данных в таблицу EXCEL (рис. 3.9).

Решение задач по математическому программированию

2) Работа в окне «Поиск решения»»

Решение задач по математическому программированию

На рис. 3.10 видно, что в оптимальном решении ПроЫ =ВЗ = 10 Прод2 = СЗ = 0 ПродЗ = D3 = 6 Прод4 = ЕЗ = 0.

При этом максимальная прибыль будет составлять F4 = 1320, а количество использованных ресурсов равно

трудовых — F7 = 16 сырья = F8 = 84 финансов = F9 = 100 Анализ оптимального решения.

Анализ оптимального решения начинается после успешного решения задачи, когда на экране появляется диалоговое окно Результат поиска решения. Решение найдено (рис. 3.10). С помощью этого диалогового окна можно вызвать отчёты трёх типов: •Результаты

•Устойчивость • Пределы.

Вызов отчётов анализа.

Начнём с отчёта по результатам. Выделяем вызываемый отчёт и жмём на ОК (рис. 3.1 1)

Решение задач по математическому программированию

На экране: вызванный отчёт на новом листе, на ярлыке которого указано название отчёта (рис. 3.12).

Отчёт состоит из трёх таблиц.

• Таблица 1 приводит сведения о целевой функции.

•Таблица 2 приводит значения искомых переменных, полученные в результате решения задачи.

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

Для Ограничений в графе Формула приведены зависимости, которые были введены в диалоговое окно Поиск решения; в графе Значение ячейки приведены величины использованного ресурса; в графе Допуск показано количество неиспользованного ресурса. Если ресурс используется полностью, то в графе Состояние указывается Привязка; при неполном использовании ресурса в этой графе указывается Без привязки.

Математическое программирование задачи с решением
Решение задач по математическому программированию

Для Граничных условий приводятся аналогичные величины с той лишь разницей, что вместо величины неиспользованного ресурса показана разность между значением переменой в найденном оптимальном решении и заданным для неё граничным условием.

Решение задач по математическому программированию

Отчёт по устойчивости (рис. 3.13) состоит из двух таблиц.

В таблице 1 приводятся следующие значения для переменных:

•результат решения задачи;

• приведенная стоимость, т.е. дополнительные двойственные переменные, которые показывают, насколько изменяется целевая функция при принудительном включении единицы этой продукции в оптимальное решение;

• коэффициенты целевой функции;

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

В таблице 2 приводятся аналогичные значения для ограничений:

• величина использованных ресурсов;

•теневая цена, т.е. двойственные оценки Решение задач по математическому программированию, которые показывают, как изменится целевая функция при изменении ресурсов на единицу;

•значения приращения ресурсов Решение задач по математическому программированию при которых сохраняется оптимальный объём переменных, входящих в оптимальное решение.
Отчёт по пределам приведён на рис. 3.14.

Решение задач по математическому программированию

В нём показано, в каких пределах может изменяться выпуск продукции, вошедшей в оптимальное решение, при сохранении структуры оптимального решения:

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

• приводятся нижние пределы изменения значений Решение задач по математическому программированию.

Кроме этого, в отчёте указаны значения целевой функции при выпуске данного типа продукции на нижнем пределе. Так, при значении 720 видно, что

Решение задач по математическому программированию

Далее приводятся верхние пределы изменения Решение задач по математическому программированию— и значения целевой функции при выпуске продукции, вошедшей в оптимальное решение на верхних пределах.

Поэтому везде

Решение задач по математическому программированию

Возможно эта страница вам будет полезна:

Примеры решения задач по линейному программированию

Решение задачи математического программирования в microsoft excel

К оглавлению…

Постановка задачи:

Предприятие выпускает продукцию двух типов Решение задач по математическому программированию и Решение задач по математическому программированию. Запас сырья и нормы расхода сырья на условную единицу продукции каждого типа даны в таблице.

Решение задач по математическому программированию

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

Решение данной задачи графическим методом в табличном редакторе Microsoft Excel

Математическая модель и исходные данные задачи — на рисунке 2.3.

Для построения области допустимых решений, Решение задач по математическому программированию и линии уровня необходимо:

1) Выделить данные в области (например, C17:D29), и на вкладке «Вставка» выбрать: «Точечная». Затем после построения первой линии из области допустимых решений, щёлкнуть правой клавишей мыши на области диаграммы и выбрать «Выбрать данные».

2) Щёлкнуть мышью по «Ряд 1» и выбрать кнопку «Изменить». В поле имя ряда записать уравнение построенной прямой (см. рис. 4.1)

Решение задач по математическому программированию

3) Нажать кнопку «Добавить» и выбрать исходные данные для построения второго графика (см. рис. 4.2)

Решение задач по математическому программированию

4) Повторить предыдущий пункт для остальных уравнений, входящих в область допустимых решений, а также для градиента и линии уровня.

5) Итоги решения задачи приведены на рисунке 4.3.

Область допустимых решений представляет собой многоугольник с вершинами в точках: (0;0), (0;6), (2;5), (4;3), (5;0).

При перемещении линии уровня в направлении вектора Математическое программирование задачи с решением получаем оптимальное решение в точке с координатами (2;5), причём

Решение задач по математическому программированию

Для получения максимальной прибыли равной 19 д. е. предприятие должно выпускать 2 ед. продукции Решение задач по математическому программированию и 5 ед. продукции Решение задач по математическому программированию

Решение задач по математическому программированию

Решение в Microsoft Excel симплекс-методом

Подготовим начальную симплекс таблицу по образцу:

Решение задач по математическому программированию

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

В столбце В записывают положительные компоненты начального опорного плана, в нём же в результате вычислений получают положительные компоненты оптимального плана.

Первые три строки начальной симплекс-таблицы определяются исходными данными задачи, а показатели четвёртой строки — вычисляют. В этой строке в столбце В записывают значение целевой функции, которое она принимает при данном опорном плане, а в столбце Решение задач по математическому программированию — значение

Решение задач по математическому программированию

Значение Решение задач по математическому программированию находится как скалярное произведение вектора

Решение задач по математическому программированию

на вектор

Решение задач по математическому программированию
Решение задач по математическому программированию

Значение Решение задач по математическому программированию равно скалярному произведению вектора Решение задач по математическому программированию на вектор Решение задач по математическому программированиюВычислим его и запишем результат в ячейку Решение задач по математическому программированию. Для вычисления скалярного произведения двух векторов используется функция СУММПРОИЗВ (массив1, [массив2], [массивЗ],…) (рис. 4.5).

Решение задач по математическому программированию

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

Решение задач по математическому программированию

Выделим ячейку Е7 и введём формулу:

Решение задач по математическому программированию

Аналогично вычислим значения других оценок.

Решение задач по математическому программированию

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

1) Решение задач по математическому программированию — исходный план является оптимальным;

2) Решение задач по математическому программированию для некоторого Решение задач по математическому программированию и все соответствующие этому индексу величины Решение задач по математическому программированию — целевая функция не ограничена сверху на множестве планов;

3) Решение задач по математическому программированию для некоторых индексов Решение задач по математическому программированию и для каждого такого Решение задач по математическому программированию по крайней мере одно из чисел Решение задач по математическому программированию является положительным — можно перейти от исходного плана к новому опорному плану, при котором значение целевой функции увеличится.

Определим разрешающий столбец — столбец с наибольшей по модулю отрицательной оценкой и найдем отношение элементов столбца В к положительным элементам выбранного столбца для определения разрешающей строки. Для этого выделим ячейку К4 и введём формулу:

Решение задач по математическому программированию

Скопируем формулу на диапазон К4:К6.

Решение задач по математическому программированию

Таким образом, разрешающий столбец — столбец Решение задач по математическому программированию и разрешающая строка — Решение задач по математическому программированию.

Создадим вторую симплекс-таблицу (скопируем предыдущую и удалим все ненужное). Произведём замену в базисе вектора Решение задач по математическому программированию(разрешающий столбец) на вектор Решение задач по математическому программированию (разрешающая строка).

Решение задач по математическому программированию

Выделим диапазон D 12:115 и сменим формат числовых данных на дробный.

Вычислим новые элементы разрешающей строки: разделим элементы разрешающей строки на разрешающий элемент. В ячейку D13 введём формулу

Решение задач по математическому программированию

Скопируйте формулу на диапазон Е13: 113:

Решение задач по математическому программированию

В ячейку D12 введём формулу:

Решение задач по математическому программированию

Скопируем формулу на диапазон Е12:I12. В ячейку D14 введём формулу:

Математическое программирование задачи с решением

и скопируем формулу на диапазон Е15:115. В ячейку D15 введём формулу:

Решение задач по математическому программированию

Скопируем формулу на диапазон Е15:I15. Получим:

Решение задач по математическому программированию

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

Решение задач по математическому программированию

Строим новую симплекс-таблицу и заменяем вектор Решение задач по математическому программированию (разрешающая строка) на вектор Решение задач по математическому программированию (разрешающий столбец). Заполняем таблицу аналогично предыдущей итерации:

Решение задач по математическому программированию

Так как строка оценок не содержит отрицательных значений, то полученный план оптимален и имеет вид:

Решение задач по математическому программированию

Исключая из решения балансовые неизвестные, получим ответ:

Решение задач по математическому программированию

Возможно эта страница вам будет полезна:

Решение задач по линейному программированию

Решение в Microsoft Excel с помощью встроенной функции Поиск решения

В табличном процессоре Microsoft Excel существует встроенная функция Поиск решения, с помощью которой можно решить задачу линейного программирования. Если данный модуль установлен, его можно запустить, выбрав вкладку Данные /Поиск решения. На экране появится диалоговое окно Поиск решения (рис. 4.12).

Если такого пункта во вкладке Данные не оказалось, следует загрузить соответствующую программу-надстройку. Для этого нужно выбрать вкладку Файл-Параметры-Надстройки—Перейти и в диалоговом окне Надстройки установить флажок в строке Поиск решения.

Решение задач по математическому программированию

Разберем решение ЗЛП с помощью функции Поиск решения на примере нашей задачи.

  • Создадим таблицу для ввода исходных данных: переменных, целевой функции,ограничений.
  • Введем начальные нулевые значения для Решение задач по математическому программированию и Решение задач по математическому программированию.
  • Зададим целевую функцию в ячейке D6 и ограничения в ячейках F4, F5 и F6 (рис. 4.13).
Решение задач по математическому программированию
  • Выберем команду Данные/Поиск решения, в открывшемся окне Поиск решения установим целевую ячейку D6, зададим условие отыскания максимального значения (рис. 4.14).
  • В поле Изменяя ячейки установим ссылку на ячейки С5 и С6, которые будут изменены (молено ввести адреса или имена ячеек с клавиатуры или указать диапазон ячеек на рабочем листе с помощью мыши).
  • Определим ограничения, для этого щелчком по кнопке Добавить откроем диалоговое окно Добавление ограничения. Введем ограничения для ячеек F4, F5, F6. Ограничения можно задать как для изменяемых ячеек, так и для целевой ячейки, а также для других ячеек, прямо или косвенно присутствующих в модели (рис. 4.14)
Решение задач по математическому программированию
  • После того как все параметры и ограничения заданы, запускаем поиск решения, щелкнув на кнопке Найти решение. Когда поиск будет закончен, в таблицу будут внесены новые значения и на экране появится диалоговое окно Результаты поиска решения, сообщающие о завершении операции (рис. 4.15).
Решение задач по математическому программированию

Решение найдено. Все ограничения и условия оптимальности выполнены. Сохраним найденное решение. В этом случае таблица будет обновлена. В случае необходимости всегда можно будет восстановить исходные данные с помощью отчета. Для выбора типа отчета достаточно выделить название нужного отчета в списке Тин отчета (или несколько названий, удерживая нажатой клавишу Ctrl). Они будут вставлены на отдельных листах в рабочую книгу перед листом с исходными данными.

Предлагаемые отчеты содержат следующую информацию:

  • •отчет Результаты содержит сведения о начальных и текущих значениях целевой ячейки и изменяемых ячеек, а также о соответствии значений заданным ограничениям;
  • • отчет Устойчивость отражает найденный результат, а также нижние и верхние предельные значения для изменяемых ячеек;
  • •отчет Пределы показывает зависимость решений от изменения формулы или ограничений.

Если планируется использовать созданную модель в дальнейшем, найденное решение можно сохранить как сценарий. Для этого в диалоговом окне Результаты поиска решения необходимо щелкнуть на кнопке Сохранить сценарий.

Возможно эта страница вам будет полезна:

Методы решения задач линейного программирования

Двойственные задачи линейного программирования

К оглавлению…

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

Т.е. ЗЛП на максимум можно поставить в соответствие ЗЛП на минимум. Эти задачи называются симметричными или взаимно-двойственными.

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

Задача №5.1.

Предприятие, специализирующееся на производстве трикотажного полотна двух видов, использует для своего производства четыре вида сырья (шерстяную, хлопковую, вискозную, и акриловую нити), запасы которого на планируемый период составляют соответственно 80, 80, 260 и 410 бобин. В приведенной ниже таблице даны технологические коэффициенты, т.е. расход каждого вида сырья на производство одного метра каждого вида трикотажа.

Решение задач по математическому программированию

Прибыль от реализации 1 м трикотажного полотна первого вида составляет 2 д. е., а трикотажного полотна второго вида 3 д. е. Необходимо определить оптимальный план выпуска трикотажного полотна первого и второго вида, чтобы обеспечить максимальную прибыль от их реализации.

Экономико-математическая модель задачи: найти максимум целевой функции (функции прибыли):

Решение задач по математическому программированию

при выполнении системы ограничений:

Решение задач по математическому программированию

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

Очевидно, что покупающая организация заинтересована в том, чтобы затраты на все ресурсы (целевая функция Решение задач по математическому программированию) в количествах 80, 80, 260 и 410 д. е. по ценам Решение задач по математическому программированию были минимальны, т.е.

Решение задач по математическому программированию

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

На изготовление 1 м трикотажного полотна I вида расходуется 0 д. е. первого ресурса (шерсти), 1 д. е. второго ресурса (хлопка), 1 д. е. третьего ресурса (вискозы) и 4 д. е. четвертого ресурса (акрила). Поэтому для удовлетворения требований продавца затраты на ресурсы, потребляемые при изготовлении 1 м трикотажного полотна I вида по ценам Решение задач по математическому программированию, должны быть не менее цены 1 м трикотажного полотна 1 вида (2 д. е.), т.е.

Решение задач по математическому программированию

Аналогично составим ограничение в виде неравенства по второму виду продукции (трикотажному полотну II вида):

Решение задач по математическому программированию

Таким образом, получили двойственную задачу относительно исходной (таблица 5.2).

Решение задач по математическому программированию

При этом цены ресурсов Решение задач по математическому программированию являются условными, в отличие от «внешних цен» на продукцию, известных, как правило, до начала производства.

Цены ресурсов Решение задач по математическому программированию так же называются «внутренними» (или оценками ресурсов), т.к. они задаются не извне, а определяются непосредственно в результате решения задачи.

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

Взаимно двойственные задачи обладают следующими свойствами:

  1. В одной задаче определяется максимум целевой функции, в другой — минимум.
  2. Коэффициенты при переменных в целевой функции одной задачи являются свободными членами системы ограничений в другой.
  3. Каждая из задач задана в стандартной форме, причем в задаче максимизации все неравенства вида Решение задач по математическому программированию, а в задаче минимизации — все неравенства видаРешение задач по математическому программированию.
  4. Матрицы коэффициентов при переменных в системах ограничений обеих задач являются транспонированными друг к другу.
  5. Число неравенств в системе ограничений одной задачи совпадает с числом переменных в другой задаче.
  6. Условия неотрицательности переменных имеются в обеих задачах.

Алгоритм составления двойственной задачи

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

Двойственная задача может быть решена симплекс-методом, а так же с помощью функции Поиск решения в табличном редакторе Microsoft Excel.

Если же исходная задача уже решена симплекс-методом, то решение двойственной задачи может быть найдено по формуле:

Решение задач по математическому программированию

где Решение задач по математическому программированию — матрица-строка коэффициентов при базисных переменных целевой функции входящих в оптимальный базис исходной задачи (в первоначальном виде); Решение задач по математическому программированию — обратная матрица для матрицы Решение задач по математическому программированию, являющейся матрицей коэффициентов при переменных, входящих в оптимальный базис (взятых из первоначальной системы ограничений исходной задачи).

Вернёмся к задаче 5.1. Решим прямую задачу симплекс-методом.

Приведем ЗЛП к каноническому виду.

Для этого приведем систему неравенств к системе уравнений путем введения дополнительных переменных Решение задач по математическому программированию.

Решение задач по математическому программированию

Определение первоначального допустимого базисного решения.

Т.к. каждая дополнительная переменная входит в уравнение с тем же знаком, что и свободный член, стоящий в правой части уравнения, то в качестве базисных переменных можно взять дополнительные Решение задач по математическому программированию и при этом получим допустимое базисное решение.

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

Полагая, что свободные переменные Решение задач по математическому программированию равны 0, получим первое базисное решение:

Математическое программирование задачи с решением

Данное базисное решение является допустимым, т.к. оно неотрицательно.

Составление симплекс-таблицы.

Получено первоначальное допустимое базисное решение, целевая функция содержит только свободные переменные, переходим к составлению первой симплекс-таблицы (таблица 5.3):

Решение задач по математическому программированию

Переход к основному алгоритму симплекс-метода.

I шаг.

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

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

  • Определение новой базисной переменной.

В качестве разрешающего выберем столбец, соответствующий переменной Решение задач по математическому программированию, т.к. ей соответствует наибольший по модулю отрицательный коэффициент (-3).

  • Определение новой свободной переменной.

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

Решение задач по математическому программированию

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

  • Пересчет симплекс-таблицы.

В столбце базисных переменных записываем новый базис: вместо базисной переменной Решение задач по математическому программированию — переменную Решение задач по математическому программированию.

В столбцах, соответствующих базисным переменным проставляем нули и единицы: 1 — против «своей» базисной переменной; 0 — против «чужой» базисной переменной; 0-в последней индексной строке для всех базисных переменных.

Все остальные элементы новой симплекс-таблицы (включая элементы индексной строки) находим по правилу «прямоугольника».

После преобразований получаем новую таблицу (таблица 5.4).

Решение задач по математическому программированию

Базисное решение:

Решение задач по математическому программированию

II шаг.

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

Полученное на II шаге базисное решение (опорный план) не является оптимальным, т.к. в индексной строке есть отрицательный коэффициент (-2).

  • Определение новой базисной переменной.

В качестве разрешающего выберем столбец, соответствующий переменной Решение задач по математическому программированию, т.к. ей соответствует отрицательный коэффициент (-2).

  • Определение новой свободной переменной.

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

Решение задач по математическому программированию

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

  • Пересчет симплекс-таблицы.

В столбце базисных переменных записываем новый базис.

Разрешающий элемент — 1. В столбцах, соответствующих базисным переменным проставляем нули и единицы: 1 — против «своей» базисной переменной; 0 — против «чужой» базисной переменной; О-в последней индексной строке для всех базисных переменных. Все остальные элементы новой симплекс-таблицы (включая элементы индексной строки) находим по правилу «прямоугольника».

После преобразований получаем новую таблицу (таблица 5.5).

Решение задач по математическому программированию

Базисное решение

Решение задач по математическому программированию

III шаг.

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

Полученное на 11 шаге базисное решение (опорный план) не является оптимальным, т.к. в индексной строке есть отрицательный коэффициент (-3).

  • Определение новой базисной переменной.

В качестве разрешающего выберем столбец, соответствующий переменной Решение задач по математическому программированию, т.к. ей соответствует отрицательный коэффициент (-3).

  • Определение новой свободной переменной.

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

Решение задач по математическому программированию

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

  • Пересчет симплекс-таблицы.

В столбце базисных переменных записываем новый базис. Каждый элемент разрешающей строки (которая в новой симплекс таблице будет уже соответствовать переменной Решение задач по математическому программированию) делим на разрешающий элемент (РЭ=9).

Решение задач по математическому программированию

На месте разрешающего элемента получаем 1. В столбцах, соответствующих базисным переменным проставляем нули и единицы: 1 — против «своей» базисной переменной; 0 — против «чужой» базисной переменной; О-в последней индексной строке для всех базисных переменных.

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

Решение задач по математическому программированию

Базисное решение

Решение задач по математическому программированию

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

Решение задач по математическому программированию

при котором

Решение задач по математическому программированию

Т.е. для получения максимальной прибыли от реализации трикотажного полотна в размере 310 д. е. предприятие должно выпустить за планируемый период соответственно 50 и 70 метров трикотажного полотна первого и второго вида.

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

Решение задач по математическому программированию

Матрица коэффициентов

Решение задач по математическому программированию

Найдем обратную матрицу Решение задач по математическому программированию в табличном редакторе Microsoft Excel с помощью встроенной функции МОБР().

Решение задач по математическому программированию

Для этого необходимо:

1) Выделить область для вывода обратной матрицы;

2) Вызвать функцию =МОБР() (рис. 5.1);

3) После выделения диапазона исходных данных одновременно нажать комбинацию клавиш CTRL-SHIFT-ENTER.

В результате получим (рис. 5.2):

Решение задач по математическому программированию

То есть:

Решение задач по математическому программированию

Тогда:

Решение задач по математическому программированию

Или, применяя встроенную функцию МУМНОЖ (рис. 5.3):

Решение задач по математическому программированию

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

Решение задач по математическому программированию

Возможно эта страница вам будет полезна:

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

Двойственный симплекс-метод. Анализ экономико-математической модели двойственной задачи

К оглавлению…

Рассмотрим симплексный алгоритм, который основан на соотношениях между прямой и двойственной задачами. Этот алгоритм эффективно решает определенный класс задач линейного программирования.

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

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

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

Двойственное условие оптимальности. Вводимая в базис переменная определяется как переменная, на которой достигается следующий минимум:

Решение задач по математическому программированию

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

Задача №6.1.

Дана задача линейного программирования:

Минимизировать

Решение задач по математическому программированию

При ограничениях

Решение задач по математическому программированию

Начальная симплекс-таблица имеет вид:

Решение задач по математическому программированию

Среди дополнительных переменных этой задачи Решение задач по математическому программированию и Решение задач по математическому программированию являются избыточными, а Решение задач по математическому программированию — остаточной. Умножим каждое равенство, соответствующее избыточным дополнительным переменным, на -1; в результате правые части этих равенств непосредственно указывают на базисные переменные, которые являются недопустимыми Решение задач по математическому программированию. Этот подход всегда используется при реализации двойственного симплекс-метода.

Поскольку элементы в индексной строке отрицательны для всех Решение задач по математическому программированию начальное базисное решение является оптимальным (но не допустимым). Таким образом, приведенная таблица удовлетворяет требованиям начальной таблицы двойственного симплекс-метода, а именно оптимальности и недопустимости.

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

Решение задач по математическому программированию

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

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

Решение задач по математическому программированию

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

Решение задач по математическому программированию

Решение, представленное в последней таблице, допустимо (и оптимально), поэтому вычисления заканчиваются. Это решение имеет вид

Решение задач по математическому программированию

На рис. 6.1 показана последовательность шагов двойственного сим-плекс-метода при решении этой задачи.

Алгоритм начинается в крайней точке А (которой соответствует недопустимое, но «лучше, чем оптимальное» решение), затем он переходит к точке В (которой также соответствует недопустимое, но «лучше, чем оптимальное» решение) и заканчивается в точке С, уже принадлежащей области допустимых решений.

Решение задач по математическому программированию

Возможно эта страница вам будет полезна:

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

Задача №6.2.

На предприятии имеется возможность выпуска трех видов продукции Решение задач по математическому программированию. При её изготовлении используются ресурсы Решение задач по математическому программированию. Размеры допустимых затрат ресурсов ограничены соответственно величинами Решение задач по математическому программированию. Расход ресурса Решение задач по математическому программированию-го вида на единицу продукции Решение задач по математическому программированию-го вида составляет Решение задач по математическому программированию единиц. Цена единицы продукции Решение задач по математическому программированию-го вида равна Решение задач по математическому программированию.

Требуется:

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

Решение:

Пусть Решение задач по математическому программированию — это количество единиц продукции соответственно Решение задач по математическому программированию, планируемой к выпуску, a Решение задач по математическому программированию— величина прибыли от реализации этой продукции.

Составим экономико-математическую модель задачи. Учитывая значение прибыли от единицы продукции, запишем суммарную величину прибыли целевую функцию — в следующем виде.

Решение задач по математическому программированию

Переменные Решение задач по математическому программированию должны удовлетворять ограничениям, накладываемым на расход ресурсов, имеющихся в распоряжении предприятия:

Решение задач по математическому программированию

По смыслу задачи переменные должны быть неотрицательными:

Решение задач по математическому программированию

Решаем задачу в MS Excel. Составим следующую таблицу:

Решение задач по математическому программированию

Формулы использовали следующие:

Решение задач по математическому программированию

Выполняем последовательность команд: Данные — Поиск решения. Поля в появившемся окне заполняем следующим образом:

Решение задач по математическому программированию

Нажимаем кнопку «Найти решение», получаем результат:

Решение задач по математическому программированию

Т.о., по оптимальному плану следует изготовить 55 ед. продукции второго вида, продукцию первого и третьего вида — не выпускать. Останутся неиспользованными 35 ед. первого ресурса и 205 ед. третьего ресурса. Прибыль при этом будет максимальна и составит 1540 ден. ед.

Составим экономико-математическую модель двойственной задачи.

Пусть Решение задач по математическому программированию — цена единицы ресурса Решение задач по математическому программированию — суммарная стоимость ресурсов. Требуется минимизировать затраты покупающего ресурсы предприятия, при этом нашему предприятию продажа должна быть менее выгодна, чем производство продукции.

Двойственная задача:

Решение задач по математическому программированию

Решаем задачу в MS Excel. Первоначальная таблица:

Решение задач по математическому программированию

Результаты:

Решение задач по математическому программированию

Соответствие между переменными:

Решение задач по математическому программированию

Запишем оптимальный план двойственной задачи:

Решение задач по математическому программированию

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

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

Возможно эта страница вам будет полезна:

Заказать работу по линейному программированию

Транспортная задача (тз)

К оглавлению…

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

В общем виде транспортную задачу можно представить следующим образом: в Решение задач по математическому программированию пунктах производства Решение задач по математическому программированию имеется однородный груз в количествах, соответственно, Решение задач по математическому программированию. Этот груз необходимо доставить в Решение задач по математическому программированию пунктов назначения Решение задач по математическому программированию в количествах, соответственно Решение задач по математическому программированию. Стоимость перевозки 1 ед. груза (тариф) из пункта Решение задач по математическому программированию в пункт Решение задач по математическому программированию равна Решение задач по математическому программированию.

Требуется составить план перевозок так, чтобы:

  1. мощности (запасы) всех поставщиков были реализованы;
  2. заказы всех потребителей были удовлетворены;
  3. суммарные затраты на перевозку были бы минимальны.

Исходные данные транспортной задачи записываются в виде таблицы 8.1

Решение задач по математическому программированию

Виды транспортных задач

В зависимости от соотношения между суммарными запасами груза у поставщиков и суммарными потребностями в нем потребителей транспортные задачи делятся на два вида: закрытые и открытые.

Определение 8.1. Если сумма запасов груза у поставщиков равна суммарной потребности в нем потребителей, т.е.

Решение задач по математическому программированию

то транспортная задача называется закрытой. Определение 2. Если условие (8.1) не выполняется, т.е.

Решение задач по математическому программированию

то транспортная задача называется открытой.

Теорема 8.1 (необходимое и достаточное условие разрешимости ТЗ). Для разрешимости транспортной задачи необходимо и достаточно, чтобы запасы груза в пунктах отправления были равны потребностям в грузе в пунктах назначения, т.е. чтобы выполнялось равенство (8.1).

Возможно эта страница вам будет полезна:

Помощь по линейному программированию

Математическая модель закрытой транспортной задачи

Рассмотрим закрытую транспортную задачу.

  • Неизвестными транспортной задачи являются Решение задач по математическому программированию — объёмы перевозок or каждого Решение задач по математическому программированию — го поставщика каждому Решение задач по математическому программированию-му потребителю. Эти переменные так же можно записать в виде матрицы перевозок:
Решение задач по математическому программированию
  • Так как произведение Решение задач по математическому программированию определяет затраты на перевозку груза от Решение задач по математическому программированию-го поставщика Решение задач по математическому программированию-му потребителю, то суммарные затраты на перевозку всех грузов равны Решение задач по математическому программированию. Т.е. целевая функция будет иметь вид:
Решение задач по математическому программированию
  • Система ограничений транспортной задачи состоит из двух групп уравнений.

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

Решение задач по математическому программированию

Вторая группа состоит из Решение задач по математическому программированию уравнений и выражает требование полностью удовлетворить запросы всех Решение задач по математическому программированию потребителей:

Решение задач по математическому программированию
Решение задач по математическому программированию

Кроме того, переменные Решение задач по математическому программированию должны быть неотрицательны:

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

Особенности экономико-математической модели ТЗ

  1. Система ограничений представляет собой систему уравнений (т.е. ТЗ задана в канонической форме);
  2. Коэффициенты при переменных системы ограничений равны единице или нулю;
  3. Каждая переменная входит только в два уравнения системы ограничений.

Число переменных Решение задач по математическому программированию в ТЗ с Решение задач по математическому программированию пунктами отправления и Решение задач по математическому программированию пунктами назначения равно Решение задач по математическому программированию, а число уравнений в системах (8.2) и (8.3) равно Решение задач по математическому программированию. Так как мы предполагаем, что выполняется условие (8.1), то число линейно независимых уравнений равно Решение задач по математическому программированию. Следовательно, опорный план транспортной задачи, может иметь не более Решение задач по математическому программированию отличных от нуля неизвестных.

Если в опорном плане число отличных от нуля неизвестных равно Решение задач по математическому программированию, то план является невырожденным, а если меньше — то вырожденным.

Возможно эта страница вам будет полезна:

Контрольная работа по линейному программированию

Открытая транспортная задача (транспортная задача с нарушенным балансом)

В открытой ТЗ сумма запасов не совпадает с суммой потребностей, поэтому для решения открытой ТЗ ее сводят к закрытой ТЗ.

  • Если Решение задач по математическому программированию, т.е. суммарный запас груза поставщиков больше суммарного спроса потребителей, то в задачу вводится фиктивный Решение задач по математическому программированию -й потребитель с потребностью равной разности объемов запаса и потребления Решение задач по математическому программированию и стоимостью перевозок
Решение задач по математическому программированию
  • Если Решение задач по математическому программированию т.е. объем потребления превышает объем запасов, то вводится фиктивный Решение задач по математическому программированию-й поставщик с запасом Решение задач по математическому программированию и стоимостью перевозок Решение задач по математическому программированию.

После добавления фиктивного потребителя или фиктивного поставщика ТЗ становится закрытой, а, следовательно, и разрешимой.

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

  1. Нахождение исходного опорного решения;
  2. Проверка полученного решения на оптимальность;
  3. Переход от одного опорного решения к другому до достижения оптимального значения (минимума) целевой функции.

При решении ТЗ ее условие и исходное опорное решение записывается в распределительную таблицу. Клетки, в которых записан объем перевозки от Решение задач по математическому программированию -го поставщика к Решение задач по математическому программированию -му потребителю называются занятыми, им соответствуют базисные переменные опорного решения. Остальные, незанятые клетки называются пустыми и им соответствуют свободные переменные. В верхнем правом углу каждой клетки записывается тариф перевозки груза от данного Решение задач по математическому программированию-го поставщика к Решение задач по математическому программированию-му потребителю.

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

Для определения исходного опорного плана ТЗ существует несколько методов. Рассмотрим на примере два из них: метод «северо-западного угла» и метод минимального элемента (метод наименьшей стоимости).

Задача №8.1.

На складах Решение задач по математическому программированию имеются запасы продукции в количествах 90, 400, 110 т соответственно. Потребители Решение задач по математическому программированию должны получить эту продукцию в количествах 140, 300, 160 т соответственно. Построить первоначальный допустимый опорный план закрепления потребителей за поставщиками. Найти оптимальный план закрепления потребителей за поставщиками, при котором сумма затрат на перевозки была бы минимальной. Расходы по перевозке 1 т продукции заданы матрицей Решение задач по математическому программированию в денежных единицах.

Решение задач по математическому программированию

Решение:

Запишем исходные данные задачи в виде таблицы 8.2

Решение задач по математическому программированию

Математическая модель задачи

Матрица перевозок:

Решение задач по математическому программированию

Система ограничений:

Решение задач по математическому программированию

Целевая функция:

Решение задач по математическому программированию

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

Запись математической модели данной транспортной задачи в табличном редакторе Microsoft Excel имеет вид (рис. 8.1).

Решение задач по математическому программированию
  • Найдем исходное опорное решение методом «северо-западного угла»:
Решение задач по математическому программированию

В результате получен исходный опорный план, который является допустимым, так как все грузы (запасы поставщиков) вывезены, спрос потребителей удовлетворен, т.е. план соответствует системе ограничений ТЗ.

Число занятых клеток в таблице равно 5,Решение задач по математическому программированию =3 + 3-1 = 5 , т.е. условие невырожденности выполнено. Получим исходное опорное решение:

Решение задач по математическому программированию

Стоимость перевозки (значение целевой функции) при исходном опорном решении составляет:

Решение задач по математическому программированию

Метод минимального тарифа (элемента) (метод наименьших затрат)

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

Найдем исходное опорное решение для примера 8.1 методом минимального элемента:

Возможны два варианта

Решение задач по математическому программированию

Опорный план:

Решение задач по математическому программированию

Стоимость перевозки (значение целевой функции):

Решение задач по математическому программированию
Решение задач по математическому программированию

Опорный план:

Решение задач по математическому программированию

Стоимость перевозки (значение целевой функции):

Решение задач по математическому программированию

Проверка оптимальности плана и перераспределение поставок с помощью метода потенциалов.

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

Покажем, как нужно пользоваться методом потенциалов на примере первоначального плана, полученного выше по методу северозападного угла (рис. 8.2).

Найдем потенциалы по базисным (загруженным) клеткам таблицы с помощью формул

Решение задач по математическому программированию

положив и Решение задач по математическому программированию:

Решение задач по математическому программированию

Вычисляем оценки

Решение задач по математическому программированию

свободных клеток:

Решение задач по математическому программированию

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

Решение задач по математическому программированию

В левых нижних углах соответствующих клеток находятся оценки Решение задач по математическому программированию.

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

Цикл — совокупность клеток распределительной таблицы, из которых только одна клетка свободная, та, для которой строится цикл. Клетки, составляющие цикл, расположены в углах замкнутой ломаной линии, каждый отрезок которой лежит на одном и том же столбце распределительной таблицы.

Каждой клетке цикла поставим в соответствие знаки «+» и «—», которые при обходе цикла будут чередоваться. При этом свободную клетку (начальную клетку цикла) всегда считаем положительной.

Строим цикл с началом в клетке (3,1) с минимальной оценкой Решение задач по математическому программированию, он будет включать в себя клетки (см. таблицу 8.4):

Решение задач по математическому программированию

Величина груза, перемещаемая с помощью цикла равна наименьшей из величии, расположенных в отрицательных клетках:

Решение задач по математическому программированию

Найденную величину прибавим в положительных клетках цикла и вычтем в отрицательных. Клетка (2,1) станет свободной. Получим новый план перевозок, который занесём в таблицу 8.4:

Решение задач по математическому программированию

Опорный план:

Решение задач по математическому программированию

Стоимость перевозки (значение целевой функции):

Решение задач по математическому программированию

Построена таблица с новым планом, состоящим из старых поставок, не вовлечённых в цикл и новых — в вершинах рассмотренного цикла. Проведём перерасчёт потенциалов Решение задач по математическому программированию и оценок Решение задач по математическому программированию:

Решение задач по математическому программированию

Оценки для незанятых клеток:

Решение задач по математическому программированию

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

Внесём данные в таблицу (таблица 8.5):

Решение задач по математическому программированию

Строим цикл с началом в клетке (1,3) с оценкой Решение задач по математическому программированию включать в себя клетки (см. таблицу 8.5):

Решение задач по математическому программированию

Тогда

Решение задач по математическому программированию

Перераспределим груз по циклу, указанному в таблице 6.5 пунктиром на величину Решение задач по математическому программированию. Получим следующую распределительную таблицу:

Решение задач по математическому программированию

Опорный план:

Решение задач по математическому программированию

Стоимость перевозки (значение целевой функции):

Решение задач по математическому программированию

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

Решение задач по математическому программированию

Оценки для незанятых клеток:

Решение задач по математическому программированию

План не является оптимальным, так как Решение задач по математическому программированию. Его нужно преобразовать в новый план, загрузив клетку (2,1). Цикл (см. таблицу 8.7):

Решение задач по математическому программированию

По этому контуру находим поставку

Решение задач по математическому программированию

Прибавляем Решение задач по математическому программированию к элементам, стоящим у вершин со знаком (+) и вычитаем из элементов, стоящих у вершин со знаком (-). Получаем новое опорное решение (см. таблицу 8.8)

Решение задач по математическому программированию

Стоимость перевозки (значение целевой функции):

Решение задач по математическому программированию
Решение задач по математическому программированию
Решение задач по математическому программированию

Исследуя этот план аналогично предыдущим, находим потенциалы (они приведены в таблице 8.8), и по ним — оценки свободных клеток:

Решение задач по математическому программированию

Отрицательных оценок нет, следовательно, в таблице содержится оптимальный план.

Табличная модель.

Вводим данные в таблицу Excel

Решение задач по математическому программированию
Решение задач по математическому программированию
Решение задач по математическому программированию

Вывод: Минимальные суммарные затраты на перевозку груза равны 1280 д.е. Они достигаются путем распределения поставок, представленных в ячейках [B4:D6]. Так, например, поставщик А1 должен доставить груз только потребителю ВЗ в количестве 90 единиц. Поставщик А2 должен поставить груз к потребителю В1 в количестве 30 ед., к потребителю В2 300 единиц и к потребителю ВЗ — 70 единиц.. Поставщик A3 должен доставить груз только потребителю В1 в количестве 90 ед. Поставщик A3 должен доставить груз только потребителю В1 в количестве 110 ед.

Возможно эта страница вам будет полезна:

Линейное программирование в Excel

Модели целочисленного линейного программирования

К оглавлению…

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

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

Решение задач по математическому программированию

при ограничениях

Решение задач по математическому программированию

а также дополнительном ограничении:

Решение задач по математическому программированию

Для решения задач целочисленного программирования используют метод Гомори (метод отсечений) и метод ветвей и границ.

Идея метода Гомори состоит в том, что сначала задача решается без условия целочисленности. Если полученное решение целочисленное, то задача решена. В противном случае к ограничениям задачи добавляется новое ограничение, обладающее следующими свойствами: оно должно быть линейным;

должно отсекать найденный оптимальный нецелочисленный план;

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

Далее задача решается с учетом нового ограничения. После этого в случае необходимости добавляется еще одно ограничение и т.д.

Алгоритм метода Гомори

  • С помощью симплекс-метода находят решение задачи (9.1) — (9.3) без учета требования целочисленности переменных. Если полученное решение целочисленное, то задача (9.1) — (9.4) решена. Если задача (9.1) -(9.3) неразрешима (т.е. не имеет конечного оптимума или условия ее противоречивы), то и задача (9.1) — (9.4) также неразрешима.
  • Если полученное решение нецелочисленное, то составляют дополнительное ограничение для переменной, которая в оптимальном плане задачи (9.1)—(9.3) имеет максимальную дробную часть, а в оптимальном плане задачи (9.1)—(9.4) должна быть целочисленной. Для составления дополнительного ограничения используется последняя симплекс-таблица. Ограничение имеет вид:
Решение задач по математическому программированию

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

  • Неравенство (9.5) заменяют уравнением путем ввода дополнительной переменной и добавляют его к ранее решенной задаче, получают новую задачу. Решают ее симплексным методом, если оптимальный план новой задачи целочисленный, то исходная задача решена. В противном случае составляется новое дополнительное ограничение и т.д., пока не будет получено целочисленное решение задачи.

Возможно эта страница вам будет полезна:

Курсовая работа по линейному программированию

Задача №9.1.

На приобретение оборудования (станков) для участка цеха выделены 30 т. р. Производственная площадь участка — 70 м2. Имеется возможность закупить станки двух видов: стоимостью 5 т. р. и 3 т. р. Станок первого вида требует для установки 12 м2 и дает продукции на 8 т. р. в месяц. Станок второго вида требует 6 м» площади и дает продукции на 2 т. р. в месяц. Определить оптимальный план приобретения оборудования, при котором производительность участка цеха в месяц была бы максимальной.

Решение:

  • Составим математическую модель задачи:

Решение задач по математическому программированию — количество станков первого вида;

Решение задач по математическому программированию — количество станков второго вида;

Решение задач по математическому программированию

целевая функция (производительность участка в месяц в ден. ед.).

Система ограничений:

Решение задач по математическому программированию
  • С помощью симплекс-метода найдем решение задачи без учета требования целочисленности переменных. Для этого приведем задачу к каноническому виду, т.е. в системе ограничений введем две дополнительные переменные Решение задач по математическому программированию и Решение задач по математическому программированию:
Решение задач по математическому программированию

В качестве базисных переменных можем взять дополнительные переменные Решение задач по математическому программированию и Решение задач по математическому программированию.

Составим симплексную таблицу (табл. 9.1):

I шаг.

Решение задач по математическому программированию

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

В качестве разрешающего выберем столбец, соответствующий переменной Решение задач по математическому программированию, т.к. ей соответствует наибольший по модулю отрицательный коэффициент (-8).

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

Вторая строка (соответствующая базисной переменной Решение задач по математическому программированию) является разрешающей (ей соответствует минимальное оценочное отношение 5,8).

Разрешающий элемент 12, который находится на пересечении разрешающего столбца и разрешающей строки.

II шаг.

Производим пересчет симплекс-таблицы (в табл. 9.2 приведён конечный результат).

Решение задач по математическому программированию

Полученный опорный план

Решение задач по математическому программированию

является оптимальным, т.к. индексная строка не содержит отрицательных элементов.

Решение задач по математическому программированию

Полученное решение нецелочисленное, поэтому составим дополнительное ограничение для переменной Решение задач по математическому программированию, которая в оптимальном плане задачи должна быть целочисленной. Для составления дополнительного ограничения воспользуемся последней симплекс-таблицей. Выпишем уравнение, содержащее неизвестную Решение задач по математическому программированию:

Решение задач по математическому программированию

Дополнительное ограничение будет иметь вид:

Решение задач по математическому программированию

(фигурные скобки обозначают дробную часть числа).

Решение задач по математическому программированию

С помощью дополнительной переменной преобразуем данное неравенство в уравнение:

Решение задач по математическому программированию

и присоединим его к исходной системе ограничений, получим новую задачу. Для ее решения в последнюю симплекс-таблицу исходной задачи добавляем строку, соответствующую введенному ограничению (табл. 9.3).

Решение задач по математическому программированию

План

Решение задач по математическому программированию

недопустим, так как -5/6 < 0, зато Решение задач по математическому программированию-строка (0, 2, 0, 2/3, 0) не содержит отрицательных чисел. Это означает, что пашу задачу можно решить двойственным симплекс методом.

При решении задачи двойственным симплекс методом за разрешающую принимается строка с максимальным по абсолютной величине отрицательным Решение задач по математическому программированию. У нас это строка Решение задач по математическому программированию. За разрешающий принимается столбец с минимальным значением- Решение задач по математическому программированию, где аРешение задач по математическому программированию (столбец Решение задач по математическому программированию). Разрешающий элемент выделяем в таблице (см. табл. 9.3) и делаем для него шаг Жордана-Гаусса:

Решение задач по математическому программированию

План

Решение задач по математическому программированию

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

Решение задач по математическому программированию

Это ограничение добавляем в последнюю симплексную таблицу и решаем новую задачу двойственным симплекс-методом.

Решение задач по математическому программированию

За разрешающую принимаем строку с максимальным по абсолютной величине отрицательным Решение задач по математическому программированию. У нас это строка Решение задач по математическому программированию. За разрешающий принимается столбец с минимальным значением—Решение задач по математическому программированию. где Решение задач по математическому программированию (столбец Решение задач по математическому программированию). Разрешающий элемент выделяем в таблице (см. табл. 9.5) и делаем для него шаг Жордана-Гаусса:

Решение задач по математическому программированию

План

Решение задач по математическому программированию

оптимален и является целочисленным, следовательно, оптимальное решение исходной задачи имеет вид:

Решение задач по математическому программированию

Решение задачи целочисленной оптимизации в Microsoft Excel осуществляется командой Поиск решения из меню Данные. Но при решении целочисленных задач необходимо в форму представления данных ввести требование целочисленности переменных.

Вводим данные в таблицу Excel, как представлено на рисунке 9.1

Решение задач по математическому программированию

Вызываем диалоговое окно Поиск решения и заносим в этом окне необходимые данные (рис. 9.3)

Решение задач по математическому программированию
Решение задач по математическому программированию

Кстати готовые на продажу задачи тут, и там же теория из учебников может быть вам поможет она.

Метод ветвей и границ

К оглавлению…

Задача №9.2.

Методом ветвей и границ решить задачу

Решение задач по математическому программированию

при ограничениях

Решение задач по математическому программированию

Решение:

Найдём оптимальное решение этой задачи как непрерывной (симплекс-методом).

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

Решение задач по математическому программированию

Поэтому можно сразу обратиться к таблице Гаусса (табл.9.1) и заполнить соответствующие блоки.

Решение задач по математическому программированию

Оптимальное решение задачи:

Решение задач по математическому программированию

Верхний индекс у переменных соответствует номеру задачи.

В полученном решении Решение задач по математическому программированию не удовлетворяет требованиям цело-численности.

В связи с этим для дальнейшего решения составим задачи с граничными условиями, исключающими возможность получения нецелочисленного значения Решение задач по математическому программированию. Такими граничными условиями являются

Решение задач по математическому программированию

Граничное условие Решение задач по математическому программированию входит в Задачу 2, решение которой найдём в Excel, используя надстройку «.Поискрешения».

  • Создадим таблицу для ввода исходных данных: переменных, целевой функции,ограничений.
  • Введем начальные нулевые значения для Решение задач по математическому программированию и Решение задач по математическому программированию.
  • Зададим целевую функцию в ячейке F3 и ограничения в ячейках Е6, Е7 и Е8 (рис. (9.5).
Решение задач по математическому программированию

Далее для исключения получения нецелочисленного значения

Решение задач по математическому программированию

введём дополнительные граничные условия и решим последовательно две задачи: Задачу 3-е условиями

Решение задач по математическому программированию

и Задачу 4-е условиями

Решение задач по математическому программированию

Решения этих задач представлены, соответственно, на рис. 9.8 и рис. 9.9.

Решение задач по математическому программированию

Схема решения всех этих задач приведена на рис. 9.10, а результат решения — в таблице 2

Решение задач по математическому программированию

Из таблицы 2 видно, что решение Задачи 3 наиболее близкое к непрерывному по значениям переменных (см. таблицу 1), не является оптимальным. Оптимальным же является решение Задачи 4, в котором значения переменных существенно отличаются от непрерывного решения. Приведённый пример наглядно показывает, что округление оптимального решения непрерывной задачи может не обеспечить получения оптимального решения целочисленной задачи.