Оглавление:
![Математическое программирование задачи с решением](https://lfirmal.com/wp-content/uploads/2020/10/Математическое-программирование-задачи-с-решением.png)
Прежде чем изучать готовые решения задач по математическому программированию, нужно знать теорию, поэтому для вас я подготовила краткую теорию по предмету «математическое программирование», после которой подробно решены задачи.
Эта страница подготовлена для школьников и студентов.
Если что-то непонятно — вы всегда можете написать мне в WhatsApp и я вам помогу! |
Математическое программирование
Математическое программирование – раздел высшей математики, разрабатывающий теорию и численные методы решения многомерных экстремальных задач с ограничениями, т. е. задач на экстремум функции многих переменных с ограничениями на область изменения этих переменных.
Жордановы исключения
Пусть дана система линейных уравнений
![Математическое программирование задачи с решением](https://lfirmal.com/wp-content/uploads/2020/03/image-45406.png)
В матрице этой системы выберем отличный от нуля элемент
. Этот элемент называется разрешающим элементом,
— й столбец матрицы
— разрешающим столбцом, а
— я строка — разрешающей строкой. Рассмотрим новую систему уравнений
![Решение задач по математическому программированию](https://lfirmal.com/wp-content/uploads/2020/03/image-45410.png)
с матрицей коэффициенты и свободные члены этой системы определяются по формулам
![Решение задач по математическому программированию](https://lfirmal.com/wp-content/uploads/2020/03/image-45412.png)
Если же . го принимаем
. Таким образом,
— е уравнения в системах (1.1) и (1.2) одинаковы, а коэффициенты при
во всех уравнениях системы (1.2), кроме
— го, равны нулю.
Системы (1.1) и (1.2) одновременно совместны или несовместны. В случае совместности эти системы равносильны (их решения совпадают).
Для определения элемента матрицы
применяется правило прямоугольника
Рассмотрим четыре элемента матрицы (элемент, подлежащий преобразованию),
(разрешающий элемент) и элементы
и
. Для нахождения элемента
следует из элемента
вычесть произведение элементов
и
расположенных в противоположных вершинах прямоугольника, делённое на разрешающий элемент
![Решение задач по математическому программированию](https://lfirmal.com/wp-content/uploads/2020/03/image-45425.png)
Аналогичным образом можно преобразовать систему (1.2), приняв за разрешающий элемент матрицы элемент
, причём
.
После этого преобразования все коэффициенты при , кроме
, обратятся в нуль. Полученная система может быть снова преобразована и т.д.
Возможно эта страница вам будет полезна:
Предмет математическое программирование |
Задача №1.1.
Найти решение системы:
![Решение задач по математическому программированию](https://lfirmal.com/wp-content/uploads/2020/03/image-45430.png)
Систему решить методом Жордано-Гаусса: 1) аналитически; 2) с помощью MS Excel.
Решение:
Запишем систему в виде жордановой таблицы.
![Решение задач по математическому программированию](https://lfirmal.com/wp-content/uploads/2020/03/image-45431.png)
1 шаг. Разрешающий столбец — 1; разрешающая строка — 3; разрешающий элемент . Применим правило прямоугольника.
![Решение задач по математическому программированию](https://lfirmal.com/wp-content/uploads/2020/03/image-45433.png)
2 шаг. Делим элементы разрешающей строки па -3 и опять применяем правило прямоугольника:
![Решение задач по математическому программированию](https://lfirmal.com/wp-content/uploads/2020/03/image-45434.png)
3 шаг. В качестве разрешающего элемента выбираем . Делим элементы четвёртой строки на 4 и проводим ещё один шаг жордановых исключений:
![Решение задач по математическому программированию](https://lfirmal.com/wp-content/uploads/2020/03/image-45436.png)
4 шаг. Умножаем первую (разрешающую) строку на -1. Разрешающий столбец — третий.
![Математическое программирование задачи с решением](https://lfirmal.com/wp-content/uploads/2020/03/image-45437.png)
Система имеет единственное решение
![Решение задач по математическому программированию](https://lfirmal.com/wp-content/uploads/2020/03/image-45438.png)
Используем для решения системы MS Excel:
![Решение задач по математическому программированию](https://lfirmal.com/wp-content/uploads/2020/03/image-45439.png)
![Решение задач по математическому программированию](https://lfirmal.com/wp-content/uploads/2020/03/image-45440.png)
Задача №1. 2.
Решить систему уравнений.
![Решение задач по математическому программированию](https://lfirmal.com/wp-content/uploads/2020/03/image-45441.png)
Систему решить методом Жордано-Гаусса с помощью MS Excel.
Решение:
![Решение задач по математическому программированию](https://lfirmal.com/wp-content/uploads/2020/03/image-45442.png)
Пусть
![Решение задач по математическому программированию](https://lfirmal.com/wp-content/uploads/2020/03/image-45443.png)
тогда
![Решение задач по математическому программированию](https://lfirmal.com/wp-content/uploads/2020/03/image-45444.png)
Возможно эта страница вам будет полезна:
Примеры решения задач по математическому программированию |
Постановка задачи математического программировании
Рассмотрим оптимизационные задачи, решаемые методами линейного программирования (ЛП), в которых оптимизируемая функция является линейной, а ограничения
задаются линейными неравенствами. Ограничения задают выпуклые линейные многогранники в конечном линейном пространстве. Целевые функции также линейны.
Задача линейного программирования (ЗЛП) записывается следующим образом: найти переменные , при которых целевая функция
![Решение задач по математическому программированию](https://lfirmal.com/wp-content/uploads/2020/03/image-45448.png)
была бы максимальной (минимальной), не нарушая следующих условий:
![Решение задач по математическому программированию](https://lfirmal.com/wp-content/uploads/2020/03/image-45449.png)
Все три случая можно привести к так называемой канонической форме, введя дополнительные переменные
![Решение задач по математическому программированию](https://lfirmal.com/wp-content/uploads/2020/03/image-45450.png)
где — количество дополнительных переменных и условие неотрицательности искомых переменных
.
В результате решения задачи находится некий план (программа) работы некоторого предприятия. Отсюда и появилось слово «программирование». Слово линейное указывает на линейный характер зависимости, как в целевой функции, так и в системе ограничений. Задача обязательно носит экстремальный характер, т.е. состоит в отыскании максимума или минимума (экстремума) целевой функции. Допустимым решением (планом) задачи линейного программирования называется любой -мерный вектор
удовлетворяющий системе ограничений и условиям неотрицательности. Множество всех допустимых решений задачи образуют область допустимых решений (сокращенно ОДР).
Элементы линейной алгебры и геометрии выпуклых множеств
Система линейных уравнений с
переменными имеет вид
![Решение задач по математическому программированию](https://lfirmal.com/wp-content/uploads/2020/03/image-45456.png)
В задачах линейного программирования представляют интерес системы, в которых максимальное число независимых уравнений системы меньше числа переменных, т.е.
.
Будем полагать, что в системе (2.1) все уравнений системы независимы, т.е.
и соответственно
.
Любые переменных системы
линейных уравнений с
переменными (
) называются основными (или базисными), если определитель матрицы коэффициентов при них отличен от нуля. Тогда остальные
переменных называются неосновными (или свободными).
Среди бесконечного множества решений системы выделяют так называемые базисные решения.
Базисным решением системы линейных уравнений с
переменными называется решение, в котором все
неосновных переменных равны нулю.
В задачах линейного программирования особый интерес представляют допустимые базисные решения, или, как их еще называют, опорные планы. Число базисных решений является конечным, так как оно равно числу групп основных переменных, не превосходящему . Базисное решение, в котором хотя бы одна из основных переменных равна нулю, называется вырожденным.
Выпуклые множества точек:
В школьном курсе математики выпуклыми назывались многоугольники, целиком расположенные по одну сторону от прямых, на которых лежат их стороны.
![Решение задач по математическому программированию](https://lfirmal.com/wp-content/uploads/2020/03/image-45462.png)
Например, многоугольник на рис. 2.1, а — выпуклый, а многоугольник на рис. 2.1, б не является выпуклым (он расположен по обе стороны от прямой ).
Общим определяющим свойством, которое отличает выпуклый многоугольник от невыпуклого, является то, что если взять любые две его точки и соединить их отрезком, то весь отрезок будет принадлежать этому многоугольнику. Это свойство может быть принято за определение выпуклого множества точек.
Множество точек называется выпуклым, если оно вместе с любыми двумя своими точками содержит весь отрезок, соединяющий эти точки.
Выпуклые множества обладают важным свойством, которое устанавливается следующей теоремой.
Теорема 2.1. Пересечение (общая часть) любого числа выпуклых множеств есть выпуклое множество.
Среди точек выпуклого множестваможно выделить внутренние, граничные и угловые точки. Точка множества называется внутренней, если в некоторой ее окрестности содержатся точки только данного множества. Точка множества называется граничной, если в любой ее окрестности содержатся как точки, принадлежащие данному множеству, так и точки, не принадлежащие ему. Точка множества называется угловой (или крайней), если она не является внутренней ни для какого отрезка, целиком принадлежащего данному множеству.
![Решение задач по математическому программированию](https://lfirmal.com/wp-content/uploads/2020/03/image-45464.png)
На рис. 2.2 приведены примеры различных точек многоугольника: внутренней (точки ), граничной (точка
) и угловых (точки
). Точка
— угловая, так как для любого отрезка, целиком принадлежащего многоугольнику, например, отрезка
, она не является внутренней; точка
— внутренняя для отрезка
, но этот отрезок не принадлежит целиком многоугольнику.
Множество точек называется замкнутым, если включает все свои граничные точки. Множество точек называется ограниченным, если существует шар (круг) радиуса конечной длины с центром в любой точке множества, который полностью содержит в себе данное множество; в противном случае множество называется неограниченным.
Если фигура ограничена только прямыми или их отрезками, то число ее угловых точек конечно; в случае криволииейпости границ фигура содержит бесконечно много угловых точек, что позволяет сделать следующее определение.
Выпуклое замкнутое множество точек пространства (плоскости), имеющее конечное число угловых точек, называется выпуклым многогранником (,многоугольником•), если оно ограниченное, и выпуклой многогранной (многоугольной) областью, если оно неограниченное.
Множество всех точек образует
-мерное точечное (векторное) пространство. При
точки и фигуры «
-мерного пространства» не имеют реального геометрического смысла и все исследования объектов этого пространства необходимо проводить в аналитической форме.
Тем не менее оказывается целесообразным и в этом случае использовать геометрические понятия для облегчения представлений об объектах
— мерного пространства.
Геометрический смысл решений неравенств, уравнений и их систем
Теорема 2.2. Множество решений неравенства с двумя переменными
![Решение задач по математическому программированию](https://lfirmal.com/wp-content/uploads/2020/03/image-45474.png)
является одной из двух полуплоскостей, на которые вся плоскость делится прямой
![Решение задач по математическому программированию](https://lfirmal.com/wp-content/uploads/2020/03/image-45475.png)
включая и эту прямую, а другая полуплоскость с той же прямой есть множество решений неравенства
![Решение задач по математическому программированию](https://lfirmal.com/wp-content/uploads/2020/03/image-45476.png)
Учитывая, что множество точек, удовлетворяющих уравнению
![Решение задач по математическому программированию](https://lfirmal.com/wp-content/uploads/2020/03/image-45477.png)
при , является плоскостью, а при
— ее обобщением в
-мерном пространстве — гиперплоскостью, теорему 2.2 можно распространить на случай трех и более переменных.
Теорема 2.3. Множество всех решений линейного неравенства с переменными
![Решение задач по математическому программированию](https://lfirmal.com/wp-content/uploads/2020/03/image-45481.png)
является одним из полупространств, на которые все пространство делится плоскостью или гиперплоскостью (2.2), включая и эту плоскость (гиперплоскость).
Рассмотрим множество решений систем неравенств:
Теорема 2.4. Множество решений совместной системы линейных неравенств с двумя переменными
![Решение задач по математическому программированию](https://lfirmal.com/wp-content/uploads/2020/03/image-45482.png)
является выпуклым многоугольником (или выпуклой многоугольной областью).
При построении областей решений систем неравенств могут встретиться и другие случаи: множество решений — выпуклая многоугольная область (рис. 2.3, а); одна точка (рис. 2.3, б); пустое множество, когда система неравенств несовместна (рис. 2.3, в).
![Решение задач по математическому программированию](https://lfirmal.com/wp-content/uploads/2020/03/image-45483.png)
Теорема 2.5. Множество решений совместной системы от линейных неравенств с переменными является выпуклым многогранником (выпуклой многогранной областью) в
-мерном пространстве.
Рассмотрим множество допустимых решений системы линейных уравнений с
переменными.
Теорема 2.6. Множество всех допустимых решений совместной системы линейных уравнений с
переменными (
) является выпуклым многогранником (выпуклой многогранной областью) в
-мерном пространстве.
Возможно эта страница вам будет полезна:
Заказать работу по математическому программированию |
Графический метод решения ЗЛП
Методы решения задач линейного программирования относятся к вычислительной математике. Задачу линейного программрования можно решать аналитическими и графическими методами. Аналитические методы, которые представляют собой последовательность вычислений по некоторым правилам, являются основой для решения задачи на компьютере. Их единственный недостаток заключается в том, что в отличие от графических методов, они совершенно не наглядны. Графические же методы достаточно наглядны, но они пригодны лишь для решения таких задач, что даёт возможность представлять задачу на плоскости.
Рассмотрим задачу линейного программирования с двумя переменными
![Решение задач по математическому программированию](https://lfirmal.com/wp-content/uploads/2020/03/image-45486.png)
Такая задача может быть решена графически (геометрически) ввиду того, что в этом случае легко строить ОДР (область допустимых решений).
Алгоритм графического решения задачи линейного программирования состоит в выполнении следующих действий.
1) Построить ОДР.
2) Построить вектор нормали целевой функции (он указывает па направление возрастания целевой функции).
3) Построить нижнюю и верхнюю опорные прямые и
, т. е. крайние линии уровня целевой функции, имеющие общие точки с ОДР.
4) Определить координаты экстремальных точек .
Примечания.
1) Если ОДР — пустое множество, то задача не имеет решения ввиду несовместности системы ограничений.
2) Если ОДР неограничена по направлению вектора , то сама целевая функция неограничена сверху в этой области, и принимаем
. Если ОДР неограничена в направлении, противоположном
, то принимаем
.
Графически может быть решена также задача линейного программирования, заданная в канонической форме, при условии (
— число переменных,
— ранг системы уравнений). Для этого задачу надо привести к симметрическому виду.
Возможно эта страница вам будет полезна:
Помощь по математическому программированию |
Задача №2.1.
Найти все базисные решения системы уравнений.
![Решение задач по математическому программированию](https://lfirmal.com/wp-content/uploads/2020/03/image-45497.png)
Решение:
Запишем систему в таблицу. Жордановы исключения будем выполнять в пакете MS Excel (Таблицы 2.1 — 2.4).
![Решение задач по математическому программированию](https://lfirmal.com/wp-content/uploads/2020/03/image-45498.png)
Эквивалентная система:
![Решение задач по математическому программированию](https://lfirmal.com/wp-content/uploads/2020/03/image-45499.png)
Система приведена к единичному базису, и переменные составляют один из базисов системы переменных
. Поэтому при нулевых значениях свободных переменных
получаем одно из базисных решений
Б, = (1,2, 0, 0).
В данном случае , поэтому всего базисных решений может 2 4!
быть не более . Другими базисами могут оказаться следующие группы переменных:
![Решение задач по математическому программированию](https://lfirmal.com/wp-content/uploads/2020/03/image-45505.png)
Для того чтобы найти второе базисное решение , вернемся к таблице 2.3. Вычеркнем из неё первую строку (первая и третья строки пропорциональны) и примем за разрешающий третий столбец. Получим таблицы 2.3 — 2.6.
![Решение задач по математическому программированию](https://lfirmal.com/wp-content/uploads/2020/03/image-45507.png)
Сделав шаг жордановых исключений, перейдём к базису и при
(таблица 2.7) получим ещё одно базисное решение
:
![Решение задач по математическому программированию](https://lfirmal.com/wp-content/uploads/2020/03/image-45510.png)
Преобразовывая последовательно шагами жордановых исключений таблицы 2.5, 2.1 получим другие базисные решения:
Базисные переменные . Свободные переменные
. Базисное решение
![Решение задач по математическому программированию](https://lfirmal.com/wp-content/uploads/2020/03/image-45513.png)
![Решение задач по математическому программированию](https://lfirmal.com/wp-content/uploads/2020/03/image-45514.png)
Базисные переменные . Свободные переменные
. Базисное решение
![Решение задач по математическому программированию](https://lfirmal.com/wp-content/uploads/2020/03/image-45516.png)
![Решение задач по математическому программированию](https://lfirmal.com/wp-content/uploads/2020/03/image-45517.png)
Базисные переменные . Свободные переменные
. Базисное решение
![Решение задач по математическому программированию](https://lfirmal.com/wp-content/uploads/2020/03/image-45519.png)
![Математическое программирование задачи с решением](https://lfirmal.com/wp-content/uploads/2020/03/image-45520.png)
Базисные переменные . Свободные переменные
. Базисное решение
![Решение задач по математическому программированию](https://lfirmal.com/wp-content/uploads/2020/03/image-45523.png)
![Решение задач по математическому программированию](https://lfirmal.com/wp-content/uploads/2020/03/image-45524.png)
Задача №2.2.
Записать в форме стандартной задачи линейного программирования следующую задачу:
![Решение задач по математическому программированию](https://lfirmal.com/wp-content/uploads/2020/03/image-45525.png)
Решение:
Приведём систему ограничительных уравнений к разрешённой форме, выделяя некоторый базис переменных. Затем, опустив базисные переменные, перейдём к эквивалентной системе неравенств. Для завершения преобразований останется выразить целевую функцию через переменные, вошедшие в полученную систему неравенств.
Эти преобразования удобнее проводить одновременно, приписав к жордановой таблице снизу строку для целевой функции (—строку). В процессе жордановых исключений эту строку не следует делать разрешающей, но преобразовывать её элементы нужно по обычным правилам. В результате целевая функция, как и базисные переменные, окажется выраженной через свободные переменные.
В условиях данной задачи разрешающие элементы можно выбрать произвольно
![Решение задач по математическому программированию](https://lfirmal.com/wp-content/uploads/2020/03/image-45527.png)
Учитывая неотрицательность базисных переменных в последней таблице, опускаем их и приходим к эквивалентной системе неравенств. а вместе с тем и к симметричной форме записи задачи:
![Решение задач по математическому программированию](https://lfirmal.com/wp-content/uploads/2020/03/image-45529.png)
Задача №2.3.
Решить графически следующую задачу математического программирования:
![Решение задач по математическому программированию](https://lfirmal.com/wp-content/uploads/2020/03/image-45530.png)
Решение:
а) Область допустимых решений, которую обозначим буквой , построим следующим образом. Построим прямые с уравнениями:
![Решение задач по математическому программированию](https://lfirmal.com/wp-content/uploads/2020/03/image-45532.png)
![Решение задач по математическому программированию](https://lfirmal.com/wp-content/uploads/2020/03/image-45533.png)
Прямые пронумерованы. Помер прямой имеется также на рисунке 2.4.
б) Каждое неравенство, фигурирующее в системе ограничений, определяет полуплоскость, причем эта полуплоскость содержит точку, координаты которой удовлетворяют соответствующему строгому неравенству.
Первые два и четвертое неравенства системы ограничений удовлетворяются координатами точки .
Поэтому три полуплоскости содержат начало координат системы .
На соответствующую полуплоскость указывают стрелки, идущие от каждой прямой. Жирной линией выделим границу ОДР выпуклый шестиугольник . Последние неравенства
, означающие неотрицательность переменных задачи, определяют первую четверть плоскости
.
в) Строим теперь нормальный вектор целевой функции . Его направление указывает направление возрастания целевой функции
.
Прямая с уравнением представляет собой «нулевую» линию уровня функции
. Эта прямая проходит через начало координат и перпендикулярна нормальному вектору
Передвигаем эту прямую параллельно себе, или перпендикулярно
, и фиксируем два ее крайних положения.
Эти крайние прямые, которые обозначим буквами и
, должны иметь с границей
либо общую вершину, либо общий отрезок, причем направление от
к
совпадает с направлением
. В нашем случае
проходит через точку
, a
— через точку
. Эти прямые называются соответственно нижней и верхней опорными прямыми для
.
г) Определим координаты точек и
. На чертеже видно, что точка
лежит на прямых 3) и 7), а
— на 2) и 4). Именно поэтому пронумерованы уравнения прямых и их изображения. Теперь легко составить системы уравнений для определения координат этих точек. Запишем это так:
![Решение задач по математическому программированию](https://lfirmal.com/wp-content/uploads/2020/03/image-45548.png)
Вычислим значения целевой функции в точках и
:
![Решение задач по математическому программированию](https://lfirmal.com/wp-content/uploads/2020/03/image-45549.png)
Возможно эта страница вам будет полезна:
Задачи математического программирования |
Симплекс-метод. Краткие теоретические сведении
Симплекс-метод. Максимум или минимум целевой функции может быть достигнут в одной из угловых точек области допустимых планов.
Сделанный вывод на первый взгляд позволяет предположить простой метод решения задач линейного программирования: надо просто «перебрать» все угловые точки области допустимых планов, в каждой из них вычислить значение целевой функции и выбрать ту угловую точку, где целевая функция оптимальна.
Однако количество угловых точек области допустимых планов растет очень резко с ростом числа переменных и особенно числа ограничений. Число перебираемых вершин можно сократить, если производить перебор не беспорядочно, а с учетом изменений целевой функции, т.е. добиваясь того, чтобы каждое следующее решение было «лучше» (или, по крайней мере, «не хуже»), чем предыдущее (было ближе к оптимальному решению).
Эта идея легла в основу универсального метода решения задач линейного программирования — симплекс-метода.
Симплекс-метод — один из первых специализированных методов оптимизации, нацеленный на решение задач линейного программирования. Он был предложен американцем Г. Данцигом в 1951 г. Симплекс-метод состоит в продвижении по выпуклому многограннику ограничений от вершины к вершине, при котором на каждом шаге значение целевой функции улучшается до тех пор, пока не будет достигнут оптимум.
Задача №3.1.
Найти какой-либо опорный план задачи (математически).
![Решение задач по математическому программированию](https://lfirmal.com/wp-content/uploads/2020/03/image-45550.png)
Решить задачу в Excel, используя «Поиск решения».
Решение:
Задача записана в канонической форме, но 2 свободных члена отрицательны, поэтому, прежде чем записать задачу в форме таблицы, умножим первое и второе уравнение на (-1).
![Математическое программирование задачи с решением](https://lfirmal.com/wp-content/uploads/2020/03/image-45551.png)
Для первого шага жорданова исключения возьмём разрешающим, например, четвёртый столбец — в нём есть положительные элементы. Разрешающая строка определится по минимальному из отношений: 4/1 и 7/1.
В данном случае
![Решение задач по математическому программированию](https://lfirmal.com/wp-content/uploads/2020/03/image-45552.png)
что соответствует первой строке, которая и будет разрешающей.
![Решение задач по математическому программированию](https://lfirmal.com/wp-content/uploads/2020/03/image-45553.png)
Сделаем ещё 2 шага жордановых исключений, получим:
![Решение задач по математическому программированию](https://lfirmal.com/wp-content/uploads/2020/03/image-45554.png)
![Решение задач по математическому программированию](https://lfirmal.com/wp-content/uploads/2020/03/image-45555.png)
Базис выделен. Ему соответствует начальный опорный план
![Решение задач по математическому программированию](https://lfirmal.com/wp-content/uploads/2020/03/image-45556.png)
Был найден опорный план в базисе . Если исходную таблицу преобразовать с другими разрешающими элементами, то получится другой базис — следовательно, и другой опорный план.
Решение задачи в процедуре EXCEL «Поиск решения».
1) Ввод данных в таблицу EXCEL (рис. 3.1).
![Решение задач по математическому программированию](https://lfirmal.com/wp-content/uploads/2020/03/image-45558.png)
Для переменных задачи отведены ячейки B3:F3. Эти ячейки называются рабочими или изменяемыми ячейками.
В изменяемые ячейки ничего не заносится и в результате решения задачи в этих ячейках будет оптимальные значения переменных.
В ячейку G4 вводится формула для вычисления целевой функции задачи (рис. 3.2):
![Решение задач по математическому программированию](https://lfirmal.com/wp-content/uploads/2020/03/image-45560.png)
В ячейку G7 вводится формула для вычисления ограничения 1: , в ячейку G8 вводится формула для вычисления ограничения 2:
а в ячейку G9 — вычисления ограничения 3:
. Обе формулы вводятся с помощью функции СУММПРОИЗВ0:
![Решение задач по математическому программированию](https://lfirmal.com/wp-content/uploads/2020/03/image-45564.png)
Окончательно после ввода формул и данных экран имеет вид (рис. 3.4):
2) Работа в окне «Поиск решения»»
В меню «Данные» выбираем процедуру «Поиск решения» В появившемся окне (рис. 3.5) нужно установить адрес целевой ячейки G4, значение целевой ячейки: максимальное, адреса изменяемых ячеек B3:F3.
![Решение задач по математическому программированию](https://lfirmal.com/wp-content/uploads/2020/03/image-45565.png)
Чтобы ввести ограничения задачи, нажать кнопку «Добавить». В появившемся диалоговом (рис. 3.6) окне слева ввести адрес G7 (ограничение 1), затем выбрать знак <= и в правой — адрес ячейки Н7.
![Решение задач по математическому программированию](https://lfirmal.com/wp-content/uploads/2020/03/image-45566.png)
После ввода нажать кнопку «Добавить» и аналогично ввести второе и третье ограничение. Снова нажать кнопку <<Добавить» и ввести ограничение: В3:3 >-0 (соответствующее ограничению ).
После ввода последнего ограничения нажать ОК. В опции «Выбрать метод решения» выбрать «Поиск решения линейных задач симплекс-методом». Окно «Поиска решений» будет иметь вид (рис. 3.7):
![Решение задач по математическому программированию](https://lfirmal.com/wp-content/uploads/2020/03/image-45568.png)
Для решения задачи в окне «Поиск решения» нажать кнопку «Найти решение». Если решение найдено появляется окно (рис. 3.8):
![Решение задач по математическому программированию](https://lfirmal.com/wp-content/uploads/2020/03/image-45569.png)
Оптимальное решение задачи линейного программирования:
![Решение задач по математическому программированию](https://lfirmal.com/wp-content/uploads/2020/03/image-45570.png)
Был найден оптимальный план в базисе
![Решение задач по математическому программированию](https://lfirmal.com/wp-content/uploads/2020/03/image-45571.png)
Различные технико-экономические и экономические задачи производственного менеджмента, от оптимальной загрузки станка и раскройки стального листа или полотна ткани
до анализа межотраслевого баланса и оценки темпов роста экономики страны в целом, приводят к необходимости решения тех или иных задач линейного программирования.
Возможно эта страница вам будет полезна:
Задача линейного программирования |
Задача №3.2.
Задача распределения ресурсов.
Если финансы, оборудование, сырьё и даже людей полагать ресурсами, то значительное число задач в экономике можно рассматривать как задачи распределения ресурсов. Достаточно часто математической моделью таких задач является задача линейного программирования.
Рассмотрим следующий пример.
Требуется определить, в каком количестве надо выпускать продукцию четырёх типов Прод1, Прод2, ПродЗ, Прод4, для изготовления которой требуются ресурсы трёх видов: трудовые, сырьё, финансы. Количество ресурсов каждого вида, необходимое для выпуска единицы продукции данного типа, называется нормой расхода. Нормы расхода, а также прибыль, получаемая от реализации единицы каждого типа продукции, приведены в таблице 2. Там же приведено наличие располагаемого ресурса.
![Решение задач по математическому программированию](https://lfirmal.com/wp-content/uploads/2020/03/image-45572.png)
Составить математическую модель, решить задачу симплекс-методом, применяя процедуру Excel «Поиск решения».
Решение:
Введём следующие обозначения:
— количество выпускаемой продукции
— го типа,
;
j — количество располагаемого ресурса
— го вида,
;
— норма расхода
— го ресурса для выпуска единицы продукции
— го типа;
— прибыль, получаемая от реализации единицы продукции
— го типа.
Как видно из таблицы 2, для выпуска единицы Прод1 требуется 6 единиц сырья, значит, для выпуска всей продукции Прод1 требуется 6 единиц сырья, где
— количество выпускаемой продукции Прод1. С учётом того, что для других видов продукции зависимости аналогичны, ограничение по сырью будет иметь вид:
![Решение задач по математическому программированию](https://lfirmal.com/wp-content/uploads/2020/03/image-45582.png)
В этом ограничении левая часть равна величине необходимого ресурса, а правая показывает количество имеющегося ресурса.
Аналогично можно составить ограничения для остальных ресурсов и написать зависимость для целевой функции. Тогда математическая модель задачи будет иметь вид:
![Решение задач по математическому программированию](https://lfirmal.com/wp-content/uploads/2020/03/image-45583.png)
Решение задачи в пакете EXCEL с поиощью «Поиск решения». 1) Ввод данных в таблицу EXCEL (рис. 3.9).
![Решение задач по математическому программированию](https://lfirmal.com/wp-content/uploads/2020/03/image-45584.png)
2) Работа в окне «Поиск решения»»
![Решение задач по математическому программированию](https://lfirmal.com/wp-content/uploads/2020/03/image-45585.png)
На рис. 3.10 видно, что в оптимальном решении ПроЫ =ВЗ = 10 Прод2 = СЗ = 0 ПродЗ = D3 = 6 Прод4 = ЕЗ = 0.
При этом максимальная прибыль будет составлять F4 = 1320, а количество использованных ресурсов равно
трудовых — F7 = 16 сырья = F8 = 84 финансов = F9 = 100 Анализ оптимального решения.
Анализ оптимального решения начинается после успешного решения задачи, когда на экране появляется диалоговое окно Результат поиска решения. Решение найдено (рис. 3.10). С помощью этого диалогового окна можно вызвать отчёты трёх типов: •Результаты
•Устойчивость • Пределы.
Вызов отчётов анализа.
Начнём с отчёта по результатам. Выделяем вызываемый отчёт и жмём на ОК (рис. 3.1 1)
![Решение задач по математическому программированию](https://lfirmal.com/wp-content/uploads/2020/03/image-45586.png)
На экране: вызванный отчёт на новом листе, на ярлыке которого указано название отчёта (рис. 3.12).
Отчёт состоит из трёх таблиц.
• Таблица 1 приводит сведения о целевой функции.
•Таблица 2 приводит значения искомых переменных, полученные в результате решения задачи.
•Таблица 3 показывает результаты оптимального решения для ограничений и граничных условий.
Для Ограничений в графе Формула приведены зависимости, которые были введены в диалоговое окно Поиск решения; в графе Значение ячейки приведены величины использованного ресурса; в графе Допуск показано количество неиспользованного ресурса. Если ресурс используется полностью, то в графе Состояние указывается Привязка; при неполном использовании ресурса в этой графе указывается Без привязки.
![Математическое программирование задачи с решением](https://lfirmal.com/wp-content/uploads/2020/03/image-45587.png)
![Решение задач по математическому программированию](https://lfirmal.com/wp-content/uploads/2020/03/image-45588.png)
Для Граничных условий приводятся аналогичные величины с той лишь разницей, что вместо величины неиспользованного ресурса показана разность между значением переменой в найденном оптимальном решении и заданным для неё граничным условием.
![Решение задач по математическому программированию](https://lfirmal.com/wp-content/uploads/2020/03/image-45589.png)
Отчёт по устойчивости (рис. 3.13) состоит из двух таблиц.
В таблице 1 приводятся следующие значения для переменных:
•результат решения задачи;
• приведенная стоимость, т.е. дополнительные двойственные переменные, которые показывают, насколько изменяется целевая функция при принудительном включении единицы этой продукции в оптимальное решение;
• коэффициенты целевой функции;
• предельные значения приращения коэффициентов целевой функции, при которых сохраняется набор переменных, входящих в оптимальное решение.
В таблице 2 приводятся аналогичные значения для ограничений:
• величина использованных ресурсов;
•теневая цена, т.е. двойственные оценки , которые показывают, как изменится целевая функция при изменении ресурсов на единицу;
•значения приращения ресурсов при которых сохраняется оптимальный объём переменных, входящих в оптимальное решение.
Отчёт по пределам приведён на рис. 3.14.
![Решение задач по математическому программированию](https://lfirmal.com/wp-content/uploads/2020/03/image-45593.png)
В нём показано, в каких пределах может изменяться выпуск продукции, вошедшей в оптимальное решение, при сохранении структуры оптимального решения:
• приводятся значения в оптимальном решении;
• приводятся нижние пределы изменения значений .
Кроме этого, в отчёте указаны значения целевой функции при выпуске данного типа продукции на нижнем пределе. Так, при значении 720 видно, что
![Решение задач по математическому программированию](https://lfirmal.com/wp-content/uploads/2020/03/image-45595.png)
Далее приводятся верхние пределы изменения — и значения целевой функции при выпуске продукции, вошедшей в оптимальное решение на верхних пределах.
Поэтому везде
![Решение задач по математическому программированию](https://lfirmal.com/wp-content/uploads/2020/03/image-45596.png)
Решение задачи математического программирования в microsoft excel
Постановка задачи:
Предприятие выпускает продукцию двух типов и
. Запас сырья и нормы расхода сырья на условную единицу продукции каждого типа даны в таблице.
![Решение задач по математическому программированию](https://lfirmal.com/wp-content/uploads/2020/03/image-45601.png)
Прибыль от реализации продукции типа составляет
денежных единиц, а прибыль от реализации продукции типа
составляет
денежных единиц. Как следует спланировать выпуск продукции, чтобы прибыль была наибольшей?
Решение данной задачи графическим методом в табличном редакторе Microsoft Excel
Математическая модель и исходные данные задачи — на рисунке 2.3.
Для построения области допустимых решений, и линии уровня необходимо:
1) Выделить данные в области (например, C17:D29), и на вкладке «Вставка» выбрать: «Точечная». Затем после построения первой линии из области допустимых решений, щёлкнуть правой клавишей мыши на области диаграммы и выбрать «Выбрать данные».
2) Щёлкнуть мышью по «Ряд 1» и выбрать кнопку «Изменить». В поле имя ряда записать уравнение построенной прямой (см. рис. 4.1)
![Решение задач по математическому программированию](https://lfirmal.com/wp-content/uploads/2020/03/image-45603.png)
3) Нажать кнопку «Добавить» и выбрать исходные данные для построения второго графика (см. рис. 4.2)
![Решение задач по математическому программированию](https://lfirmal.com/wp-content/uploads/2020/03/image-45604.png)
4) Повторить предыдущий пункт для остальных уравнений, входящих в область допустимых решений, а также для градиента и линии уровня.
5) Итоги решения задачи приведены на рисунке 4.3.
Область допустимых решений представляет собой многоугольник с вершинами в точках: (0;0), (0;6), (2;5), (4;3), (5;0).
При перемещении линии уровня в направлении вектора получаем оптимальное решение в точке с координатами (2;5), причём
![Решение задач по математическому программированию](https://lfirmal.com/wp-content/uploads/2020/03/image-45605.png)
Для получения максимальной прибыли равной 19 д. е. предприятие должно выпускать 2 ед. продукции и 5 ед. продукции
![Решение задач по математическому программированию](https://lfirmal.com/wp-content/uploads/2020/03/image-45606.png)
Решение в Microsoft Excel симплекс-методом
Подготовим начальную симплекс таблицу по образцу:
![Решение задач по математическому программированию](https://lfirmal.com/wp-content/uploads/2020/03/image-45607.png)
В столбце этой таблицы записывают коэффициенты при неизвестных целевой функции, имеющие те же индексы, что и векторы данного базиса.
В столбце В записывают положительные компоненты начального опорного плана, в нём же в результате вычислений получают положительные компоненты оптимального плана.
Первые три строки начальной симплекс-таблицы определяются исходными данными задачи, а показатели четвёртой строки — вычисляют. В этой строке в столбце В записывают значение целевой функции, которое она принимает при данном опорном плане, а в столбце — значение
![Решение задач по математическому программированию](https://lfirmal.com/wp-content/uploads/2020/03/image-45610.png)
Значение находится как скалярное произведение вектора
![Решение задач по математическому программированию](https://lfirmal.com/wp-content/uploads/2020/03/image-45612.png)
на вектор
![Решение задач по математическому программированию](https://lfirmal.com/wp-content/uploads/2020/03/image-45613.png)
![Решение задач по математическому программированию](https://lfirmal.com/wp-content/uploads/2020/03/image-45614.png)
Значение равно скалярному произведению вектора
на вектор
Вычислим его и запишем результат в ячейку
. Для вычисления скалярного произведения двух векторов используется функция СУММПРОИЗВ (массив1, [массив2], [массивЗ],…) (рис. 4.5).
![Решение задач по математическому программированию](https://lfirmal.com/wp-content/uploads/2020/03/image-45619.png)
Для вычисления оценок используется формула
![Решение задач по математическому программированию](https://lfirmal.com/wp-content/uploads/2020/03/image-45621.png)
Выделим ячейку Е7 и введём формулу:
![Решение задач по математическому программированию](https://lfirmal.com/wp-content/uploads/2020/03/image-45622.png)
Аналогично вычислим значения других оценок.
![Решение задач по математическому программированию](https://lfirmal.com/wp-content/uploads/2020/03/image-45623.png)
Далее исходный план нужно проверить на оптимальность. Для этого просматриваем элементы последней строки таблицы. В результате может иметь место один из следующих трёх случаев:
1) — исходный план является оптимальным;
2) для некоторого
и все соответствующие этому индексу величины
— целевая функция не ограничена сверху на множестве планов;
3) для некоторых индексов
и для каждого такого
по крайней мере одно из чисел
является положительным — можно перейти от исходного плана к новому опорному плану, при котором значение целевой функции увеличится.
Определим разрешающий столбец — столбец с наибольшей по модулю отрицательной оценкой и найдем отношение элементов столбца В к положительным элементам выбранного столбца для определения разрешающей строки. Для этого выделим ячейку К4 и введём формулу:
![Решение задач по математическому программированию](https://lfirmal.com/wp-content/uploads/2020/03/image-45630.png)
Скопируем формулу на диапазон К4:К6.
![Решение задач по математическому программированию](https://lfirmal.com/wp-content/uploads/2020/03/image-45631.png)
Таким образом, разрешающий столбец — столбец и разрешающая строка —
.
Создадим вторую симплекс-таблицу (скопируем предыдущую и удалим все ненужное). Произведём замену в базисе вектора (разрешающий столбец) на вектор
(разрешающая строка).
![Решение задач по математическому программированию](https://lfirmal.com/wp-content/uploads/2020/03/image-45634.png)
Выделим диапазон D 12:115 и сменим формат числовых данных на дробный.
Вычислим новые элементы разрешающей строки: разделим элементы разрешающей строки на разрешающий элемент. В ячейку D13 введём формулу
![Решение задач по математическому программированию](https://lfirmal.com/wp-content/uploads/2020/03/image-45635.png)
Скопируйте формулу на диапазон Е13: 113:
![Решение задач по математическому программированию](https://lfirmal.com/wp-content/uploads/2020/03/image-45636.png)
В ячейку D12 введём формулу:
![Решение задач по математическому программированию](https://lfirmal.com/wp-content/uploads/2020/03/image-45637.png)
Скопируем формулу на диапазон Е12:I12. В ячейку D14 введём формулу:
![Математическое программирование задачи с решением](https://lfirmal.com/wp-content/uploads/2020/03/image-45638.png)
и скопируем формулу на диапазон Е15:115. В ячейку D15 введём формулу:
![Решение задач по математическому программированию](https://lfirmal.com/wp-content/uploads/2020/03/image-45639.png)
Скопируем формулу на диапазон Е15:I15. Получим:
![Решение задач по математическому программированию](https://lfirmal.com/wp-content/uploads/2020/03/image-45640.png)
Так как строка оценок содержит отрицательное число, и соответствующий столбец содержит положительные числа, то план можно улучшить. Выбираем разрешающую строку и разрешающий столбец:
![Решение задач по математическому программированию](https://lfirmal.com/wp-content/uploads/2020/03/image-45641.png)
Строим новую симплекс-таблицу и заменяем вектор (разрешающая строка) на вектор
(разрешающий столбец). Заполняем таблицу аналогично предыдущей итерации:
![Решение задач по математическому программированию](https://lfirmal.com/wp-content/uploads/2020/03/image-45644.png)
Так как строка оценок не содержит отрицательных значений, то полученный план оптимален и имеет вид:
![Решение задач по математическому программированию](https://lfirmal.com/wp-content/uploads/2020/03/image-45645.png)
Исключая из решения балансовые неизвестные, получим ответ:
![Решение задач по математическому программированию](https://lfirmal.com/wp-content/uploads/2020/03/image-45646.png)
Возможно эта страница вам будет полезна:
Решение задач по линейному программированию |
Решение в Microsoft Excel с помощью встроенной функции Поиск решения
В табличном процессоре Microsoft Excel существует встроенная функция Поиск решения, с помощью которой можно решить задачу линейного программирования. Если данный модуль установлен, его можно запустить, выбрав вкладку Данные /Поиск решения. На экране появится диалоговое окно Поиск решения (рис. 4.12).
Если такого пункта во вкладке Данные не оказалось, следует загрузить соответствующую программу-надстройку. Для этого нужно выбрать вкладку Файл-Параметры-Надстройки—Перейти и в диалоговом окне Надстройки установить флажок в строке Поиск решения.
![Решение задач по математическому программированию](https://lfirmal.com/wp-content/uploads/2020/03/image-45647.png)
Разберем решение ЗЛП с помощью функции Поиск решения на примере нашей задачи.
- Создадим таблицу для ввода исходных данных: переменных, целевой функции,ограничений.
- Введем начальные нулевые значения для
и
.
- Зададим целевую функцию в ячейке D6 и ограничения в ячейках F4, F5 и F6 (рис. 4.13).
![Решение задач по математическому программированию](https://lfirmal.com/wp-content/uploads/2020/03/image-45650.png)
- Выберем команду Данные/Поиск решения, в открывшемся окне Поиск решения установим целевую ячейку D6, зададим условие отыскания максимального значения (рис. 4.14).
- В поле Изменяя ячейки установим ссылку на ячейки С5 и С6, которые будут изменены (молено ввести адреса или имена ячеек с клавиатуры или указать диапазон ячеек на рабочем листе с помощью мыши).
- Определим ограничения, для этого щелчком по кнопке Добавить откроем диалоговое окно Добавление ограничения. Введем ограничения для ячеек F4, F5, F6. Ограничения можно задать как для изменяемых ячеек, так и для целевой ячейки, а также для других ячеек, прямо или косвенно присутствующих в модели (рис. 4.14)
![Решение задач по математическому программированию](https://lfirmal.com/wp-content/uploads/2020/03/image-45651.png)
- После того как все параметры и ограничения заданы, запускаем поиск решения, щелкнув на кнопке Найти решение. Когда поиск будет закончен, в таблицу будут внесены новые значения и на экране появится диалоговое окно Результаты поиска решения, сообщающие о завершении операции (рис. 4.15).
![Решение задач по математическому программированию](https://lfirmal.com/wp-content/uploads/2020/03/image-45652.png)
Решение найдено. Все ограничения и условия оптимальности выполнены. Сохраним найденное решение. В этом случае таблица будет обновлена. В случае необходимости всегда можно будет восстановить исходные данные с помощью отчета. Для выбора типа отчета достаточно выделить название нужного отчета в списке Тин отчета (или несколько названий, удерживая нажатой клавишу Ctrl). Они будут вставлены на отдельных листах в рабочую книгу перед листом с исходными данными.
Предлагаемые отчеты содержат следующую информацию:
- •отчет Результаты содержит сведения о начальных и текущих значениях целевой ячейки и изменяемых ячеек, а также о соответствии значений заданным ограничениям;
- • отчет Устойчивость отражает найденный результат, а также нижние и верхние предельные значения для изменяемых ячеек;
- •отчет Пределы показывает зависимость решений от изменения формулы или ограничений.
Если планируется использовать созданную модель в дальнейшем, найденное решение можно сохранить как сценарий. Для этого в диалоговом окне Результаты поиска решения необходимо щелкнуть на кнопке Сохранить сценарий.
Возможно эта страница вам будет полезна:
Методы решения задач линейного программирования |
Двойственные задачи линейного программирования
Каждой задаче линейного программирования можно поставить в соответствие другую задачу тоже линейного программирования, которая получается из исходной задачи путем определенных преобразований и называется двойственной по отношению к данной исходной задаче.
Т.е. ЗЛП на максимум можно поставить в соответствие ЗЛП на минимум. Эти задачи называются симметричными или взаимно-двойственными.
Рассмотрим понятие двойственных задач на примере следующей задачи.
Задача №5.1.
Предприятие, специализирующееся на производстве трикотажного полотна двух видов, использует для своего производства четыре вида сырья (шерстяную, хлопковую, вискозную, и акриловую нити), запасы которого на планируемый период составляют соответственно 80, 80, 260 и 410 бобин. В приведенной ниже таблице даны технологические коэффициенты, т.е. расход каждого вида сырья на производство одного метра каждого вида трикотажа.
![Решение задач по математическому программированию](https://lfirmal.com/wp-content/uploads/2020/03/image-45653.png)
Прибыль от реализации 1 м трикотажного полотна первого вида составляет 2 д. е., а трикотажного полотна второго вида 3 д. е. Необходимо определить оптимальный план выпуска трикотажного полотна первого и второго вида, чтобы обеспечить максимальную прибыль от их реализации.
Экономико-математическая модель задачи: найти максимум целевой функции (функции прибыли):
![Решение задач по математическому программированию](https://lfirmal.com/wp-content/uploads/2020/03/image-45654.png)
при выполнении системы ограничений:
![Решение задач по математическому программированию](https://lfirmal.com/wp-content/uploads/2020/03/image-45655.png)
Предположим, что некоторая организация решила закупить ресурсы предприятия и необходимо установить оптимальные цены на эти ресурсы .
Очевидно, что покупающая организация заинтересована в том, чтобы затраты на все ресурсы (целевая функция ) в количествах 80, 80, 260 и 410 д. е. по ценам
были минимальны, т.е.
![Решение задач по математическому программированию](https://lfirmal.com/wp-content/uploads/2020/03/image-45658.png)
С другой стороны, предприятие, продающее ресурсы, заинтересовано в том. чтобы полученная выручка была не менее той суммы, которую предприятие может получить при переработке ресурсов в готовую продукцию.
На изготовление 1 м трикотажного полотна I вида расходуется 0 д. е. первого ресурса (шерсти), 1 д. е. второго ресурса (хлопка), 1 д. е. третьего ресурса (вискозы) и 4 д. е. четвертого ресурса (акрила). Поэтому для удовлетворения требований продавца затраты на ресурсы, потребляемые при изготовлении 1 м трикотажного полотна I вида по ценам , должны быть не менее цены 1 м трикотажного полотна 1 вида (2 д. е.), т.е.
![Решение задач по математическому программированию](https://lfirmal.com/wp-content/uploads/2020/03/image-45659.png)
Аналогично составим ограничение в виде неравенства по второму виду продукции (трикотажному полотну II вида):
![Решение задач по математическому программированию](https://lfirmal.com/wp-content/uploads/2020/03/image-45661.png)
Таким образом, получили двойственную задачу относительно исходной (таблица 5.2).
![Решение задач по математическому программированию](https://lfirmal.com/wp-content/uploads/2020/03/image-45662.png)
При этом цены ресурсов являются условными, в отличие от «внешних цен» на продукцию, известных, как правило, до начала производства.
Цены ресурсов так же называются «внутренними» (или оценками ресурсов), т.к. они задаются не извне, а определяются непосредственно в результате решения задачи.
Исходную задачу можно рассматривать как двойственную по отношению к своей двойственной задаче, т.е. обе задачи являются взаимно двойственными.
Взаимно двойственные задачи обладают следующими свойствами:
- В одной задаче определяется максимум целевой функции, в другой — минимум.
- Коэффициенты при переменных в целевой функции одной задачи являются свободными членами системы ограничений в другой.
- Каждая из задач задана в стандартной форме, причем в задаче максимизации все неравенства вида
, а в задаче минимизации — все неравенства вида
.
- Матрицы коэффициентов при переменных в системах ограничений обеих задач являются транспонированными друг к другу.
- Число неравенств в системе ограничений одной задачи совпадает с числом переменных в другой задаче.
- Условия неотрицательности переменных имеются в обеих задачах.
Алгоритм составления двойственной задачи
- Привести все неравенства системы ограничений исходной задачи к одному виду: если в исходной задаче ищут максимум целевой функции, то все неравенства системы ограничений привести к виду
, а если минимум — к виду
. Для этого неравенства, в которых данное требование не выполняется, умножить на (-1).
- Составить расширенную матрицу системы ограничений исходной задачи — матрицу
, в которую включить строку коэффициентов при переменных в целевой функции.
- Найти матрицу
, транспонированную к матрице
.
- Сформулировать двойственную задачу на основании полученной матрицы
, и условия неотрицательности переменных.
Двойственная задача может быть решена симплекс-методом, а так же с помощью функции Поиск решения в табличном редакторе Microsoft Excel.
Если же исходная задача уже решена симплекс-методом, то решение двойственной задачи может быть найдено по формуле:
![Решение задач по математическому программированию](https://lfirmal.com/wp-content/uploads/2020/03/image-45668.png)
где — матрица-строка коэффициентов при базисных переменных целевой функции входящих в оптимальный базис исходной задачи (в первоначальном виде);
— обратная матрица для матрицы
, являющейся матрицей коэффициентов при переменных, входящих в оптимальный базис (взятых из первоначальной системы ограничений исходной задачи).
Вернёмся к задаче 5.1. Решим прямую задачу симплекс-методом.
Приведем ЗЛП к каноническому виду.
Для этого приведем систему неравенств к системе уравнений путем введения дополнительных переменных .
![Решение задач по математическому программированию](https://lfirmal.com/wp-content/uploads/2020/03/image-45672.png)
Определение первоначального допустимого базисного решения.
Т.к. каждая дополнительная переменная входит в уравнение с тем же знаком, что и свободный член, стоящий в правой части уравнения, то в качестве базисных переменных можно взять дополнительные и при этом получим допустимое базисное решение.
Замечание: Базисные переменные — это переменные, которые входят только в одно уравнение системы ограничений и при этом имеют коэффициент, равный единице.
Полагая, что свободные переменные равны 0, получим первое базисное решение:
![Математическое программирование задачи с решением](https://lfirmal.com/wp-content/uploads/2020/03/image-45675.png)
Данное базисное решение является допустимым, т.к. оно неотрицательно.
Составление симплекс-таблицы.
Получено первоначальное допустимое базисное решение, целевая функция содержит только свободные переменные, переходим к составлению первой симплекс-таблицы (таблица 5.3):
![Решение задач по математическому программированию](https://lfirmal.com/wp-content/uploads/2020/03/image-45676.png)
Переход к основному алгоритму симплекс-метода.
I шаг.
- Проверка критерия оптимальности.
Полученное на I шаге базисное решение (опорный план) не является оптимальным, т.к. в индексной строке есть отрицательные коэффициенты.
- Определение новой базисной переменной.
В качестве разрешающего выберем столбец, соответствующий переменной , т.к. ей соответствует наибольший по модулю отрицательный коэффициент (-3).
- Определение новой свободной переменной.
Вычислим оценочные отношения для строк соответствующих базисным переменным как частное от деления
(т.к. эти строки содержат положительные коэффициенты в разрешающем столбце). Выберем из полученных значений наименьшее:
![Решение задач по математическому программированию](https://lfirmal.com/wp-content/uploads/2020/03/image-45681.png)
Следовательно, первая строка (соответствующая базисной переменной ) является разрешающей. Разрешающий элемент — 1, который находится на пересечении разрешающего столбца и разрешающей строки.
- Пересчет симплекс-таблицы.
В столбце базисных переменных записываем новый базис: вместо базисной переменной — переменную
.
В столбцах, соответствующих базисным переменным проставляем нули и единицы: 1 — против «своей» базисной переменной; 0 — против «чужой» базисной переменной; 0-в последней индексной строке для всех базисных переменных.
Все остальные элементы новой симплекс-таблицы (включая элементы индексной строки) находим по правилу «прямоугольника».
После преобразований получаем новую таблицу (таблица 5.4).
![Решение задач по математическому программированию](https://lfirmal.com/wp-content/uploads/2020/03/image-45683.png)
Базисное решение:
![Решение задач по математическому программированию](https://lfirmal.com/wp-content/uploads/2020/03/image-45684.png)
II шаг.
- Проверка критерия оптимальности.
Полученное на II шаге базисное решение (опорный план) не является оптимальным, т.к. в индексной строке есть отрицательный коэффициент (-2).
- Определение новой базисной переменной.
В качестве разрешающего выберем столбец, соответствующий переменной , т.к. ей соответствует отрицательный коэффициент (-2).
- Определение новой свободной переменной.
Вычислим оценочные отношения для строк соответствующих базисным переменным как частное от деления
(т.к. эти строки содержат положительные коэффициенты в разрешающем столбце). Выберем из полученных значений наименьшее:
![Решение задач по математическому программированию](https://lfirmal.com/wp-content/uploads/2020/03/image-45687.png)
Следовательно, третья строка (соответствующая базисной переменной ) является разрешающей. Разрешающий элемент 1, который находится на пересечении разрешающего столбца и разрешающей строки.
- Пересчет симплекс-таблицы.
В столбце базисных переменных записываем новый базис.
Разрешающий элемент — 1. В столбцах, соответствующих базисным переменным проставляем нули и единицы: 1 — против «своей» базисной переменной; 0 — против «чужой» базисной переменной; О-в последней индексной строке для всех базисных переменных. Все остальные элементы новой симплекс-таблицы (включая элементы индексной строки) находим по правилу «прямоугольника».
После преобразований получаем новую таблицу (таблица 5.5).
![Решение задач по математическому программированию](https://lfirmal.com/wp-content/uploads/2020/03/image-45689.png)
Базисное решение
![Решение задач по математическому программированию](https://lfirmal.com/wp-content/uploads/2020/03/image-45691.png)
III шаг.
- Проверка критерия оптимальности.
Полученное на 11 шаге базисное решение (опорный план) не является оптимальным, т.к. в индексной строке есть отрицательный коэффициент (-3).
- Определение новой базисной переменной.
В качестве разрешающего выберем столбец, соответствующий переменной , т.к. ей соответствует отрицательный коэффициент (-3).
- Определение новой свободной переменной.
Вычислим оценочные отношения для строк соответствующих базисным переменным как частное от деления:
(т.к. эти строки содержат положительные коэффициенты в разрешающем столбце). Выберем из полученных значений наименьшее:
![Решение задач по математическому программированию](https://lfirmal.com/wp-content/uploads/2020/03/image-45697.png)
Следовательно, четвертая строка (соответствующая базисной переменной ) является разрешающей. Разрешающий элемент 9, который находится на пересечении разрешающего столбца и разрешающей строки.
- Пересчет симплекс-таблицы.
В столбце базисных переменных записываем новый базис. Каждый элемент разрешающей строки (которая в новой симплекс таблице будет уже соответствовать переменной ) делим на разрешающий элемент (РЭ=9).
![Решение задач по математическому программированию](https://lfirmal.com/wp-content/uploads/2020/03/image-45698.png)
На месте разрешающего элемента получаем 1. В столбцах, соответствующих базисным переменным проставляем нули и единицы: 1 — против «своей» базисной переменной; 0 — против «чужой» базисной переменной; О-в последней индексной строке для всех базисных переменных.
Все остальные элементы новой симплекс-таблицы (включая элементы индексной строки) находим по правилу «прямоугольника» После преобразований получаем новую таблицу.
![Решение задач по математическому программированию](https://lfirmal.com/wp-content/uploads/2020/03/image-45700.png)
Базисное решение
![Решение задач по математическому программированию](https://lfirmal.com/wp-content/uploads/2020/03/image-45701.png)
Полученное базисное решение (опорный план) является оптимальным, т.к. в индексной строке нет отрицательных коэффициентов. Таким образом, оптимальным будет решение:
![Решение задач по математическому программированию](https://lfirmal.com/wp-content/uploads/2020/03/image-45702.png)
при котором
![Решение задач по математическому программированию](https://lfirmal.com/wp-content/uploads/2020/03/image-45704.png)
Т.е. для получения максимальной прибыли от реализации трикотажного полотна в размере 310 д. е. предприятие должно выпустить за планируемый период соответственно 50 и 70 метров трикотажного полотна первого и второго вида.
Рассмотрим последний шаг решения прямой задачи. Составим матрицу из коэффициентов при переменных, входящих в оптимальный базис (взятых из первоначальной системы ограничений исходной задачи)
![Решение задач по математическому программированию](https://lfirmal.com/wp-content/uploads/2020/03/image-45706.png)
Матрица коэффициентов
![Решение задач по математическому программированию](https://lfirmal.com/wp-content/uploads/2020/03/image-45707.png)
Найдем обратную матрицу в табличном редакторе Microsoft Excel с помощью встроенной функции МОБР().
![Решение задач по математическому программированию](https://lfirmal.com/wp-content/uploads/2020/03/image-45708.png)
Для этого необходимо:
1) Выделить область для вывода обратной матрицы;
2) Вызвать функцию =МОБР() (рис. 5.1);
3) После выделения диапазона исходных данных одновременно нажать комбинацию клавиш CTRL-SHIFT-ENTER.
В результате получим (рис. 5.2):
![Решение задач по математическому программированию](https://lfirmal.com/wp-content/uploads/2020/03/image-45710.png)
То есть:
![Решение задач по математическому программированию](https://lfirmal.com/wp-content/uploads/2020/03/image-45711.png)
Тогда:
![Решение задач по математическому программированию](https://lfirmal.com/wp-content/uploads/2020/03/image-45712.png)
Или, применяя встроенную функцию МУМНОЖ (рис. 5.3):
![Решение задач по математическому программированию](https://lfirmal.com/wp-content/uploads/2020/03/image-45714.png)
Т.е. оптимальный план двойственной задачи равен:
![Решение задач по математическому программированию](https://lfirmal.com/wp-content/uploads/2020/03/image-45715.png)
Возможно эта страница вам будет полезна:
Графическое решение задач линейного программирования |
Двойственный симплекс-метод. Анализ экономико-математической модели двойственной задачи
Рассмотрим симплексный алгоритм, который основан на соотношениях между прямой и двойственной задачами. Этот алгоритм эффективно решает определенный класс задач линейного программирования.
В двойственном симплекс-методе решение задачи линейного программирования начинается с недопустимого, но лучшего, чем оптимальное решения. Последовательные итерации этого метода приближают решение к области допустимости без нарушения оптимальности промежуточных решений. Когда будет достигнута область допустимых решений, процесс вычислений заканчивается, так как последнее решение будет оптимальным.
В двойственном симплекс-методе начальная симплекс-таблица обязательно должна иметь в базисном решении недопустимую (т.е. отрицательную) переменную. Для реализации двойственного симплекс-метода разработаны следующие два условия, выполнение которых гарантирует оптимальность последовательных промежуточных решений и приближение их к области допустимых решений.
Двойственное условие допустимости. В качестве исключаемой переменной выбирается базисная переменная, имеющая наибольшее по абсолютной величине отрицательное значение. Если таких переменных несколько, то выбор произволен. Если все базисные переменные неотрицательные, процесс вычислений заканчивается.
Двойственное условие оптимальности. Вводимая в базис переменная определяется как переменная, на которой достигается следующий минимум:
![Решение задач по математическому программированию](https://lfirmal.com/wp-content/uploads/2020/03/image-45718.png)
где — коэффициент из симплекс-таблицы, расположенный на пересечении ведущей строки (соответствующей исключаемой переменной
) и столбца, соответствующего переменной
. При наличии нескольких альтернативных переменных, выбор делается произвольно.
Задача №6.1.
Дана задача линейного программирования:
Минимизировать
![Решение задач по математическому программированию](https://lfirmal.com/wp-content/uploads/2020/03/image-45721.png)
При ограничениях
![Решение задач по математическому программированию](https://lfirmal.com/wp-content/uploads/2020/03/image-45722.png)
Начальная симплекс-таблица имеет вид:
![Решение задач по математическому программированию](https://lfirmal.com/wp-content/uploads/2020/03/image-45724.png)
Среди дополнительных переменных этой задачи и
являются избыточными, а
— остаточной. Умножим каждое равенство, соответствующее избыточным дополнительным переменным, на -1; в результате правые части этих равенств непосредственно указывают на базисные переменные, которые являются недопустимыми
. Этот подход всегда используется при реализации двойственного симплекс-метода.
Поскольку элементы в индексной строке отрицательны для всех начальное базисное решение является оптимальным (но не допустимым). Таким образом, приведенная таблица удовлетворяет требованиям начальной таблицы двойственного симплекс-метода, а именно оптимальности и недопустимости.
Двойственное условие допустимости указывает на переменную как на исключаемую из базиса. Теперь применим двойственное условие оптимальности для определения переменной, вводимой в базис. Для этого используем следующую таблицу.
![Решение задач по математическому программированию](https://lfirmal.com/wp-content/uploads/2020/03/image-45732.png)
Приведенные отношения показывают, что вводимой в базис переменной будет .
Следующая таблица получена с помощью известных операций над строками, применяемых в прямом симплекс-методе.
![Решение задач по математическому программированию](https://lfirmal.com/wp-content/uploads/2020/03/image-45737.png)
Последняя таблица показывает, что из базиса исключается переменная и вводится
. В результате получаем следующую симплекс-таблицу.
![Решение задач по математическому программированию](https://lfirmal.com/wp-content/uploads/2020/03/image-45744.png)
Решение, представленное в последней таблице, допустимо (и оптимально), поэтому вычисления заканчиваются. Это решение имеет вид
![Решение задач по математическому программированию](https://lfirmal.com/wp-content/uploads/2020/03/image-45745.png)
На рис. 6.1 показана последовательность шагов двойственного сим-плекс-метода при решении этой задачи.
Алгоритм начинается в крайней точке А (которой соответствует недопустимое, но «лучше, чем оптимальное» решение), затем он переходит к точке В (которой также соответствует недопустимое, но «лучше, чем оптимальное» решение) и заканчивается в точке С, уже принадлежащей области допустимых решений.
![Решение задач по математическому программированию](https://lfirmal.com/wp-content/uploads/2020/03/image-45746.png)
Возможно эта страница вам будет полезна:
Графический метод решения задач линейного программирования |
Задача №6.2.
На предприятии имеется возможность выпуска трех видов продукции . При её изготовлении используются ресурсы
. Размеры допустимых затрат ресурсов ограничены соответственно величинами
. Расход ресурса
-го вида на единицу продукции
-го вида составляет
единиц. Цена единицы продукции
-го вида равна
.
Требуется:
- Найти план продукции, обеспечивающий предприятию максимальный доход.
- Сформулировать в экономических терминах двойственную задачу, составить математическую модель двойственной задачи и решить её.
- Используя решение исходной и двойственных задач, а также соответствие между двойственными переменными, провести анализ плана, указать наиболее дефицитный и избыточный ресурс, если он имеется.
![Решение задач по математическому программированию](https://lfirmal.com/wp-content/uploads/2020/03/image-45754.png)
Решение:
Пусть — это количество единиц продукции соответственно
, планируемой к выпуску, a
— величина прибыли от реализации этой продукции.
Составим экономико-математическую модель задачи. Учитывая значение прибыли от единицы продукции, запишем суммарную величину прибыли целевую функцию — в следующем виде.
![Решение задач по математическому программированию](https://lfirmal.com/wp-content/uploads/2020/03/image-45760.png)
Переменные должны удовлетворять ограничениям, накладываемым на расход ресурсов, имеющихся в распоряжении предприятия:
![Решение задач по математическому программированию](https://lfirmal.com/wp-content/uploads/2020/03/image-45763.png)
По смыслу задачи переменные должны быть неотрицательными:
![Решение задач по математическому программированию](https://lfirmal.com/wp-content/uploads/2020/03/image-45769.png)
Решаем задачу в MS Excel. Составим следующую таблицу:
![Решение задач по математическому программированию](https://lfirmal.com/wp-content/uploads/2020/03/image-45770.png)
Формулы использовали следующие:
![Решение задач по математическому программированию](https://lfirmal.com/wp-content/uploads/2020/03/image-45771.png)
Выполняем последовательность команд: Данные — Поиск решения. Поля в появившемся окне заполняем следующим образом:
![Решение задач по математическому программированию](https://lfirmal.com/wp-content/uploads/2020/03/image-45772.png)
Нажимаем кнопку «Найти решение», получаем результат:
![Решение задач по математическому программированию](https://lfirmal.com/wp-content/uploads/2020/03/image-45773.png)
Т.о., по оптимальному плану следует изготовить 55 ед. продукции второго вида, продукцию первого и третьего вида — не выпускать. Останутся неиспользованными 35 ед. первого ресурса и 205 ед. третьего ресурса. Прибыль при этом будет максимальна и составит 1540 ден. ед.
Составим экономико-математическую модель двойственной задачи.
Пусть — цена единицы ресурса
— суммарная стоимость ресурсов. Требуется минимизировать затраты покупающего ресурсы предприятия, при этом нашему предприятию продажа должна быть менее выгодна, чем производство продукции.
Двойственная задача:
![Решение задач по математическому программированию](https://lfirmal.com/wp-content/uploads/2020/03/image-45776.png)
Решаем задачу в MS Excel. Первоначальная таблица:
![Решение задач по математическому программированию](https://lfirmal.com/wp-content/uploads/2020/03/image-45777.png)
Результаты:
![Решение задач по математическому программированию](https://lfirmal.com/wp-content/uploads/2020/03/image-45778.png)
Соответствие между переменными:
![Решение задач по математическому программированию](https://lfirmal.com/wp-content/uploads/2020/03/image-45779.png)
Запишем оптимальный план двойственной задачи:
![Решение задач по математическому программированию](https://lfirmal.com/wp-content/uploads/2020/03/image-45780.png)
Так как , то второй ресурс дефицитен, первый и третий ресурсы являются избыточными для них
.
При увеличении использования второго ресурса на единицу прибыль увеличиться па 7 денежных ед., первого и третьего — прибыль не изменится.
Возможно эта страница вам будет полезна:
Заказать работу по линейному программированию |
Транспортная задача (тз)
Одним из частных случаев задач линейного программирования является транспортная задача. Цель данной задачи состоит в определении оптимального плана перевозок, при котором минимальной была либо стоимость перевозок, либо минимальным было время доставки груза.
В общем виде транспортную задачу можно представить следующим образом: в пунктах производства
имеется однородный груз в количествах, соответственно,
. Этот груз необходимо доставить в
пунктов назначения
в количествах, соответственно
. Стоимость перевозки 1 ед. груза (тариф) из пункта
в пункт
равна
.
Требуется составить план перевозок так, чтобы:
- мощности (запасы) всех поставщиков были реализованы;
- заказы всех потребителей были удовлетворены;
- суммарные затраты на перевозку были бы минимальны.
Исходные данные транспортной задачи записываются в виде таблицы 8.1
![Решение задач по математическому программированию](https://lfirmal.com/wp-content/uploads/2020/03/image-45793.png)
Виды транспортных задач
В зависимости от соотношения между суммарными запасами груза у поставщиков и суммарными потребностями в нем потребителей транспортные задачи делятся на два вида: закрытые и открытые.
Определение 8.1. Если сумма запасов груза у поставщиков равна суммарной потребности в нем потребителей, т.е.
![Решение задач по математическому программированию](https://lfirmal.com/wp-content/uploads/2020/03/image-45794.png)
то транспортная задача называется закрытой. Определение 2. Если условие (8.1) не выполняется, т.е.
![Решение задач по математическому программированию](https://lfirmal.com/wp-content/uploads/2020/03/image-45795.png)
то транспортная задача называется открытой.
Теорема 8.1 (необходимое и достаточное условие разрешимости ТЗ). Для разрешимости транспортной задачи необходимо и достаточно, чтобы запасы груза в пунктах отправления были равны потребностям в грузе в пунктах назначения, т.е. чтобы выполнялось равенство (8.1).
Возможно эта страница вам будет полезна:
Помощь по линейному программированию |
Математическая модель закрытой транспортной задачи
Рассмотрим закрытую транспортную задачу.
- Неизвестными транспортной задачи являются
— объёмы перевозок or каждого
— го поставщика каждому
-му потребителю. Эти переменные так же можно записать в виде матрицы перевозок:
![Решение задач по математическому программированию](https://lfirmal.com/wp-content/uploads/2020/03/image-45799.png)
- Так как произведение
определяет затраты на перевозку груза от
-го поставщика
-му потребителю, то суммарные затраты на перевозку всех грузов равны
. Т.е. целевая функция будет иметь вид:
![Решение задач по математическому программированию](https://lfirmal.com/wp-content/uploads/2020/03/image-45802.png)
- Система ограничений транспортной задачи состоит из двух групп уравнений.
Первая группа состоит из уравнений и описывает тот факт, что запасы всех поставщиков
вывозятся полностью, т.е.:
![Решение задач по математическому программированию](https://lfirmal.com/wp-content/uploads/2020/03/image-45805.png)
Вторая группа состоит из уравнений и выражает требование полностью удовлетворить запросы всех
потребителей:
![Решение задач по математическому программированию](https://lfirmal.com/wp-content/uploads/2020/03/image-45807.png)
![Решение задач по математическому программированию](https://lfirmal.com/wp-content/uploads/2020/03/image-45808.png)
Кроме того, переменные должны быть неотрицательны:
![Решение задач по математическому программированию](https://lfirmal.com/wp-content/uploads/2020/03/image-45809.png)
- Оптимальным решением транспортной задачи является матрица размерности
, удовлетворяющая системе ограничений и обеспечивающая минимум целевой функции.
Особенности экономико-математической модели ТЗ
- Система ограничений представляет собой систему уравнений (т.е. ТЗ задана в канонической форме);
- Коэффициенты при переменных системы ограничений равны единице или нулю;
- Каждая переменная входит только в два уравнения системы ограничений.
Число переменных в ТЗ с
пунктами отправления и
пунктами назначения равно
, а число уравнений в системах (8.2) и (8.3) равно
. Так как мы предполагаем, что выполняется условие (8.1), то число линейно независимых уравнений равно
. Следовательно, опорный план транспортной задачи, может иметь не более
отличных от нуля неизвестных.
Если в опорном плане число отличных от нуля неизвестных равно , то план является невырожденным, а если меньше — то вырожденным.
Возможно эта страница вам будет полезна:
Контрольная работа по линейному программированию |
Открытая транспортная задача (транспортная задача с нарушенным балансом)
В открытой ТЗ сумма запасов не совпадает с суммой потребностей, поэтому для решения открытой ТЗ ее сводят к закрытой ТЗ.
- Если
, т.е. суммарный запас груза поставщиков больше суммарного спроса потребителей, то в задачу вводится фиктивный
-й потребитель с потребностью равной разности объемов запаса и потребления
и стоимостью перевозок
![Решение задач по математическому программированию](https://lfirmal.com/wp-content/uploads/2020/03/image-45817.png)
- Если
т.е. объем потребления превышает объем запасов, то вводится фиктивный
-й поставщик с запасом
и стоимостью перевозок
.
После добавления фиктивного потребителя или фиктивного поставщика ТЗ становится закрытой, а, следовательно, и разрешимой.
Транспортная задача как задача линейного программирования может быть решена симплекс-методом, однако наличие большого числа переменных и ограничений делает вычисления громоздкими. Поэтому для решения данного класса задач разработан специальный метод, имеющий те же этапы, что и симплексный метод, а именно:
- Нахождение исходного опорного решения;
- Проверка полученного решения на оптимальность;
- Переход от одного опорного решения к другому до достижения оптимального значения (минимума) целевой функции.
При решении ТЗ ее условие и исходное опорное решение записывается в распределительную таблицу. Клетки, в которых записан объем перевозки от -го поставщика к
-му потребителю называются занятыми, им соответствуют базисные переменные опорного решения. Остальные, незанятые клетки называются пустыми и им соответствуют свободные переменные. В верхнем правом углу каждой клетки записывается тариф перевозки груза от данного
-го поставщика к
-му потребителю.
При распределении грузов может оказаться, что количество занятых клеток меньше, чем (в случае вырожденной транспортной задачи). В этом случае недостающее их число заполняется клетками с нулевыми поставками, такие клетки называют условно занятыми. Нулевую поставку помещают в свободную клетку с наименьшим тарифом, причем чтобы в каждой строке и столбце было не менее одной занятой клетки.
Для определения исходного опорного плана ТЗ существует несколько методов. Рассмотрим на примере два из них: метод «северо-западного угла» и метод минимального элемента (метод наименьшей стоимости).
Задача №8.1.
На складах имеются запасы продукции в количествах 90, 400, 110 т соответственно. Потребители
должны получить эту продукцию в количествах 140, 300, 160 т соответственно. Построить первоначальный допустимый опорный план закрепления потребителей за поставщиками. Найти оптимальный план закрепления потребителей за поставщиками, при котором сумма затрат на перевозки была бы минимальной. Расходы по перевозке 1 т продукции заданы матрицей
в денежных единицах.
![Решение задач по математическому программированию](https://lfirmal.com/wp-content/uploads/2020/03/image-45826.png)
Решение:
Запишем исходные данные задачи в виде таблицы 8.2
![Решение задач по математическому программированию](https://lfirmal.com/wp-content/uploads/2020/03/image-45827.png)
Математическая модель задачи
Матрица перевозок:
![Решение задач по математическому программированию](https://lfirmal.com/wp-content/uploads/2020/03/image-45828.png)
Система ограничений:
![Решение задач по математическому программированию](https://lfirmal.com/wp-content/uploads/2020/03/image-45829.png)
Целевая функция:
![Решение задач по математическому программированию](https://lfirmal.com/wp-content/uploads/2020/03/image-45830.png)
является закрытой, необходимое и достаточное условие разрешимости задачи выполнено.
Запись математической модели данной транспортной задачи в табличном редакторе Microsoft Excel имеет вид (рис. 8.1).
![Решение задач по математическому программированию](https://lfirmal.com/wp-content/uploads/2020/03/image-45831.png)
- Найдем исходное опорное решение методом «северо-западного угла»:
![Решение задач по математическому программированию](https://lfirmal.com/wp-content/uploads/2020/03/image-45832.png)
В результате получен исходный опорный план, который является допустимым, так как все грузы (запасы поставщиков) вывезены, спрос потребителей удовлетворен, т.е. план соответствует системе ограничений ТЗ.
Число занятых клеток в таблице равно 5, =3 + 3-1 = 5 , т.е. условие невырожденности выполнено. Получим исходное опорное решение:
![Решение задач по математическому программированию](https://lfirmal.com/wp-content/uploads/2020/03/image-45833.png)
Стоимость перевозки (значение целевой функции) при исходном опорном решении составляет:
![Решение задач по математическому программированию](https://lfirmal.com/wp-content/uploads/2020/03/image-45834.png)
Метод минимального тарифа (элемента) (метод наименьших затрат)
Согласно этому методу, грузы распределяются в первую очередь в те клетки, в которых находится минимальный тариф перевозок . Далее поставки распределяются в незанятые клетки с наименьшими тарифами с учетом оставшихся запасов у поставщиков и удовлетворения спроса потребителей. Процесс распределения продолжают до тех пор, пока все грузы от поставщиков не будут вывезены, а спрос всех потребителей не будет удовлетворен.
Найдем исходное опорное решение для примера 8.1 методом минимального элемента:
Возможны два варианта
![Решение задач по математическому программированию](https://lfirmal.com/wp-content/uploads/2020/03/image-45836.png)
Опорный план:
![Решение задач по математическому программированию](https://lfirmal.com/wp-content/uploads/2020/03/image-45837.png)
Стоимость перевозки (значение целевой функции):
![Решение задач по математическому программированию](https://lfirmal.com/wp-content/uploads/2020/03/image-45838.png)
![Решение задач по математическому программированию](https://lfirmal.com/wp-content/uploads/2020/03/image-45839.png)
Опорный план:
![Решение задач по математическому программированию](https://lfirmal.com/wp-content/uploads/2020/03/image-45840.png)
Стоимость перевозки (значение целевой функции):
![Решение задач по математическому программированию](https://lfirmal.com/wp-content/uploads/2020/03/image-45841.png)
Проверка оптимальности плана и перераспределение поставок с помощью метода потенциалов.
Для анализа полученных планов и их последующего улучшения удобно ввести дополнительные характеристики пунктов отправления и назначения, называемые потенциалами.
Покажем, как нужно пользоваться методом потенциалов на примере первоначального плана, полученного выше по методу северозападного угла (рис. 8.2).
Найдем потенциалы по базисным (загруженным) клеткам таблицы с помощью формул
![Решение задач по математическому программированию](https://lfirmal.com/wp-content/uploads/2020/03/image-45842.png)
положив и :
![Решение задач по математическому программированию](https://lfirmal.com/wp-content/uploads/2020/03/image-45844.png)
Вычисляем оценки
![Решение задач по математическому программированию](https://lfirmal.com/wp-content/uploads/2020/03/image-45845.png)
свободных клеток:
![Решение задач по математическому программированию](https://lfirmal.com/wp-content/uploads/2020/03/image-45846.png)
Среди оценок имеются отрицательные, поэтому план не оптимален, его следует преобразовать в новый план. Занесём оценки в таблицу. Получим:
![Решение задач по математическому программированию](https://lfirmal.com/wp-content/uploads/2020/03/image-45847.png)
В левых нижних углах соответствующих клеток находятся оценки .
Чтобы улучшить план перевозок, необходимо для свободной клетки распределительной таблицы, имеющей отрицательную оценку, построить цикл пересчёта (цикл), который позволяет перераспределить занятые клетки так, чтобы получить новый план перевозок с меньшими суммарными затратами.
Цикл — совокупность клеток распределительной таблицы, из которых только одна клетка свободная, та, для которой строится цикл. Клетки, составляющие цикл, расположены в углах замкнутой ломаной линии, каждый отрезок которой лежит на одном и том же столбце распределительной таблицы.
Каждой клетке цикла поставим в соответствие знаки «+» и «—», которые при обходе цикла будут чередоваться. При этом свободную клетку (начальную клетку цикла) всегда считаем положительной.
Строим цикл с началом в клетке (3,1) с минимальной оценкой , он будет включать в себя клетки (см. таблицу 8.4):
![Решение задач по математическому программированию](https://lfirmal.com/wp-content/uploads/2020/03/image-45850.png)
Величина груза, перемещаемая с помощью цикла равна наименьшей из величии, расположенных в отрицательных клетках:
![Решение задач по математическому программированию](https://lfirmal.com/wp-content/uploads/2020/03/image-45851.png)
Найденную величину прибавим в положительных клетках цикла и вычтем в отрицательных. Клетка (2,1) станет свободной. Получим новый план перевозок, который занесём в таблицу 8.4:
![Решение задач по математическому программированию](https://lfirmal.com/wp-content/uploads/2020/03/image-45852.png)
Опорный план:
![Решение задач по математическому программированию](https://lfirmal.com/wp-content/uploads/2020/03/image-45853.png)
Стоимость перевозки (значение целевой функции):
![Решение задач по математическому программированию](https://lfirmal.com/wp-content/uploads/2020/03/image-45854.png)
Построена таблица с новым планом, состоящим из старых поставок, не вовлечённых в цикл и новых — в вершинах рассмотренного цикла. Проведём перерасчёт потенциалов и оценок
:
![Решение задач по математическому программированию](https://lfirmal.com/wp-content/uploads/2020/03/image-45857.png)
Оценки для незанятых клеток:
![Решение задач по математическому программированию](https://lfirmal.com/wp-content/uploads/2020/03/image-45858.png)
Наличие отрицательной оценки говорит о том, что данный план не является оптимальным.
Внесём данные в таблицу (таблица 8.5):
![Решение задач по математическому программированию](https://lfirmal.com/wp-content/uploads/2020/03/image-45859.png)
Строим цикл с началом в клетке (1,3) с оценкой включать в себя клетки (см. таблицу 8.5):
![Решение задач по математическому программированию](https://lfirmal.com/wp-content/uploads/2020/03/image-45861.png)
Тогда
![Решение задач по математическому программированию](https://lfirmal.com/wp-content/uploads/2020/03/image-45862.png)
Перераспределим груз по циклу, указанному в таблице 6.5 пунктиром на величину . Получим следующую распределительную таблицу:
![Решение задач по математическому программированию](https://lfirmal.com/wp-content/uploads/2020/03/image-45864.png)
Опорный план:
![Решение задач по математическому программированию](https://lfirmal.com/wp-content/uploads/2020/03/image-45865.png)
Стоимость перевозки (значение целевой функции):
![Решение задач по математическому программированию](https://lfirmal.com/wp-content/uploads/2020/03/image-45866.png)
Проверим план на оптимальность. Потенциалы:
![Решение задач по математическому программированию](https://lfirmal.com/wp-content/uploads/2020/03/image-45867.png)
Оценки для незанятых клеток:
![Решение задач по математическому программированию](https://lfirmal.com/wp-content/uploads/2020/03/image-45868.png)
План не является оптимальным, так как . Его нужно преобразовать в новый план, загрузив клетку (2,1). Цикл (см. таблицу 8.7):
![Решение задач по математическому программированию](https://lfirmal.com/wp-content/uploads/2020/03/image-45870.png)
По этому контуру находим поставку
![Решение задач по математическому программированию](https://lfirmal.com/wp-content/uploads/2020/03/image-45871.png)
Прибавляем к элементам, стоящим у вершин со знаком (+) и вычитаем из элементов, стоящих у вершин со знаком (-). Получаем новое опорное решение (см. таблицу 8.8)
![Решение задач по математическому программированию](https://lfirmal.com/wp-content/uploads/2020/03/image-45872.png)
Стоимость перевозки (значение целевой функции):
![Решение задач по математическому программированию](https://lfirmal.com/wp-content/uploads/2020/03/image-45873.png)
![Решение задач по математическому программированию](https://lfirmal.com/wp-content/uploads/2020/03/image-45874.png)
![Решение задач по математическому программированию](https://lfirmal.com/wp-content/uploads/2020/03/image-45875.png)
Исследуя этот план аналогично предыдущим, находим потенциалы (они приведены в таблице 8.8), и по ним — оценки свободных клеток:
![Решение задач по математическому программированию](https://lfirmal.com/wp-content/uploads/2020/03/image-45876.png)
Отрицательных оценок нет, следовательно, в таблице содержится оптимальный план.
Табличная модель.
Вводим данные в таблицу Excel
![Решение задач по математическому программированию](https://lfirmal.com/wp-content/uploads/2020/03/image-45877.png)
![Решение задач по математическому программированию](https://lfirmal.com/wp-content/uploads/2020/03/image-45878.png)
![Решение задач по математическому программированию](https://lfirmal.com/wp-content/uploads/2020/03/image-45879.png)
Вывод: Минимальные суммарные затраты на перевозку груза равны 1280 д.е. Они достигаются путем распределения поставок, представленных в ячейках [B4:D6]. Так, например, поставщик А1 должен доставить груз только потребителю ВЗ в количестве 90 единиц. Поставщик А2 должен поставить груз к потребителю В1 в количестве 30 ед., к потребителю В2 300 единиц и к потребителю ВЗ — 70 единиц.. Поставщик A3 должен доставить груз только потребителю В1 в количестве 90 ед. Поставщик A3 должен доставить груз только потребителю В1 в количестве 110 ед.
Возможно эта страница вам будет полезна:
Линейное программирование в Excel |
Модели целочисленного линейного программирования
При рассмотрении целого ряда экономических задач линейного программирования необходимо учитывать требование получения целочисленного решения. Такие задачи называются задачами целочисленного программирования .
Принципиальное отличие задачи целочисленного линейного программирования от обычной ЗЛП состоит только в том, что в системе ограничений вводится дополнительное ограничение па целочисленность переменных, т.е. задача целочисленного линейного программирования формулируется следующим образом: найти максимум или минимум функции
![Решение задач по математическому программированию](https://lfirmal.com/wp-content/uploads/2020/03/image-45880.png)
при ограничениях
![Решение задач по математическому программированию](https://lfirmal.com/wp-content/uploads/2020/03/image-45881.png)
а также дополнительном ограничении:
![Решение задач по математическому программированию](https://lfirmal.com/wp-content/uploads/2020/03/image-45882.png)
Для решения задач целочисленного программирования используют метод Гомори (метод отсечений) и метод ветвей и границ.
Идея метода Гомори состоит в том, что сначала задача решается без условия целочисленности. Если полученное решение целочисленное, то задача решена. В противном случае к ограничениям задачи добавляется новое ограничение, обладающее следующими свойствами: оно должно быть линейным;
должно отсекать найденный оптимальный нецелочисленный план;
- не должно отсекать ни одного целочисленного плана. Дополнительное ограничение, обладающее указанными свойствами, называется правильным отсечением.
Далее задача решается с учетом нового ограничения. После этого в случае необходимости добавляется еще одно ограничение и т.д.
Алгоритм метода Гомори
- С помощью симплекс-метода находят решение задачи (9.1) — (9.3) без учета требования целочисленности переменных. Если полученное решение целочисленное, то задача (9.1) — (9.4) решена. Если задача (9.1) -(9.3) неразрешима (т.е. не имеет конечного оптимума или условия ее противоречивы), то и задача (9.1) — (9.4) также неразрешима.
- Если полученное решение нецелочисленное, то составляют дополнительное ограничение для переменной, которая в оптимальном плане задачи (9.1)—(9.3) имеет максимальную дробную часть, а в оптимальном плане задачи (9.1)—(9.4) должна быть целочисленной. Для составления дополнительного ограничения используется последняя симплекс-таблица. Ограничение имеет вид:
![Решение задач по математическому программированию](https://lfirmal.com/wp-content/uploads/2020/03/image-45883.png)
где — дробная часть коэффициента при переменной
в
— той строке последней симплексной таблицы,
— дробная часть значения базисной переменной
.
- Неравенство (9.5) заменяют уравнением путем ввода дополнительной переменной и добавляют его к ранее решенной задаче, получают новую задачу. Решают ее симплексным методом, если оптимальный план новой задачи целочисленный, то исходная задача решена. В противном случае составляется новое дополнительное ограничение и т.д., пока не будет получено целочисленное решение задачи.
Возможно эта страница вам будет полезна:
Курсовая работа по линейному программированию |
Задача №9.1.
На приобретение оборудования (станков) для участка цеха выделены 30 т. р. Производственная площадь участка — 70 м2. Имеется возможность закупить станки двух видов: стоимостью 5 т. р. и 3 т. р. Станок первого вида требует для установки 12 м2 и дает продукции на 8 т. р. в месяц. Станок второго вида требует 6 м» площади и дает продукции на 2 т. р. в месяц. Определить оптимальный план приобретения оборудования, при котором производительность участка цеха в месяц была бы максимальной.
Решение:
- Составим математическую модель задачи:
— количество станков первого вида;
— количество станков второго вида;
![Решение задач по математическому программированию](https://lfirmal.com/wp-content/uploads/2020/03/image-45891.png)
целевая функция (производительность участка в месяц в ден. ед.).
Система ограничений:
![Решение задач по математическому программированию](https://lfirmal.com/wp-content/uploads/2020/03/image-45892.png)
- С помощью симплекс-метода найдем решение задачи без учета требования целочисленности переменных. Для этого приведем задачу к каноническому виду, т.е. в системе ограничений введем две дополнительные переменные
и
:
![Решение задач по математическому программированию](https://lfirmal.com/wp-content/uploads/2020/03/image-45895.png)
В качестве базисных переменных можем взять дополнительные переменные и
.
Составим симплексную таблицу (табл. 9.1):
I шаг.
![Решение задач по математическому программированию](https://lfirmal.com/wp-content/uploads/2020/03/image-45896.png)
Полученное на I шаге базисное решение (опорный план) не является оптимальным, т.к. в индексной строке есть отрицательные коэффициенты.
В качестве разрешающего выберем столбец, соответствующий переменной , т.к. ей соответствует наибольший по модулю отрицательный коэффициент (-8).
Вычислим оценочные отношения для строк соответствующих базисным переменным.
Вторая строка (соответствующая базисной переменной ) является разрешающей (ей соответствует минимальное оценочное отношение 5,8).
Разрешающий элемент 12, который находится на пересечении разрешающего столбца и разрешающей строки.
II шаг.
Производим пересчет симплекс-таблицы (в табл. 9.2 приведён конечный результат).
![Решение задач по математическому программированию](https://lfirmal.com/wp-content/uploads/2020/03/image-45897.png)
Полученный опорный план
![Решение задач по математическому программированию](https://lfirmal.com/wp-content/uploads/2020/03/image-45898.png)
является оптимальным, т.к. индексная строка не содержит отрицательных элементов.
![Решение задач по математическому программированию](https://lfirmal.com/wp-content/uploads/2020/03/image-45899.png)
Полученное решение нецелочисленное, поэтому составим дополнительное ограничение для переменной , которая в оптимальном плане задачи должна быть целочисленной. Для составления дополнительного ограничения воспользуемся последней симплекс-таблицей. Выпишем уравнение, содержащее неизвестную
:
![Решение задач по математическому программированию](https://lfirmal.com/wp-content/uploads/2020/03/image-45900.png)
Дополнительное ограничение будет иметь вид:
![Решение задач по математическому программированию](https://lfirmal.com/wp-content/uploads/2020/03/image-45901.png)
(фигурные скобки обозначают дробную часть числа).
![Решение задач по математическому программированию](https://lfirmal.com/wp-content/uploads/2020/03/image-45902.png)
С помощью дополнительной переменной преобразуем данное неравенство в уравнение:
![Решение задач по математическому программированию](https://lfirmal.com/wp-content/uploads/2020/03/image-45903.png)
и присоединим его к исходной системе ограничений, получим новую задачу. Для ее решения в последнюю симплекс-таблицу исходной задачи добавляем строку, соответствующую введенному ограничению (табл. 9.3).
![Решение задач по математическому программированию](https://lfirmal.com/wp-content/uploads/2020/03/image-45904.png)
План
![Решение задач по математическому программированию](https://lfirmal.com/wp-content/uploads/2020/03/image-45905.png)
недопустим, так как -5/6 < 0, зато -строка (0, 2, 0, 2/3, 0) не содержит отрицательных чисел. Это означает, что пашу задачу можно решить двойственным симплекс методом.
При решении задачи двойственным симплекс методом за разрешающую принимается строка с максимальным по абсолютной величине отрицательным . У нас это строка
. За разрешающий принимается столбец с минимальным значением-
, где а
(столбец
). Разрешающий элемент выделяем в таблице (см. табл. 9.3) и делаем для него шаг Жордана-Гаусса:
![Решение задач по математическому программированию](https://lfirmal.com/wp-content/uploads/2020/03/image-45911.png)
План
![Решение задач по математическому программированию](https://lfirmal.com/wp-content/uploads/2020/03/image-45912.png)
оптимален, но переменная не является целочисленной. Введем второе дополнительное ограничение, для этого из последней симплексной таблицы выпишем последнее уравнение:
![Решение задач по математическому программированию](https://lfirmal.com/wp-content/uploads/2020/03/image-45913.png)
Это ограничение добавляем в последнюю симплексную таблицу и решаем новую задачу двойственным симплекс-методом.
![Решение задач по математическому программированию](https://lfirmal.com/wp-content/uploads/2020/03/image-45914.png)
За разрешающую принимаем строку с максимальным по абсолютной величине отрицательным . У нас это строка
. За разрешающий принимается столбец с минимальным значением—
. где
(столбец
). Разрешающий элемент выделяем в таблице (см. табл. 9.5) и делаем для него шаг Жордана-Гаусса:
![Решение задач по математическому программированию](https://lfirmal.com/wp-content/uploads/2020/03/image-45917.png)
План
![Решение задач по математическому программированию](https://lfirmal.com/wp-content/uploads/2020/03/image-45918.png)
оптимален и является целочисленным, следовательно, оптимальное решение исходной задачи имеет вид:
![Решение задач по математическому программированию](https://lfirmal.com/wp-content/uploads/2020/03/image-45919.png)
Решение задачи целочисленной оптимизации в Microsoft Excel осуществляется командой Поиск решения из меню Данные. Но при решении целочисленных задач необходимо в форму представления данных ввести требование целочисленности переменных.
Вводим данные в таблицу Excel, как представлено на рисунке 9.1
![Решение задач по математическому программированию](https://lfirmal.com/wp-content/uploads/2020/03/image-45920.png)
Вызываем диалоговое окно Поиск решения и заносим в этом окне необходимые данные (рис. 9.3)
![Решение задач по математическому программированию](https://lfirmal.com/wp-content/uploads/2020/03/image-45921.png)
![Решение задач по математическому программированию](https://lfirmal.com/wp-content/uploads/2020/03/image-45922.png)
Кстати готовые на продажу задачи тут, и там же теория из учебников может быть вам поможет она.
Метод ветвей и границ
Задача №9.2.
Методом ветвей и границ решить задачу
![Решение задач по математическому программированию](https://lfirmal.com/wp-content/uploads/2020/03/image-45923.png)
при ограничениях
![Решение задач по математическому программированию](https://lfirmal.com/wp-content/uploads/2020/03/image-45924.png)
Решение:
Найдём оптимальное решение этой задачи как непрерывной (симплекс-методом).
Сначала приведем исходную (основную) задачу к каноническому виду. Очевидно, что для получения канонического вида необходимо прибавить 2 дополнительные неотрицательные переменные соответственно к первому и второму неравенствам системы ограничений.
![Решение задач по математическому программированию](https://lfirmal.com/wp-content/uploads/2020/03/image-45926.png)
Поэтому можно сразу обратиться к таблице Гаусса (табл.9.1) и заполнить соответствующие блоки.
![Решение задач по математическому программированию](https://lfirmal.com/wp-content/uploads/2020/03/image-45927.png)
Оптимальное решение задачи:
![Решение задач по математическому программированию](https://lfirmal.com/wp-content/uploads/2020/03/image-45928.png)
Верхний индекс у переменных соответствует номеру задачи.
В полученном решении не удовлетворяет требованиям цело-численности.
В связи с этим для дальнейшего решения составим задачи с граничными условиями, исключающими возможность получения нецелочисленного значения . Такими граничными условиями являются
![Решение задач по математическому программированию](https://lfirmal.com/wp-content/uploads/2020/03/image-45932.png)
Граничное условие входит в Задачу 2, решение которой найдём в Excel, используя надстройку «.Поискрешения».
- Создадим таблицу для ввода исходных данных: переменных, целевой функции,ограничений.
- Введем начальные нулевые значения для
и
.
- Зададим целевую функцию в ячейке F3 и ограничения в ячейках Е6, Е7 и Е8 (рис. (9.5).
![Решение задач по математическому программированию](https://lfirmal.com/wp-content/uploads/2020/03/image-45940.png)
Далее для исключения получения нецелочисленного значения
![Решение задач по математическому программированию](https://lfirmal.com/wp-content/uploads/2020/03/image-45941.png)
введём дополнительные граничные условия и решим последовательно две задачи: Задачу 3-е условиями
![Решение задач по математическому программированию](https://lfirmal.com/wp-content/uploads/2020/03/image-45942.png)
и Задачу 4-е условиями
![Решение задач по математическому программированию](https://lfirmal.com/wp-content/uploads/2020/03/image-45943.png)
Решения этих задач представлены, соответственно, на рис. 9.8 и рис. 9.9.
![Решение задач по математическому программированию](https://lfirmal.com/wp-content/uploads/2020/03/image-45944.png)
Схема решения всех этих задач приведена на рис. 9.10, а результат решения — в таблице 2
![Решение задач по математическому программированию](https://lfirmal.com/wp-content/uploads/2020/03/image-45946.png)
Из таблицы 2 видно, что решение Задачи 3 наиболее близкое к непрерывному по значениям переменных (см. таблицу 1), не является оптимальным. Оптимальным же является решение Задачи 4, в котором значения переменных существенно отличаются от непрерывного решения. Приведённый пример наглядно показывает, что округление оптимального решения непрерывной задачи может не обеспечить получения оптимального решения целочисленной задачи.