Формы линейных математических моделей и их преобразование

Лекция 2

графический метод нахождения оптимального решения

1. Формы линейных математических моделей и их преобразование

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

3. Особые ситуации графического решения ЗЛП

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

Формы линейных математических моделей и их преобразование

Математическая модель задачи линейного программирования (ЗЛП) может быть записана в одной из трех форм.

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

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

В стандартной форме математической модели требуется найти максимум или минимум функции; все ограничения являются неравенствами; все переменные неотрицательны.

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

Множество допустимых решений называют областью допустимых решений ЗЛП.

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

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

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

Переход к канонической форме записи ЗЛП.

Пример.

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

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

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

Особые ситуации графического решения ЗЛП

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

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

2. задача не разрешима из-за неограниченности ОДР, или – рисунок 3;

3. ОДР - единственная точка А, тогда ;

4. задача не разрешима, если ОДР есть пустая область.

В

А

Рисунок 2 Рисунок 3

Если линия уровня параллельна стороне области допустимых решений, то экстремум достигается во всех точках стороны . Задача имеет бесчисленное множество оптимальных решений – альтернативный оптимум. Оптимальное решение находится по формуле

,

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

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

Эту задачу рекомендуется решить студентам самостоятельно.

Вопросы для самоконтроля

1. Запишите задачу линейного программирования в общей форме.

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

3. С помощью каких преобразований можно перейти от общей или стандартной формы задачи линейного программирования к канонической?

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

5. Какое из решений и является «лучшим» для задачи минимизации функции , если ?

6. Какое из решений и является «лучшим» для задачи максимизации функции , если ?

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

8. Как построить полуплоскость, заданную линейным неравенством с двумя переменными ?

9. Что называется решением системы линейных неравенств с двумя переменными? Постройте на плоскости область допустимых решений такой системы линейных неравенств, которая:

1) имеет единственное решение;

2) имеет бесконечное множество решений;

3) не имеет ни одного решения.

10. Запишите для линейной функции вектор градиент, назовите вид линий уровня. Как расположены относительно друг друга градиент и линии уровня?

11. Сформулируйте алгоритм графического метода решения стандартной ЗЛП с двумя переменными.

12. Как найти координаты решения и значения , ?

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

1) достигается в единственной точке, а - на отрезке ОДР;

2) достигается в единственной точке ОДР, а .

14. Дайте геометрическую иллюстрацию ЗЛП, если она:

1) имеет единственные оптимальные решения для и ;

2) имеет множество оптимальных решений для .

Лекция 2

графический метод нахождения оптимального решения

1. Формы линейных математических моделей и их преобразование

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

3. Особые ситуации графического решения ЗЛП

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

Формы линейных математических моделей и их преобразование

Математическая модель задачи линейного программирования (ЗЛП) может быть записана в одной из трех форм.

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

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

В стандартной форме математической модели требуется найти максимум или минимум функции; все ограничения являются неравенствами; все переменные неотрицательны.

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

Множество допустимых решений называют областью допустимых решений ЗЛП.

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

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

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

Переход к канонической форме записи ЗЛП.

Пример.

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

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

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

Что делает отдел по эксплуатации и сопровождению ИС? Отвечает за сохранность данных (расписания копирования, копирование и пр.)...

Живите по правилу: МАЛО ЛИ ЧТО НА СВЕТЕ СУЩЕСТВУЕТ? Я неслучайно подчеркиваю, что место в голове ограничено, а информации вокруг много, и что ваше право...

Конфликты в семейной жизни. Как это изменить? Редкий брак и взаимоотношения существуют без конфликтов и напряженности. Через это проходят все...

Что будет с Землей, если ось ее сместится на 6666 км? Что будет с Землей? - задался я вопросом...

Не нашли то, что искали? Воспользуйтесь поиском гугл на сайте: