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



Скачать 409.17 Kb.
страница1/6
Дата02.01.2013
Размер409.17 Kb.
ТипГлава
  1   2   3   4   5   6
ГЛАВА 8. ЛИНЕЙНОЕ ПРОГРАММИРОВАНИЕ
8.1. Задачи математического и линейного

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

Несмотря на разнообразие смыслового содержания задач математического программирования, все они с формальной точки зрения сводятся к одной общей постановке:

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

(8.1)

и удовлетворяющие в то же время системе условий вида

. (8.2)

Эти условия (8.2) называются ограничениями задачи. В каждом из них, естественно, должен сохраняться какой-либо один знак: или =, или , или . Множество значений переменных , удовлетворяющих всем ограничениям задачи, составляет её область определения. Функция в формуле (8.1) называется целевой функцией.

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

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

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

, (8.3)

. (8.4)

Здесь и – известные постоянные коэффициенты. Из дополнительных ограничений обычно присутствует требование . Если же дополнительно поставлено условие, что все или некоторые целые числа, то возникает задача целочисленного (или дискретного) линейного программирования. Методы её решения имеют свои особенности, что не позволяет отождествлять «целочисленную» и «простую» задачи.

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

, (8.5)

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

Математическое программирование как наука возникло в 30-е годы XX века для решения экономических задач. Советским экономистом А.Н. Толстым в 1930 году впервые была сформулирована и решена задача по составлению оптимального плана перевозок, позволяющего минимизировать суммарный километраж. Слово «программирование» означает процедуру перебора переменных , определяющих оптимальный план решения экономической задачи. Термин «линейное программирование» впервые появился в 1951 году в работах американского экономиста Дж. Данцига, который разработал и опубликовал основной метод решения задач линейного программирования – симплексный метод. Наиболее интенсивно линейное программирование развивалось в СССР и в США в 1955-65 годах. В 1975 году советскому математику академику Л.В. Канторовичу и американскому экономисту Т. Купмансу была присуждена Нобелевская премия по экономике за разработку теории оптимального использования ресурсов.

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

В современном понимании математическое программирование есть область прикладной математики, которая является теоретической основой решения задач оптимального планирования экономических процессов.
8.2. Экономико-математические модели простейших задач

линейного программирования
1. З а д а ч а и с п о л ь з о в а н и я р е с у р с о в (п л а н и р о в а- н и я п р о и з в о д с т в а).

Производственная задача об оптимальном использовании ресурсов является одной из важнейших задач линейного программирования. Рассмотрим её экономическую постановку. Пусть предприятие выпускает n различных видов изделий P1, P2, …, Pn , для изготовления которых требуется m различных типов ресурсов S1, S2, …, Sm . Ресурсами могут быть различные виды сырья, вспомогательные материалы, полуфабрикаты, электроэнергия, запасы машинного времени, людские ресурсы и т.п. Объём каждого типа ресурсов всегда ограничен и в планируемый период составляет соответственно b1, b2, …, bm условных единиц.

Считаются известными также технологические коэффициенты , показывающие, сколько единиц i-го ресурса Si требуется для производства единицы j-го вида изделия Pj . Кроме того, считается известной прибыль , получаемая от реализации (продажи) единицы изделия вида Pj ,.

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

Все данные производственной задачи представим для наглядности в виде таблицы 1.

Таблица 1

Типы

ресурсов

Технологические коэффициенты aij

число единиц ресурсов Si, затрачиваемых на изготовление единицы изделия Pj

Объёмы запасов ресурсов

P1

P2



Pn

S1











S2























Sm











Прибыль от реализации ед. изделия

c1

c2



cn




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

Пусть предприятие предполагает изготовить и выпустить на реализацию x1 единиц изделий вида P1, x2 единиц изделий вида P2, …, xn единиц изделий вида Pn . Тогда на все изделия всех видов P1, P2, …, Pn израсходуется ресурсов первого типа S1 в количестве

. (8.6)

Аналогичные неравенства должны выполняться и для остальных типов ресурсов S2, S3, …, Sm . Следует учитывать также, что все значения , , так как есть количество единиц выпускаемых изделий вида Pj .

Общая прибыль, получаемая от реализации (продажи) всей продукции P1, P2, …, Pn , производимой соответственно в количестве единиц, представляется в виде линейной функции

. (8.7)

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

Таким образом, математическая модель производственной задачи использования ресурсов в общей постановке имеет следующую формулировку:

требуется найти такой план объёма выпускаемой продукции , удовлетворяющий системе ограничений

(8.8)

и условиям

, (8.9)

при котором целевая функция

(8.10)

принимает наибольшее значение: .

2. З а д а ч а с о с т а в л е н и я р а ц и о н а (задача о диете, задача о смесях, задача о закупке ресурсов).

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

Пусть имеется n различных видов продуктов P1, P2, …, Pn и перечень из m питательных веществ S1, S2, …, Sm , необходимых для составления рациона. Обозначим через содержание в весовых единицах i-го питательного вещества Si в единице j-го продукта Pj , а через bi обозначим минимальную суточную потребность в i-м питательном веществе Si. Через xj обозначим количество каждого вида продуктов Pj в весовых единицах в ежедневном рационе, тогда , . Кроме того, будем считать известной стоимость весовой единицы j-го продукта Pj , .

Все данные задачи представим для наглядности в виде таблицы 2

Таблица 2

Питательные вещества

Коэффициенты aij – количество i-го вещества в единице j-го продукта Pj

Минимальная суточная

потребность

P1

P2



Pn

S1











S2























Sm











Стоимость

1 кг продукта Pj

c1

c2



cn



Для первого вида питательного вещества S1 неравенство – ограничение примет вид

. (8.11)

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

, (8.12)

которую нужно минимизировать.

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

требуется составить дневной рацион , удовлетворяющий системе ограничений

(8.13)

и условиям

, (8.14)

при котором функция цели

, (8.15)

выражающая стоимость продуктов питания P1, P2, …, Pn, принимает наименьшее значение: .

  1   2   3   4   5   6

Похожие:

Линейное программирование задачи математического и линейного программирования iconЛинейное программирование. Методы решения одношаговых задач оптимального управления
Методы решения таких задач получили название математического программирования. Простейшим случаем математического программирования...
Линейное программирование задачи математического и линейного программирования iconВопросы экзаменационных билетов по курсу "линейное программирование"
Постановка и различные формы записи задач линейного программирования: стандартная, каноническая, общая. Эквивалентность задач линейного...
Линейное программирование задачи математического и линейного программирования iconПараметрическое линейное программирование
Параметрическое программирование представляет собой один из разделов математического программирования, изучающий задачи, в которых...
Линейное программирование задачи математического и линейного программирования iconЗадачи линейного программирования
Темой одного из таких специальных курсов могло бы стать линейное программирование задач из различных отраслей экономики и управления...
Линейное программирование задачи математического и линейного программирования iconТематика и примеры контрольных заданий и вопросов (тестирование, индивидуальные типовые расчеты, коллоквиум) очная форма обучения тест №1. Тема «Линейное программирование»
Приводить задачу линейного программирования к канонической форме; применять графический метод, симплексный метод для решения задач...
Линейное программирование задачи математического и линейного программирования iconЛинейное программирование и симплекс-метод
Цель данного курсового проекта составить план производства требуемых изделий, обеспечивающий максимальную прибыль от их реализации,...
Линейное программирование задачи математического и линейного программирования iconТранспортная задача
Линейное программирование является одним из разделов математического программирования – области математики, разрабатывающей теорию...
Линейное программирование задачи математического и линейного программирования iconРассматриваются прикладные математические методы и модели, в том числе методы математического программирования (поиск экстремума, линейное, нелинейное, динамическое программирование), системы массового обслуживания

Линейное программирование задачи математического и линейного программирования iconПредпосылки возникновения линейного программирования
Линейное программирование — математическая дисциплина, посвященная теории и методам решения задач об экстремумах линейных функций...
Линейное программирование задачи математического и линейного программирования iconРешение задачи линейного программирования
Решить задачу линейного программирования. Используя теорию двойственности, доказать правильность полученного решения
Разместите кнопку на своём сайте:
ru.convdocs.org


База данных защищена авторским правом ©ru.convdocs.org 2016
обратиться к администрации
ru.convdocs.org