Навигация
Задача линейного программирования
18831
знак
3
таблицы
5
изображений
1. Задача линейного программирования
Линейное программирование – это направление математического программирования, изучающее методы решения экстремальных задач, которые характеризуются линейной зависимостью между переменными и линейным критерием.
Необходимым условием постановки задачи линейного программирования являются ограничения на наличие ресурсов, величину спроса, производственную мощность предприятия и другие производственные факторы.
Сущность линейного программирования состоит в нахождении точек наибольшего или наименьшего значения некоторой функции при определенном наборе ограничений, налагаемых на аргументы и образующих систему ограничений, которая имеет, как правило, бесконечное множество решений. Каждая совокупность значений переменных (аргументов функции F), которые удовлетворяют системе ограничений, называется допустимым планом задачи линейного программирования. Функция F, максимум или минимум которой определяется, называется целевой функцией задачи. Допустимый план, на котором достигается максимум или минимум функции F, называется оптимальным планом задачи.
Система ограничений, определяющая множество планов, диктуется условиями производства. Задачей линейного программирования (ЗЛП) является выбор из множества допустимых планов наиболее выгодного (оптимального).
Математическая модель любой задачи линейного программирования включает в себя:
1) максимум или минимум целевой функции (критерий оптимальности);
2) систему ограничений в форме линейных уравнений и неравенств;
2. Построение экономико-математической задачи
Требуется определить план выпуска четырех видов продукции, обеспечивающий максимальную прибыль от ее реализации. На изготовление этой продукции расходуются три вида ресурсов (R). С учетом рыночного спроса и производственно-технологических возможностей заданы предельные границы выпуска каждого вида продукции. Эти границы, наличие и нормы расхода ресурсов, а также маржинальная прибыль (разность между выручкой и переменными издержками) на единицу продукции приведены в таблице:
| Ресурсы | А | В | С | D | Наличие |
| Ресурс R1 | 4 | 2 | 1 | 4 | 530 |
| Ресурс R2 | 2 | - | 2 | 3 | 230 |
| Ресурс R3 | 2 | 3 | 1 | - | 570 |
| Прибыль | 15 | 10 | 9 | 13 | |
| Нижн. гр. | 15 | 30 | 0 | 10 | |
| Верхн. гр. | 150 | 300 | 75 | 300 |
Построим математическую модель задачи, обозначив количество выпускаемых изделий через х1, х2, х3, х4, а целевую функцию (валовую маржинальную прибыль) — через F:
F(х) = 15х1 + 10х2 + 9х3 + 13х4 →Мах;
Граничные условия:
4х1 + 2х2 + 1х3 + 4х4 <530;
2х1 +…+ 2х3 + 3х4 <230;
2х1 + 3х2 + 1х3+…<570;
х1,х2,х3,х4 >0
Ограничения:
15<x1<150,
30<x2<300,
x3<75,
10<x4<300,
х1,х2,х3,х4 >0
Решения, удовлетворяющие системе ограничений условий задачи и требованиям не отрицательности, называются допустимыми, а решения, удовлетворяющие одновременно и требованиям максимизации целевой функции, - оптимальными.
Выше описанная задача линейного программирования представлена в общей форме, но мне следует представить задачу в канонической форме. В канонической форме задача является задачей на максимум некоторой линейной функции F, ее система ограничений состоит только из равенств (уравнений). Для этого мне необходимо ввести дополнительные переменные.
На данном этапе следует представить задачу в канонической форме. Для того, чтобы реализовать данное действие, следует добавить дополнительные переменные. Получаем систему уравнений:
4х1 + 2х2 + х3 + 4х4 + х5=530;
2х1 +…+ 2х3 + 3х4 +х6=230;
2х1 + 3х2 + х3 +…+х7 =570;
х1,х2,х3,х4, х5,х6,х7 >0
(4х1 + 2х2 + х3 + 4х4 – мы реально физически используем данное кол-во; х5 – степень использования ресурса R1 (недоиспользованный ресурс). Аналогично будет и для других уравнений).
При этом необходимо ввести в целевую функцию издержки («убытки от недоиспользования ресурса»), которые были нам даны в изначальном условии, поэтому целевая функция будет следующей:
F(х) = 15х1 + 10х2 + 9х3 + 13х4 –2х5 – 3х6 – 4х7 →Мах.
Похожие работы
... Наилучшая альтернатива A1, следовательно, необходимо продлить договор с первым поставщиком. Заключение Данная курсовая работа состоит из двух частей: 1. Раздел I «Сетевые модели». 2. Раздел II «Использование метода анализа иерархий для организации поставок». В 1 разделе рассматривалась задача о минимизации протяженности дорог между 7-ю населенными пунктами. В ...
... Ю.Н. Математические методы в экономике: Учебник.2-е изд. – М.: МГУ им. М.В. Ломоносова, Издательство «Дело и Сервис», 1999. – 368 с. 7. Монахов А.В. Математические методы анализа экономики. – Спб: Питер, 2002. – 176 с. 8. Экономико-математические методы и прикладные модели: Учеб. пособие для вузов /В.В. Федосеев, А.Н. Гармаш, Д.М. Дайитбегов и др., Под ред. В.В. Федосеева. – М.: ЮНИТИ, 1999. ...
... , как детерминированность более поздних решений от более ранних. Кроме этих двух, достаточно детально разработанных методов, в экономических исследованиях в последнее время стали применяться множество других методов. Одним из подходов к решению экономических задач является подход, основанный на применении новой математической дисциплины - теории игр. Суть этой теории заключается в том, что игрок ( ...
... понятие теории понятие множества не подлежит логическому определению. Элементы множества могут иметь самую различную природу. Например, можно говорить о множестве микросхем, входящих в определенную конструкцию РЭА, или о множестве чертежей, входящих в полный комплект конструкторской документации для производства какого-либо изделия, и т. д. Множества обозначают заглавными буквами латинского ...
0 комментариев