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

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

Текст из файла

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

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

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

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

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

Крайние точки такой области и выпуклого многогранника (многоугольника) называют вершинами.

Каждое ограничение типа неравенства (например, или ) выделяет в пространстве координат полупространство, кото­рому принадлежат все точки, лежащие по одну сторону от гипер­плоскости ( или х_i = 0) и на самой этой гиперплоскости. Дан­ное полупространство (при п=2 полуплоскость) является выпук­лым множеством. Ограничение типа равенства выделяет в простран­стве координат гиперплоскость (при n= 2 плоскость), являющуюся тоже выпуклым множеством. Пересечение всех полупространств и гиперплоскостей, задаваемых всеми ограничениями, если они не противоречивы, будет областью XD допустимых решений ЗЛП. Область XD является выпуклой многогранной (при п= 2 многоугольной) областью или выпуклым многогранником (многоуголь­ником или в частном случае отрезком прямой или точкой).

Если существует конечное оптимальное решение ЗЛП (мини­мум и/или максимум), то оно достигается либо в одной из вер­шин выпуклого многогранника или многогранной области XD, ли­бо на выпуклом множестве, порождаемом двумя или более верши­нами (на грани многогранника или многогранной области, стороне многоугольника или многоугольной области).

Возможны следующие случаи областей XD допустимых зна­чений X и соответствующих им оптимальных решений ЗЛП.

1. Система уравнений и неравенств, задаваемая ограниче­ниями, несовместна. Тогда области XD не существует и нет решений ЗЛП. Пример отсутствия области XD при п- 2 изо­бражен на рис. 3.2.

1. Область XD не является ограниченной.

2.1. Область XD не ограничена в направлении возрастания функции f(X), тогда при поиске максимума этой функции решение ЗЛП не ограничено, т.е. нет конечного решения ЗЛП, а при поиске минимума функции f(X) оптимальное решение ЗЛП находится в точке X* (точках) области XD, ближайшей к линии постоянного уровня функции f(Х)=с₀.

Пример данной области XD и решения ЗЛП при п= 2 при­веден на рис. 3.3. Стрелкой на линии постоянного уровня функ­ции f(X)= с₀ будем показывать направление ее возрастания.

2.2. Аналогично, если XD не ограничена в направлении убыва­ния функции f(X), тогда при по­иске минимума этой функции ре­шение ЗЛП не ограничена, т.е. нет конечного решения ЗЛП, а при поиске максимума функции f(X) оптимальное решение ЗЛП нахо­дится в точке X* (точках) области XD, ближайшей к линии постоянного уровня функции f(X)= с₀.

Пример данной области и решения ЗЛИ при п=2 и целевой функции f(X) приведен на рис. 3.4.

3. Наиболее или/и наименее удаленная от f(X)= с₀ грань или грани многогранника (при n= 2 сторона или стороны многоугольника) области XD параллельна поверхности (линии постоянного уровня функции f(X)= с₀. Тогда решением ЗЛП будет все множество точек, лежащих на этих гранях многогранника {сторонах многоугольника). При этом минимум дости­гается в точках с наименьшим в XD значением функции f(X), а максимум — с наибольшим.

На рис. 3.5 представлены примеры таких областей и реше­ний ЗЛП при п = 2. В случае области XD, изображенной на рис. 3.5, а, минимум достигается на множестве решений, явля­ющихся точками отрезка АВ, а максимум — отрезка CD. Отрез­ки АВ и CD параллельны линиям постоянного уровня функций f(X)= с₀ и f ₁(Х)=с₀. Для области XD₁, показанной на рис. 3.5, б, минимум при решении ЗЛП достигается в точке X*, а мак­симум — на множестве точек отрезка CD. В случае области XD₂ на рис. 3.5, в максимум достигается в точке X* , а мини­мум — на множестве точек отрезка АВ.

4. Наиболее и наименее удаленные от f(X)=с₀ грани мно­гогранника (при п= 2 стороны многоугольника) ограниченной области XD не параллельны поверхностям (линиям) постоян­ного уровня функции f(X). Тогда ЗЛП имеет единственные минимум и максимум в наиболее и наименее удаленных от f(X)= с₀ точках области XD. На рис. 3.6, а,б,в приведены примеры при п= 2 таких областей XD₃ (в виде четырехуголь­ника) и XD₄ (в виде отрезка прямой) и решений ЗЛП для трех различных целевых функций: f(X), f₁(Х) и f₂(Х). Ми­нимум достигается в X*₁, а максимум — в X*₂

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

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

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

2. Если XD – пустое множество (когда система неравенств, задаваемая ограничениями, несовместна), то решений ЗЛП нет и переходим к п.5.

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

4. Определяем оптимальные решения ЗЛП, которыми являются найденные в п.3 вершины XD и все множество точек сторон XD, выделенных в п.3. При этом минимум достигается в точке (точках) с наименьшим в XD значением функции, а максимум – с наибольшим.

5. конец алгоритма.

Симплекс метод Данцига для решения ЗЛП частного вида.

Рассмотрим решение симплекс-методом ЗЛП в случае ограничений частного вида, когда имеется m ограничений со знаком неравенства « », сводимых к канонической форме, т.е. решается задача

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

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

Базисным решением называется такая совокупность значений и , что n из всех n+m переменных равны нулю, а m переменных выражены через оставшиеся. n переменных, приравненных к нулю, называют небазисными. Остальные m переменных образуют базис, и их называют базисными.

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

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

Таблица 3.1

Таблица 3.2

Строка r и столбец s, где находится разрешающий элемент , называются разрешающими строкой и столбцом соответст­венно. В базисном столбце находятся базисные переменные и це­левая функция (например, в табл. 3.1 это и f). В небазисных столбцах в первой строке таблицы на каждой итера­ции находятся небазисные переменные со знаком минус, например, в табл. 3.1 на к-й итерации небазисными переменными яв­ляются

Характеристики

Тип файла документ

Документы такого типа открываются такими программами, как Microsoft Office Word на компьютерах Windows, Apple Pages на компьютерах Mac, Open Office - бесплатная альтернатива на различных платформах, в том числе Linux. Наиболее простым и современным решением будут Google документы, так как открываются онлайн без скачивания прямо в браузере на любой платформе. Существуют российские качественные аналоги, например от Яндекса.

Будьте внимательны на мобильных устройствах, так как там используются упрощённый функционал даже в официальном приложении от Microsoft, поэтому для просмотра скачивайте PDF-версию. А если нужно редактировать файл, то используйте оригинальный файл.

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

Список файлов ответов (шпаргалок)