Моделирование задач линейного программирования доклад

Обновлено: 18.05.2024

Аннотация: Данная лекция раскрывает ряд вопросов, посвященных линейному программированию как одному из разделов математического программирования; в частности, формулирует основные виды задач линейного программирования, раскрывает отличия данных задач от классических задач математического анализа; знакомит с различными формами записи данных задач, осуществляет их постановку и исследование структуры. Наиболее полно раскрыт вопрос о решении задач линейного программирования симплекс-методом.

1. Понятие математического программирования

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

Наличие ограничений делает задачи математического программирования принципиально отличными от классических задач математического анализа по отысканию экстремальных значений функции. Методы математического анализа для поиска экстремума функции в задачах математического программирования оказываются непригодными.

Для решения задач математического программирования разработаны и разрабатываются специальные методы и теории. Так как при решении этих задач приходится выполнять значительный объем вычислений, то при сравнительной оценке методов большое значение придается эффективности и удобству их реализации на ЭВМ.

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

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

задачи линейного программирования,
задачи нелинейного программирования .

Если целевая функция и функции ограничений – линейные функции, то соответствующая задача поиска экстремума является задачей линейного программирования. Если хотя бы одна из указанных функций нелинейна, то соответствующая задача поиска экстремума является задачей нелинейного программирования .

2. Понятие линейного программирования. Виды задач линейного программирования

Линейное программирование (ЛП) – один из первых и наиболее подробно изученных разделов математического программирования . Именно линейное программирование явилось тем разделом, с которого и начала развиваться сама дисциплина " математическое программирование ". Термин "программирование" в названии дисциплины ничего общего с термином "программирование (т.е. составление программы) для ЭВМ" не имеет, т.к. дисциплина " линейное программирование " возникла еще до того времени, когда ЭВМ стали широко применяться для решения математических, инженерных, экономических и др. задач.

Термин " линейное программирование " возник в результате неточного перевода английского " linear programming ". Одно из значений слова "programming" - составление планов, планирование. Следовательно, правильным переводом английского " linear programming " было бы не " линейное программирование ", а "линейное планирование", что более точно отражает содержание дисциплины. Однако, термины линейное программирование , нелинейное программирование, математическое программирование и т.д. в нашей литературе стали общепринятыми и поэтому будут сохранены.

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

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

Линейное программирование применяется при решении экономических задач, в таких задачах как управление и планирование производства; в задачах определения оптимального размещения оборудования на морских судах, в цехах; в задачах определения оптимального плана перевозок груза (транспортная задача); в задачах оптимального распределения кадров и т.д.

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

$\min сх$

Общая форма задачи имеет вид: найти при условиях

$& a_i x - b_i \geq 0, \quad i \in I_1, \\ & a_i x - b_i = 0, \quad i \in I_2, \\ & x_j \geq 0, \quad j \in J_1$

$I_1 \cup I_2 & = \< 1 , \ldots , m \></p> <p>, \; I_1 \cap I_2 = \emptyset , \; J_1 \subset \ < 1, \ldots , n \>, \; x = ( x_1 , \ldots , x_n )^T , \\ c & = ( c_1 , \ldots , c_n ) , \; a_i = (a_ , \ldots , a_) , \; i = 1 , \ldots , m$

Наряду с общей формой широко используются также каноническая и стандартная формы. Как в канонической, так и в стандартной форме

$J_1 = \< 1, \ldots , n \></p> <p>$

т.е. все переменные в любом допустимом решении задачи должны принимать неотрицательные значения (такие переменные принято называть неотрицательные в отличие от так называемых свободных переменных, на область значений которых подобное ограничение не накладывается). Отличие же между этими формами состоит в том, что в одном случае I₂ = 0 , а в другом - I₁ = 0 .

Задача ЛП в канонической форме:

$w = cx \rightarrow \min$

( 2.1)

( 2.2)

$x \geq 0.$

( 2.3)

Задача ЛП в стандартной форме:

$w & = cx \rightarrow \min \\ Ax & \geq b \\ x & \geq 0$

В обоих случаях А есть матрица размерности m x n , i -я строка которой совпадает с вектором а_i .

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

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

Линейное программирование: постановка задач и графическое решение

Общая задача линейного программирования.

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

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

Примеры задач, решаемых графическим методом.

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

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

Действительно, путь необходимо исследовать на экстремум линейную функцию Z = С₁х₁+С₂х₂+. +С_Nx_N

при линейных ограничениях

Так как Z - линейная функция, то = С_j (j = 1, 2, . n), то все коэффициенты линейной функции не могут быть равны нулю, следовательно, внутри области, образованной системой ограничений, экстремальные точки не существуют. Они могут быть на границе области, но исследовать точки границы невозможно, поскольку частные производные являются константами.

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

Общая задача линейного программирования

Даны линейная функция

и система линейных ограничений

где а_ij, Ь_j и С_j - заданные постоянные величины.

Найти такие неотрицательные значения х₁, х₂, . х_n, которые удовлетворяют системе ограничений (1.2) и доставляют линейной функции (1.1)минимальное значение.

Общая задача имеет несколько форм записи.

Векторная форма записи. Минимизировать линейную функцию Z = СХ при ограничениях

состоят соответственно из коэффициентов при неизвестных и свободных членах.

Матричная форма записи. Минимизировать линейную функцию, Z = СХ при ограничениях АХ = А₀, Х 0, где С = (с₁, с₂, . с_N) - матрица-cтрока; А = (а_ij) - матрица системы;

Х - матрица-столбец, А₀ - матрица-столбец

Запись с помощью знаков суммирования. Минимизировать линейную функцию Z = С_jх_j при ограничениях

0пределение 1. Планом или допустимым решением задачи линейного программирования называется Х = (х₁, х₂, . х_N), удовлетворяющий условиям (1.2) и (1.3).

0пределение 2. План Х = (х₁, х₂, . х_N) называется опорным, если векторы А (i = 1, 2, . N), входящие в разложение (1.4) с положительными коэффициентами х , являются линейно независимыми.

Так как векторы А являются N-мерными, то из определения опорного плана следует, что число его положительных компонент не может превышать М.

0пределение 3. Опорный план называется невырожденным, если он содержит М положительных компонент, в противном случае опорный план называется вырожденным.

0пределение 4. Оптимальным планом или оптимальным решением задачи линейного программирования называется план, доставляющий наименьшее (наибольшее) значение линейной функции.

В дальнейшем рассмотрено решение задач линейного программирования, связанных с нахождением минимального значения линейной функции. Там, где необходимо найти максимальное значение линейной функции, достаточно заменить на противоположный знак линейной функции и найти минимальное значение последней функции. Заменяя на противоположный знак полученного минимального значения, определяем максимальное значение исходной линейной функции.

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

Рассмотрим задачу линейного программирования, система ограничений которой задана в виде неравенств.

Найти минимальное значение линейной функции

Совокупность чисел х₁, х₂, . х_N, удовлетворяющих ограничениям (1.6) и (1.7), называется решением. Если система неравенств (1.6) при условии (1.7) имеет хотя бы одно решение, она называется совместной, в противном случае - несовместной.

Рассмотрим на плоскости х₁Ох₂ совместную систему линейных неравенств

Это все равно, что в системе (1.6) - (1.7) положить N=2. Каждое неравенство этой системы геометрически определяет полуплоскость с граничной прямой

a_i1x₁ + a_i2x₂ = b_i ,(i = 1, 2, . m). Условия неотрицательности определяют полуплоскости соответственно с граничными прямыми х = 0, х = 0. Система совместна, поэтому полуплоскости, как выпуклые множества, пересекаясь, образуют общую часть, которая является выпуклым множеством и представляет собой совокупность точек, координаты каждой из которых являются решением данной системы (рис. 1.1).

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

Если в системе ограничений (1.6) - (1.7) n = 3, то каждое нера-венство геометрически представляет полупространство трехмерного пространства, граничная плоскость которого a_i₁x₁ + a_i₂x₂ + a_i₃x₃ = b_i ,(i = 1, 2, . n), а условия неотрицательности – полупрост-ранства с граничными плоскостями соответственно х_j = 0 (j = 1, 2, 3). Если система ограничений совместна, то эти полупространства, как выпуклые множества, пересекаясь, образуют в трехмерном пространстве общую часть, которая называется многогранником решений. Многогранник решений может быть точкой, отрезком, лучом, многоугольником, многогранником, многогранной неограниченной областью. Пусть в системе ограничений (1.6) - (1.7) n 3; тогда каждое неравенство определяет полупространство n-мерного пространства с граничной гиперплоскостью a_i₁x₁ + a_i₂x₂ + a_iNx_N = b_i (i = 1, 2, . m), а условия неотрицательности – полупространства с граничными гиперплоскостями х_j 0 (j = 1, 2, . n).

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

Таким образом, геометрически задача линейного программирования представляет собой отыскание такой точки многогранника решений, координаты которой доставляют линейной функции минимальное значение, причем допустимыми решениями служат все точки многогранника решений.

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

Графический метод основан на геометрической интерпретации задачи линейного программирования и применяется в основном при решении задач двумерного пространства и только некоторых задач трехмерного простран6тва, так как довольно трудно построить многогранник решений, который образуется в результате пересечения полупространств. Задачу пространства размерности больше трех изобразить графически вообще невозможно.

Пусть задача линейного программирования задана в двумерном пространстве, т. е. ограничения содержат две переменные.

Найти минимальное значение функции

Допустим, что система (2.2) при условии (2.3) совместна и ее многоугольник решений ограничен. Каждое из неравенств (2.2) и (2.3), как отмечалось выше, определяет полуплоскость с граничными прямыми: a_i₁x₁ + a_i₂x₂ + a_i₃x₃ = b_i,(i = 1, 2, . n), х₁=0, х₂=0. Линейная функция (2.1) при фиксированных значениях Z является уравнением прямой линии: С₁х₁ + С₂х₂ = const. Построим многоугольник решений системы ограничений (2.2) и график линейной функции (2.1) при Z = 0 (рис. 2.1). Тогда поставленной задаче линейного прграммирования можно дать следующую интерпретацию. Найти точку многоугольника решений, в которой прямая С₁х₁ + С₂х₂ = const опорная и функция Z при этом достигает минимума.

Значения Z = С₁х₁ + С₂х₂ возрастают в направлении вектора N =(С₁, С₂), поэтому прямую Z = 0 передвигаем параллельно самой себе в направлении вектора Х. Из рис. 2.1 следует, что прямая дважды становится опорной по отношению к многоугольнику решений (в точках А и С), причем минимальное значение принимает в точке А. Координаты точки А (х₁, х₂) находим, решая систему уравнений прямых АВ и АЕ.

Если многоугольник решений представляет собой неограниченную многоуголь-ную область, то возможны два случая.

Случай 1. Прямая С₁х₁ + С₂х₂ = const, передвигаясь в направлении вектора N или противоположно ему, постоянно пересекает многоугольник решений и ни в какой точке не является опорной к нему. В этом случае линейная функция не ограничена на многоугольнике решений как сверху, так и снизу (рис. 2.2).

Случай 2. Прямая, пере-двигаясь, все же становится опорной относительно многоу-гольника решений (рис. 2.2, а – 2.2, в). Тогда в зави-симости от вида области ли-нейная функция может быть ограниченной сверху и неограниченной снизу (рис. 2.2, а), ограниченной снизу и неограниченной сверху (рис. 2.2, б), либо ограниченной как снизу, так и сверху (рис. 2.2, в).

2.1. Примеры задач, решаемых графическим методом.

Решим графическим методом задачи использования сырья и составления рациона.

Задача использования сырья. Для изготовления двух видов продукции Р₁ и Р₂ используют три вида сырья: S₁, S₂, S₃. Запасы сырья, количество единиц сырья, затрачиваемых на изготовление единицы продукци, а так же величина прибыли, получаемая от реализации единицы продукции, приведены в таблице 2.1.

Теоретическая часть, в которой кратко рассмотрены основные вопросы теории.
Практическая часть, в которой рассмотрен 1 пример линейного программирования графическим способом.
НГТУ, 4 курс
Основой для решения экономических задач являются математические модели.
Линейное программирование - один из важнейших разделов математики, изучающий теории и методы решения определенных задач. Эта математическая дисциплина стала в последние годы широко применяться в различных областях экономики, техники и военного дела, где в их развитии не последнюю роль играет математическое планирование и использование автоматических цифровых вычислительных машин. Данный раздел науки изучает линейные оптимизационные модели. Иначе говоря, линейное программирование посвящено численному анализу и решению задач, требующих нахождения оптимального значения, т. е. максимума или минимума, некоторой системы показателей в процессе, а состояние его описывает система линейных неравенств.
Начало широкого использования линейных зависимостей для описания экономических явлений, многие из которых вовсе не обладают свойством линейности, было в середине ХХ в. подлинной научной революцией. Ее даже так и называли — линейная революция в экономике. Она дала мощный толчок развитию экономико-математических методов, способствовала всестороннему формированию практически применимого математического аппарата для исследования разнообразных областей экономики. Надо, однако, учитывать, что многие экономические процессы в действительности носят нелинейный и стохастический характер и их аппроксимация линейными зависимостями (линеаризация), упрощая расчеты, существенно огрубляет и искажает их. Поэтому линейные модели страдают известной ограниченностью в том, что касается отображения с их помощью реальных экономических процессов. Но во многих случаях созданный на этой основе математический аппарат в сочетании с компьютерной техникой, производящей сложные и трудоемкие расчеты, позволяет с успехом использовать такие модели в хозяйственной практике и в экономической науке.
Цель данной работы – рассмотреть модели линейного программирования - математические модели решения экономических задач, представленные в форме задач линейного программирования

Алесинская Т.В., Сербин В.Д., Катаев А.В. Учебно-методическое пособие по курсу Экономико-математические методы и модели. Линейное программирование

формат doc
размер 1.94 МБ
добавлен 24 октября 2011 г.

Таганрогский государственный радиотехнический университет, 2001, 84с. В учебно-методическом пособии рассмотрены вопросы построения математических моделей основных типов задач линейного программирования и способы их решения средствами табличного редактора Microsoft Excel, приведены примеры решения или рекомендации к решению конкретных задач. Предлагаемое учебно-методическое пособие рекомендуется для использования в курсе "Экономико-математические.

Березкин О.И., Кулагина А.Г. Математическое программирование

формат djvu
размер 6.98 МБ
добавлен 02 июля 2011 г.

Текст лекций для студентов экономических специальностей. Чебоксары. Изд.-во Чуваш. ун.-та, 2000. 164 c. Предмет математического программирования. Целевая функция ограничения. Основная постановка задачи. Классические методы решения задачи математического программирования и их возможности. Численные методы. Сплошное зондирование поверхности отклика. Равномерно-упорядоченное зондирование. Стохастическое зондирование (методы случайного поиска) Аддити.

Буторин. Математическая экономика

формат doc
размер 1.2 МБ
добавлен 17 апреля 2007 г.

Моделирование экономических процессов, математические модели. Математическая теория динамики развивающихся систем. Основные понятия. Классические методы описания динамических систем. Динамические модели в экономике. О классификации моделей. Некоторые примеры модели. Математическое моделирование. Зачем нужны модели? Примеры математических моделей. Математические модели и экономика. Линейная алгебра в экономике. Какие бывают задачи линейного прогр.

Мамаева З.М. Экономико-математические методы и модели

формат pdf
размер 808.68 КБ
добавлен 02 сентября 2011 г.

Математические методы исследования операций в экономике. Тест с ответами. 2011 г

формат doc
размер 2.92 МБ
добавлен 28 июня 2011 г.

Ответы к тесту МЭСИ по предмету "Математические методы исследования операций в экономике" К каноническому виду можно привести: В задаче линейного программирования область допустимых решений имеет: Задачу линейного программирования приводят к каноническому виду для: Как выглядит целевая функция вспомогательной задачи, если исходная задача имеет вид: В опорном плане задачи линейного программирования число ненулевых элементов:

Методическое пособие - Экономико-математические методы и модели

формат doc
размер 315 КБ
добавлен 16 марта 2011 г.

В.: ВолГТУ, экономический факультет, 2012 г. Содержание: Транспортная задача, по существу, представляет собой задачу линейного программирования, которую можно решать симплекс – методом. Однако специфическая структура условий задачи позволяет разработать более эффективный вычислительный метод. Определение транспортной модели и ее математическая постановка Решение транспортной задачи

Орлова И.В. Краткий конспект лекций и лабораторная работа № 1 по курсу Экономико-математические методы и прикладные модели

формат doc
размер 640.57 КБ
добавлен 12 ноября 2010 г.

Решение систем линейных уравнений методом Жордана - Гаусса. Общая задача оптимизации. Графический метод решения задач линейного программирования. Симплексный метод решения задачи линейного программирования. Технология решения задач линейного программирования с помощью Поиска решений в среде EXCEL. Двойственность в задачах линейного программирования. Анализ полученных оптимальных решений. Задания к контрольной работе.

Пазюк К.Т. Практикум по курсу Математические методы и модели в экономике

формат doc
размер 1.51 МБ
добавлен 25 декабря 2011 г.

Учебное пособие. - Хабаровск: Издательство ХГТУ, 2003. - 100с. Введение Линейное программирование Теоретические основы моделирования. Составление математической модели Графический метод задач линейного программирования (ЛП) Симплекс-метод решения задач линейного программирования (ЛП) Транспортная задача (ТЗ) Универсальная транспортная задача Теория игр, нелинейное и динамическое программирование Задачи теории игр Нелинейное программирование (НП).

Полежаев В.Д. и др. Методы и модели в экономике

формат doc
размер 538.21 КБ
добавлен 15 июля 2011 г.

Конспект лекций/ В.Д. Полежаев, Л.Н. Полежаева, Е.Н. Казанцева. – Омск: Изд-во ОмГТУ, 2008.– 64 с. Классификация экономико-математических методов и моделей. Линейное программирование. Теоретические основы методов линейного программирования. Геометрический (графический) метод решения задачи линейного программирования. Алгоритм геометрического метода решения задачи линейного программирования. Симплексный метод. Метод искусственного базиса. Двойств.

Поттосина С.А. Экономико-математические модели и методы

формат pdf
размер 819.97 КБ
добавлен 29 апреля 2009 г.

Минск: 2003 г. , - 94 стр. В учебном пособии представлены основные математические модели и методы для решения широкого класса прикладных задач экономического анализа. Теоретический материал сопровождается конкретными числовыми примерами. Для студентов и преподавателей экономических специальностей. Содержание Введение. Основные понятия математического моделирования социально-экономических систем. Линейные балансовые модели. Необходимые сведения.

Л.В. Канторович впервые сформулировал такие широко используемые экономико-математические понятия, как оптимальный план, оптимальное распределение ресурсов, объективно обусловленные оценки, указав многочисленные области экономики, где они могут быть применены.

В классическом математическом анализе исследуются общая постановка задачи определения условного экстремума. Однако в связи с развитием промышленного производства, транспорта, агропромышленного комплекса, банковского сектора традиционных результатов математического анализа оказалось недостаточно. Потребности практики и развитие вычислительной техники привели к необходимости определения оптимальных решений при анализе сложных экономических систем.

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

Линейное программирование получило широкое развитие в связи с тем, что было установлено: ряд задач сферы планирования и управления может быть сформулирован в виде задач линейного программирования, для решения которых имеются эффективные методы. По оценкам специалистов примерно 80–85 % всех решаемых на практике задач оптимизации относится к задачам линейного программирования.

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

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

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

К задачам линейного программирования сводится широкий круг вопросов планирования экономических процессов, где ставится задача поиска наилучшего (оптимального) решения.

Общая задача линейного программирования (ЗЛП) состоит в нахождении экстремального значения (максимума или минимума) линейной функции, называемой целевой[10]:

от n переменных x₁, x₂, …, х_n при наложенных функциональных ограничениях:

и прямых ограничениях (требовании неотрицательности переменных)

где a_ij, b_i, c_j – заданные постоянные величины.

ЗЛП в более краткой записи имеет вид:

Вектор `Х = (x₁, x₂, …, х_n) компоненты которого удовлетворяют функциональным и прямым ограничениям задачи называют планом (или допустимым решением) ЗЛП.

Все допустимые решения образуют область определения задачи линейного программирования, или область допустимых решений (ОДР). Допустимое решение, которое доставляет максимум или минимум целевой функции f(`X), называется оптимальным планом задачи и обозначается f(`X * ), где `Х * =(x₁ * , x₂ * , …, х_n * ).

Еще одна форма записи ЗЛП:

где f(`X * ) есть максимальное (минимальное) значение f(С, х), взятое по всем решениям, входящим в множество возможных решений Х.

Определение 2[11]. Математическое выражение целевой функции и ее ограничений называются математической моделью экономической задачи.

Для составления математической модели необходимо:

1) обозначить переменные;

2) составить целевую функцию исходя из цели задачи;

3) записать систему ограничений, учитывая имеющие в условии задачи показатели и их количественные закономерности.

от n переменных x₁, x₂, …, х_n при наложенных функциональных ограничениях:

и прямых ограничениях (требовании неотрицательности переменных)

где a_ij, b_i, c_j – заданные постоянные величины.

ЗЛП в более краткой записи имеет вид:

Еще одна форма записи ЗЛП:

Для составления математической модели необходимо:

1) обозначить переменные;

2) составить целевую функцию исходя из цели задачи;

ГОСТ

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

Основы экономико-математического моделирования и линейного программирования

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

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

Все формы математического моделирования любого экономического объекта предполагают последовательную реализацию следующих этапов:

описание экономической задачи;
построение математической модели (т.е. математическая формализация экономической ситуации);
практическое использование математической модели, получение решения и его анализ на допустимость, устойчивость и другие критерии;
экономическая интерпретация полученного решения.

Характеристика линейного программирования

Линейное программирование является одним из разделов этой математической теории, которая зачастую используется в науке для решения экономических задач. Впервые теоретические основы линейного программирования были сформулированы и опубликованы в 1939 году советским математиком и экономистом Л.В. Канторовичем. В том числе и за эту работу он в 1975 году был удостоен Нобелевской премии по экономике.

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

Готовые работы на аналогичную тему

Общая задача линейного программирования (еще называется стандартной задачей) заключается в нахождении минимума линейной целевой функции, которая принимает следующий вид:

Рисунок 1. Линейная функция. Автор24 — интернет-биржа студенческих работ

Если в экономической задаче присутствуют ограничения в форме неравенств, то она называется основной задачей линейного программирования. Эта задача может принять канонический вид, если вместо системы неравенств будет использоваться система равенств. Осуществить трансформацию задачи к каноническому виду можно благодаря введению дополнительных переменных.

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

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

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

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

Для решения общей задачи линейного программирования в большинстве случаев специалисты обращаются к такому известному методу, как симплекс-метод. Он был разработан американским математиком Джорджем Бернард Данцигом и впервые представлен публике в 1949 году.

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

Ещё один метод решения задач линейного программирования – это метод эллипсоидов, который относится к категории полиномиальных алгоритмов. Его разработчиком (относительно задач линейного программирования) считается советский математик Л. Хачиян, который предложил данный метод в 1979 году.

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

Читайте также: