Автор: Пользователь скрыл имя, 21 Февраля 2012 в 15:34, шпаргалка
Работа содержит ответы на вопросы для экзамена по "Логистике".
В классическом математическом анализе рассматривается задача отыскания условного экстремума функции. Тем не менее, время показало, что для многих задач, возникающих под влиянием запросов практики, классические методы недостаточны. В связи с развитием техники, ростом промышленного производства и с появлением ЭВМ все большую роль начали играть задачи отыскания оптимальных решений в различных сферах человеческой деятельности. Основным инструментом при решении этих задач стало математическое моделирование — формальное описание изучаемого явления и исследование с помощью математического аппарата.
Искусство математического
моделирования состоит в том,
чтобы учесть как можно больше
факторов по возможности простыми средствами.
Именно в силу этого процесс моделирования
часто носит итеративный
В большинстве случаев первой степенью приближения к реальности является модель, в которой все зависимости между переменными, характеризующими состояние объекта, предполагаются линейными. Здесь имеется полная аналогия с тем, как весьма важна и зачастую исчерпывающая информация о поведении произвольной функции получается на основе изучения ее производной — происходит замена этой функции в окрестности каждой точки линейной зависимостью. Значительное количество экономических, технических и других процессов достаточно хорошо и полно описывается линейными моделями.
Линейное программирование - это наука о методах исследования и отыскания наибольших и наименьших значений линейной функции, на неизвестные
которой наложены линейные ограничения. Таким образом, задачи линейного программирования относятся к задачам на условный экстремум функции. Казалось бы, что для исследования линейной функции многих переменных на условный экстремум достаточно применить хорошо разработанные методы математического анализа, однако невозможность их использования можно довольно просто проиллюстрировать.
Действительно, путь необходимо исследовать на экстремум линейную функцию
при линейных ограничениях
Так как Z - линейная функция, то n= Сj (j = 1, 2, ..., n), то все коэффициенты линейной функции не могут быть равны нулю, следовательно, внутри области, образованной системой ограничений, экстремальные точки не существуют. Они могут быть на границе области, но исследовать точки границы невозможно, поскольку частные производные являются константами.
При изучении задач линейного программирования сложилась определенная терминология:
Линейная форма , подлежащая максимизации (или минимизации), называется целевой функцией.
Вектор , удовлетворяющий всем ограничениям задачи линейного программирования, называется допустимым вектором, или планом.
Задача ЛП, для которой существуют допустимые векторы, называется допустимой задачей. Допустимый вектор , доставляющий наибольшее значение целевой функции по сравнению с любым другим допустимым вектором , т.е. , называется решением задачи, или оптимальным планом. Максимальное значение целевой функции называется значением задачи. Различают три основные формы задач линейного программирования в зависимости от наличия ограничений разного типа.
или, в матричной записи,
где — матрица коэффициентов. Вектор называется вектором коэффициентов линейной формы, — вектором ограничений.
Стандартная задача важна ввиду наличия большого числа прикладных моделей, сводящихся наиболее естественным образом к этому классу задач линейного программирования.
или, в матричной записи,
Основные вычислительные схемы решения задач линейного программирования разработаны именно для канонической задачи.
Пример. Приведем стандартную задачу линейного программирования к каноническому виду:
и обращающее в максимум линейную функцию от этих переменных:
Начнём с того, что приведём условия (1) к стандартной форме, так, чтобы знак неравенства был ³, а справа стоял нуль. Получим:
А теперь обозначим левые части неравенств (3) соответственно через y1 и y2:
Из условий (3) и (4) видно, что новые переменные y1, y2 также должны быть неотрицательными.
Какая же теперь перед нами стоит задача? Найти неотрицательные значения переменных x1,x2,x3,y1,y2 такие, чтобы они удовлетворяли условиям – равенствам (4) и обращали в максимум линейную функцию этих переменных (то, что в L не входит дополнительные переменные y1, y2, неважно: можно считать, что они входят, но с нулевыми коэффициентами). Перед нами – каноническая задача линейного программирования. Переход к ней от первоначальной задачи с ограничениями – неравенствами (2) «куплен» ценой увеличения числа переменных на два (число неравенств).
В этой задачи часть ограничений носит характер неравенств, а часть является уравнениями. Кроме того, не на все переменные наложено условие неотрицательности:
Здесь . Ясно, что стандартная задача получается как частный случай общей при ; каноническая — при .
Все три перечисленные задачи эквивалентны в том смысле, что каждую из них можно простыми преобразованиями привести к любой из двух остальных.