Введение
Линейное программирование - это набор методов рационального анализа и решения проблем, призванный помочь лицам, принимающим решения, в вопросах, связанных с большим количеством переменных.
Название линейного программирования произошло не от создания компьютерных программ, а от военного термина «программирование», что означает «составление планов или сроков обучения, материально-технического обеспечения или развертывания боевых единиц».
Хотя кажется, что линейное программирование было использовано Г. Монжем в 1776 году, Л. В. Канторович считается одним из его создателей. Он представил ее в своей книге «Математические методы организации и производства» (1939 г.) и развил ее в своей работе «О передаче масс» (1942 г.). Канторович получил Нобелевскую премию по экономике в 1975 году за свой вклад в решение проблемы оптимального распределения человеческих ресурсов.
Исследования операций в целом и линейного программирования в частности получили большой импульс благодаря компьютерам. Одним из важнейших моментов стало появление симплекс-метода.
цели
- Знание линейного программирования и его приложений в повседневной жизни. Постановка и решение ситуаций с помощью линейного программирования. Этапы построения модели.
Тип решения
Линейные программы с двумя переменными обычно классифицируются по типу решения, которое они представляют. Это могут быть:
- Выполнимо: если существует набор решений или значений, удовлетворяющих ограничениям. Это, в свою очередь, может быть: с одним решением, с несколькими решениями (если существует более одного решения) и с неограниченным решением (когда нет предела для целевой функции) Невозможно: когда нет набора решений, которые соответствуют ограничений, то есть когда ограничения несовместимы.
Методы решения
Существует три метода решения задач линейного программирования:
- Графический метод: линии уровня показывают точки плоскости, в которых целевая функция принимает одно и то же значение. Аналитический метод: следующий результат, называемый фундаментальной теоремой линейного программирования, позволяет нам узнать другой метод решения программы с двумя переменными.: «В линейной программе с двумя переменными, если существует уникальное решение, оптимизирующее целевую функцию, оно находится в крайней точке (вершине) ограниченной допустимой области, но никогда внутри указанной области. Если целевая функция принимает одинаковое оптимальное значение в двух вершинах, она также принимает такое же значение в точках сегмента, который они определяют. В случае, когда допустимая область не ограничена, целевая линейная функция не обязательно достигает определенного оптимального значения, но если это так, то она находится в одной из вершин области ».Практическая схема: задачи линейного программирования могут быть представлены в стандартной форме с указанием функции, целей и ограничений, или они могут быть сформулированы с помощью утверждения.
Базовая структура:
Примеры линейного программирования взяты из:
www.superprof.es/apuntes/escolar/matematicas/algebralineal/pl/ejembres-de-programacion-lineal.html
Универмаг заказывает у производителя брюки и спортивные куртки.
У производителя есть 750 м хлопчатобумажной ткани и 1000 м полиэстера. Для каждой штаны требуется 1 м хлопка и 2 м полиэстера. На каждую куртку понадобится 1,5 м хлопка и 1 м полиэстера.
Цена на брюки - 50 долларов, пиджак - 40 долларов.
Какое количество брюк и курток производитель должен поставить на склады, чтобы они зарегистрировали максимальную продажу?
1. Выбор неизвестных.
- X = количество брюк Y = количество курток
2. Целевая функция
- F (x, y) = 50x + 40y
3. Ограничения
Чтобы написать ограничения, мы поможем себе таблицей:
| Штаны | Жакеты | Доступный | |
|
Хлопок |
один |
1,5 |
750 |
|
Полиэстер |
два |
один |
1000 |
- X + 1.5y <750 à 2x + 3y <1500 2x + y <1000
Поскольку количество брюк и курток - натуральные числа, у нас будет еще два ограничения:
- X> 0Y> 0
4. Найдите множество возможных решений.
Мы должны построить график ограничений.
Поскольку x> 0 и y> 0, мы будем работать в первом квадранте.
Изображаем линии, начиная с их точек пересечения с осями.
Линейное программирование
Решаем графически неравенство: 2x + 3y <1500, для этого берем точку плоскости, например (0,0).
Поскольку 0 <1500, то точка (0,0) находится в полуплоскости, где выполняется неравенство.
Аналогично решите 2x + y <1000.
Линейное программирование
Область пересечения решений неравенств будет решением системы неравенств, которая составляет множество возможных решений.
5. Вычислить координаты вершин огораживания возможных решений.
Оптимальное решение, если оно уникальное, находится в углу вольера. Это решения систем:
2х + 3у = 1500; х = 0 (0,500)
2х + у = 1000; у = 0 (500,0)
2х + 3у = 1500; 2х + у = 1000 (375, 250)
Линейное программирование
6. Рассчитайте значение целевой функции.
В целевую функцию подставляем каждую из вершин.
- F (x, y) = 50x + 40yF (0,500) = 50 * 0 + 40 * 500 = 20000 долларов США (500,0) = 50 * 500 + 40 * 0 = 25000 долларов США (375 250) = 50 * 375 + 40 * 250 = 28750 долларов
Оптимальное решение - сделать 375 штанов и 250 курток с прибылью в 28 750 долларов.
Библиография:
Примеры линейного программирования взяты из:
www.superprof.es/apuntes/escolar/matematicas/algebralineal/pl/ejembres-de-programacion-lineal.html
