Нахождение альтернативного максимума задачи линейного программирования с помощью программы "Поиск решения"

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

Рубрика Программирование, компьютеры и кибернетика
Вид статья
Язык русский
Дата добавления 05.05.2019
Размер файла 235,1 K

Отправить свою хорошую работу в базу знаний просто. Используйте форму, расположенную ниже

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

Размещено на http://www.allbest.ru//

1

Размещено на http://www.allbest.ru//

Нахождение альтернативного максимума задачи линейного программирования с помощью программы «Поиск решения»

Овчинникова О.И.

Линейное программирование рассматривается не только как наука о методах исследования и отыскания экстремальных (наибольших и наименьших) значений линейной функции, на неизвестные которой наложены линейные ограничения [4], но и как специальный класс оптимизационных задач, в котором все отношения между переменными выражаются линейными функциями, а переменные принимают действительные значения [1]. Основоположниками линейного программирования считаются Л.В. Канторович (1912-1986) и Д. Данциг (1914-2005). Впервые задача линейного программирования (ЗЛП) в России была сформулирована в 1939 г. Л.В. Канторовичем, который применил математическую модель этой задачи в экономике и разработал метод решения. В 1975 г. Л.В. Канторович получил Нобелевскую премию за достижения в этой области [2]. В 1947 г. американский ученый Д. Данциг разработал алгоритм решения ЗЛП [1].

Математическая модель ЗЛП [4] имеет вид

Содержание ЗЛП формулируется следующим образом: необходимо найти набор действительных чисел (вектор) Хопт = (х1, х2, …, хn), доставляющий экстремум (максимум или минимум) линейной целевой функции (1) и удовлетворяющий системе ограничений (2). ЗЛП может иметь одно или множество оптимальных решений Хопт, которые называются альтернативным отпимумом [4]. Выявление альтернативного оптимума в решении ЗЛП представляется важным условием понимания существенных взаимосвязей, обеспечивающих достижение целевой функцией оптимального значения. При изучении ЗЛП с двумя переменными обязательно рассматривается графический способ ее решения. Критерием альтернативного оптимума в этом случае выступает совпадение оптимальной линии уровня целевой функции Lопт с одной из сторон многоугольника области допустимых решений (ОДР), а оптимальное решение Хопт находится по формуле

где Хопт1 и Хопт2 - оптимальные решения в угловых точках области допустимых решений (ОДР); 0 ? t ? 1; (хопт11; хопт12) и (хопт21; хопт22) - координаты угловых точек ОДР [4].

Развитие программного обеспечения современных компьютеров расширяет способы решения задач оптимизации в учебном процессе. Программа «Поиск решения» электронных таблиц Excel позволяет в автоматическом режиме находить только одно оптимальное решение Хопти значение целевой функции L(Хопт) [3]. Если ЗЛП имеет единственное решение, то данная программа определяет его однозначно. Если ЗЛП имеет альтернативный оптимум, то пользователю становится известно одно частное решение. В отчете о результатах вычислений данная программа сигнализирует о множестве оптимальных решений, отмечая в статусе одной из функциональных зависимостей системы ограничений связанность с целевой функцией (если ЗЛП с двумя переменными имеет единственное решение, то связанность с целевой функцией фиксируется у двух функциональных зависимостей системы ограничений). Составление множества Хопт становится возможным, если моделируются ситуации, при которых обеспечивается достижение условий для использования формулы (3).

Проведем анализ математической модели ЗЛП с двумя переменными и альтернативным оптимумом, которая имеет следующий вид

(4)

(5)

Коэффициенты переменных в одном из неравенств системы ограничений пропорциональны коэффициентам целевой функции, что и определяет характерное расположение линии уровня целевой функции Lопт и одной из сторон М1М2 многоугольника ОДР (рис. 1).

Размещено на http://www.allbest.ru//

1

Размещено на http://www.allbest.ru//

Рис. 1. Граница ОДР (ОДР располагается ниже отрезка М1М2)

Угловой коэффициент k прямой Lопт равен отношению коэффициентов целевой функции (k = c2/c1). Если увеличить c1 на положительную величину д, а c2 оставить без изменения, то линия уровня Lопт совершит поворот по ходу часовой стрелки и примет положение, которое на рис. 1 отмечено как Lопт2. При таком изменении целевой функции (4) ЗЛП будет иметь одно оптимальное решение, которому будут соответствовать значения координат точки М2 (рис. 1). Если увеличить c2 на положительную величину д, а c1 оставить без изменения, то линия уровняLопт совершит поворот против хода часовой стрелки и примет положение, которое на рис. 1 отмечено как Lопт1. При этом изменении целевой функции (4) ЗЛП будет иметь также одно оптимальное решение, которому будут соответствовать значения координат точки М1 (рис. 1). Нахождение координат точек М1 и М2, которые являются угловыми в ОДР, позволяет составить множество Хопт при использовании формулы (3). Установление Хопт ЗЛП, заданной математической моделью (4)-(5), с помощью программы «Поиск решения» требует определения Хопт1 и Хопт2, которые относятся к ЗЛП1 и ЗЛП2. Система ограничений ЗЛП1 и ЗЛП2 описывается системой неравенств (5). Математические модели целевых функций L1(X) и L2(X) этих задач соответственно будут иметь вид

(6)(7)

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

(8)

(9)

Функциональные зависимости (8) и (9) вводятся в ячейки электронного процессора Excel, а в соответствующих разделах диалогового окна программы «Поиск решения» фиксируются их адреса. Автоматический поиск Хопт и L(Хопт) завершается сообщением результата: х1 = 0,8; х2 = 1,6; L(0,8; 1,6) = 20. Для определения Хопт1 и Хопт2 следует составить ЗЛП1 и ЗЛП2 с единой ОДР, которая описывается системой неравенств (9). Величине д можно, например, присвоить значение, равное 0,5. Математические модели целевых функций L1(x1; x2) и L2(x1; x2) соответственно для ЗЛП1 и ЗЛП2 составляются по формулам (6), (7) и принимают с учетом выбранной д следующий вид

(10)

(11)

Результат работы программы «Поиск решения» для ЗЛП1 и ЗЛП2: Хопт1 = (0; 2), L1(0; 2) = 21, Хопт2 = (2; 1), L2(2; 1) = 21. Нахождение Хопт1 и Хопт2 позволяет записать множество всех оптимальных решений ЗЛП (8)-(9) по формуле (3) в матричном виде

Проверка полученного результата (12) может проводиться через его сравнение с результатом, к которому приведет применение другого способа решения ЗЛП. Использование графического способа решения [4] ЗЛП (8)-(9) отражено на рис. 2.

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

Размещено на http://www.allbest.ru//

1

Размещено на http://www.allbest.ru//

Рис. 2. Линия уровня целевой функции Lопт и ОДР

Четырехугольник М1М2М3М4 - это ОДР системы ограничений (9) (рис. 2), сторона М2М3 совпадает с оптимальной линией уровня целевой функции Lопт(Хопт) = 20. Координаты вершин М2(0; 2) и М3(2; 1) определяют оптимальные решения Хопт1 и Хопт2, а их подстановка в формулу (3) подтверждает ранее полученный результат Хопт (12). Нахождение множества оптимальных решений ЗЛП с двумя переменными при использовании программы «Поиск решения» требует соблюдения условий (составление и решение ЗЛП1 и ЗЛП2), рассмотренных в данной работе.

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

Алексеева Е.В. Построение математических моделей целочисленного линейного программирования. Примеры и задачи: учеб. пособие / Новосиб. Гос. ун-т. Новосибирск, 2012. 131 с.

Вершик А.М. Леонид Витальевич Канторович: человек и ученый: В 2 т. Новосибирск:

Изд-во СО РАН. Филиал «Гео», 2002. Т.1.

Вуколов Э.А. Основы статистического анализа. Практикум по статситическим методам и исследованию операций с использованием пакетов STATISTICA и EXCEL: учеб. пособие. - 2-е изд,, испр. и доп. - М.: ФОРУМ, 2008. 464 с.

Красс М.С., Чупрынов Б.П. Основы математики и ее приложения в экономическом образовании: учеб. пособие. Издательство: Дело, 2008 г. 688 с.

Размещено на Allbest.ru


Подобные документы

  • Теоретическая основа линейного программирования. Задачи линейного программирования, методы решения. Анализ оптимального решения. Решение одноиндексной задачи линейного программирования. Постановка задачи и ввод данных. Построение модели и этапы решения.

    курсовая работа [132,0 K], добавлен 09.12.2008

  • Анализ метода линейного программирования для решения оптимизационных управленческих задач. Графический метод решения задачи линейного программирования. Проверка оптимального решения в среде MS Excel с использованием программной надстройки "Поиск решения".

    курсовая работа [2,2 M], добавлен 29.05.2015

  • Алгоритм решения задач линейного программирования симплекс-методом. Построение математической модели задачи линейного программирования. Решение задачи линейного программирования в Excel. Нахождение прибыли и оптимального плана выпуска продукции.

    курсовая работа [1,1 M], добавлен 21.03.2012

  • Математическое программирование. Линейное программирование. Задачи линейного программирования. Графический метод решения задачи линейного программирования. Экономическая постановка задачи линейного программирования. Построение математической модели.

    курсовая работа [581,5 K], добавлен 13.10.2008

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

    курсовая работа [678,7 K], добавлен 03.04.2011

  • Критерий эффективности и функции в системе ограничений. Общая постановка задачи линейного программирования. Составление математической модели задачи. Алгоритмы решения задачи симплексным методом. Построение начального опорного решения методом Гаусса.

    курсовая работа [232,4 K], добавлен 01.06.2009

  • Общее понятие и характеристика задачи линейного программирования. Решение транспортной задачи с помощью программы MS Excel. Рекомендации по решению задач оптимизации с помощью надстройки "Поиск решения". Двойственная задача линейного программирования.

    дипломная работа [2,4 M], добавлен 20.11.2010

  • Применение методов линейного программирования для решения оптимизационных задач. Основные понятия линейного программирования, свойства транспортной задачи и теоремы, применяемые для ее решения. Построение первичного опорного плана и системы потенциалов.

    курсовая работа [280,8 K], добавлен 17.11.2011

  • Изучение и укрепление на практике всех моментов графического метода решения задач линейного программирования о производстве журналов "Автомеханик" и "Инструмент". Построение математической модели. Решение задачи с помощью электронной таблицы Excel.

    курсовая работа [663,9 K], добавлен 10.06.2014

  • Решение задачи линейного программирования графическим методом, его проверка в MS Excel. Анализ внутренней структуры решения задачи в программе. Оптимизация плана производства. Решение задачи симплекс-методом. Многоканальная система массового обслуживания.

    контрольная работа [2,0 M], добавлен 02.05.2012

Работы в архивах красиво оформлены согласно требованиям ВУЗов и содержат рисунки, диаграммы, формулы и т.д.
PPT, PPTX и PDF-файлы представлены только в архивах.
Рекомендуем скачать работу.