Прочитать публикацию в формате PDF 169 Кб Для чтения PDF необходима программа Adobe Reader

Князева А., Лыкова Н.П.

ГОУ ВПО «Российский государственный гуманитарный университет»

Филиал в г. Самаре

постановка Задач линейного программирования и их решение с помощью msexcel

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

Свое второе рождение линейное программирование получило в начале пятидесятых годов с появлением ЭВМ. Тогда началось всеобщее увлечение линейным программированием, вызвавшее в свою очередь развитие других разделов математического программирования. В 1975 году академик Л.В.Канторович и американец профессор Т. Купманс получили Нобелевскую премию по экономическим наукам за "вклад в разработку теории и оптимального использования ресурсов в экономике".

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

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

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

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

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

1. задача об оптимальном использовании ресурсов при производственном планировании;

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

3. задача о нахождении оптимальной комбинации различных видов продукции для хранения на складах (управление товарно-материальными запасами или "задача о рюкзаке");

4. транспортные задачи (анализ размещения предприятия, перемещение грузов).

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

В общем виде модель записывается следующим образом:

целевая функция: F(x)= c₁x₁ + c₂x₂ + ... + cnxn → max(min) (1)

ограничения:

a₁₁x₁ + a₁₂x₂ + ... + a_1nxn {≤ = ≥} b₁,

a₂₁x₁ + a₂₂x₂ + ... + a_2nxn {≤ = ≥} b₂, (2)

...

a_m1x₁ + a_m2x₂ + ... + a_mnxn {≤ = ≥} b_m;

требование неотрицательности: x_j ≥ 0, j = 1, 2,……, n (3)

При этом a_ij, b_i, c_j (I = 1, 2, ….., m; j = 1, 2,……, n) - заданные постоянные величины.

Задача состоит в нахождении оптимального значения функции (1) при соблюдении ограничений (2) и (3).

Систему ограничений (2) называют функциональными ограничениями задачи, а ограничения (3) - прямыми.

Вектор, удовлетворяющий ограничениям (2) и (3), называется допустимым решением (планом) задачи линейного программирования. План, при котором функция (1) достигает своего максимального (минимального) значения, называется оптимальным.

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

Разберём решение таких задач на конкретном примере:

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

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

Запишем математическую модель:

Х шт – лисицы, У шт - песцы

16x+12y - max (1)

2x+3y180 (2)

4x+y240 (3)

6x+7y426 (4)

X>0, Y>0

Решение данной задачи аналитически сводится к решению системы из трёх неравенств (2-4), выражая значение одной переменной через другую получаем:

х  90 – 1,5у

4(90 – 1,5у) + у  240

6(90 – 1,5у) + 7у  426

х₁  54 х₂  4,5

у₁  24 у₂  57

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

Следовательно, целевая функция будет равна: 1152

Однако, с помощью MS Excel решение гораздо проще и быстрее.

Для решения задачи в MS Excel, необходимо создать таблицу с исходными данными (рис. 1)

Рис.1 – Таблица с исходными данными (задача на оптимизацию производства)

Затем с помощью встроенных функций MS Excel (=СУММПРОИЗВ) ввести ограничения и целевую функцию (рис.2)

Рис. 2 – ограничения и целевая функция

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

Рис. 3 – Поиск решения

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

Рис. 4 – Параметры поиска решения

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

Рис. 5 – Итоговая таблица, с полученным решением

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

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

Выделяют следующие три задачи анализа на чувствительность.

1. Анализ сокращения или увеличения ресурсов:

1) на сколько можно увеличить или уменьшить запас дефицитного ресурса для улучшения оптимального значения ЦФ?

2) на сколько можно уменьшить или увеличить запас недефицитного ресурса при сохранении полученного оптимального значения ЦФ?

2. Увеличение (уменьшение) запаса какого из ресурсов наиболее выгодно?

3. Анализ изменения целевых коэффициентов: каков диапазон изменения коэффициентов ЦФ, при котором не меняется оптимальное решение?

MS Excel позволяет делать отчет по результатам, который состоит из 3 таблиц:

1 – Целевая ячейка. В ней отображается начальное значение целевой функции и оптимальное (результат).

2- Изменяемые ячейки. В ней отражены исходные значения переменных и результирующие (оптимальные). Если продукт не входит в оптимальное решение (равен 0), то он считается не рентабельным.

3- Ограничения. Кроме имени ограничения, ячейки, в которую вписана левая часть ограничения, в ней отображены столбцы:

Значение – значение левой части ограничения при оптимальном плане. Т.е. сколько фактически использовано ресурса.

Формула – отображается знак ограничения (больше или равно, меньше или равно и т.д.)

Статус – отображено Связанное или не связанное ограничение. Если статус связанное, то ресурс использован полностью. Если же статус – не связанное, то ресурс использован не полностью.

Разница – отображено количество оставшегося не использованным ресурса.

А также отчет по устойчивости, который состоит из 2 таблиц:

1 – изменяемые ячейки. Кроме имени переменных и адресов ячеек в ней присутствуют столбцы:

Результирующее значение – это оптимальный план.

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

Целевой коэффициент – значения коэффициентов целевой функции.

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

2 – Ограничения. Кроме имени переменных и адресов ячеек в ней присутствуют столбцы:

Результирующее значение - значение левой части ограничения при оптимальном плане. Т.е. сколько фактически использовано ресурса.

Теневая цена – изменение целевой функции при изменении дефицитного ресурса на 1 единицу. Теневая цена недефицитного ресурса будет равна 0.

Ограничение Правая часть – запас ресурса.

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

Удобство использования MS Excel для решения задач линейного программирования заключается в том, что:

• создав один раз таблицу, её можно применять для задач такого же типа изменяя только исходные данные;

• все необходимые для решения задачи формулы уже представлены в MS Excel;

• решение задачи занимает в несколько раз меньше времени, нежели её же решение вручную;

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

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

Список литературы:

1. А.Г.Трифонов. Примеры решения оптимизационных задач // 2008

2. Попова Н.В. Математические методы // М.:ВТК. – 2005

Библиографическая ссылка

Лыкова Н.П., Князева А ПОСТАНОВКА ЗАДАЧ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ И ИХ РЕШЕНИЕ С ПОМОЩЬЮ MS EXCEL // Научный электронный архив.
URL: http://econf.rae.ru/article/5667 (дата обращения: 27.12.2024).

Получить сертификат

Форма заказа сертификата

Ф.И.О.
Почтовый адрес
Телефон
Авторы
Название работы
E-mail