Использование Microsoft Excel для решения задач линейного программирования

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

Министерство образования и науки РФ

Федеральное государственное бюджетное образовательное учреждение высшего образования

«Карачаево-черкесский государственный университет имени У. Д. Алиева»

Физико-математический факультет

Кафедра информатики и вычислительной математики

Выпускная квалификационная работа

Использование Microsoft Excel для решения задач линейного программирования

Автор Ф.М. Абайханова

Научный руководитель

ст.пр. З.К. Джаубаева

Карачаевск 2017



ВВЕДЕНИЕ

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

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

Объект исследования - методика формирования умений и навыков у студентов решения задач линейного программирования с помощью прикладной программы Microsoft Excel.

Предмет исследования - использование прикладных программ при преподавании математики в вузе.

Задачи исследования:

- изучить общие понятия и определения;

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

- освоить основные способы использования EXCEL при решении ЗЛП;

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

На защиту выносятся следующие положения:

- различные способы вычисления ЗЛП оживят изучение такой дисциплины, как математика, научат студентов пользоваться полученными знаниями, терминологией;

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

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

математика линейный программирование еxcel



ГЛАВА 1. МЕТОДЫ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ

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

Начало линейного программирования было положено в 1939 году советским математиком и экономистом Л. В. Канторовичем в работе "Математические методы организации и планирования производства». Появление этой работы открыл новый этап в применении математики в экономике.

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

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

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

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

Общая идея симплекс-метода (последовательное усовершенствование метода плана) для решения ЗЛП распределилась следующим образом:

1. Способность найти первоначальную программу поддержки;

2. Наличие оптимальности программы поддержки;

3. Возможность перехода к нехудшему программы поддержки.

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

1.2 Основные понятия и определения

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

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

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

1) множество неизвестных, действуя на которые могут улучшить систему. Они призвали задачи (векторное управление, решение, менеджмент, стратегия, поведение и т.д.);

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

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

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



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

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

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

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

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

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

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

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

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

· при планировании грузовых потоков, определение плана товарооборота и его распределение;

· в задачах развития и размещения производительных сил, баз и складов систем обработки материалов, ресурсов и т.д.

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

Мы пришли к выводу, что к классу задач линейного программирования (ЗЛП) относится большое разнообразие задач планирования и управления, таких как, например, [1, 2]:

* нахождение оптимального плана выхода (оптимальное распределение ресурсов);

* оптимизация межотраслевых потоков (планирование производства различных видов продукции по отраслям промышленности);

* определение оптимального рациона (оптимизация химической смеси);

* транспортная задача (оптимальное распределение товарных потоков снабжения транспортной сети);

* Проблема распределения производства (планирование, принимая во внимание стоимость производства и транспортировки продукции);

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

И экономико-математическая модель любой задачи линейного программирования включает в себя:

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

· ограничения в виде системы линейных уравнений и неравенств;

· требование неотрицательности переменных.

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

целевая функция:

F(x)= c₁x₁ + c₂x₂ + ... + c_nx_n > max(min) (1.1)

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

a₁₁x₁ + a₁₂x₂ + ... + a_1nx_n {? = ?} b₁,

a₂₁x₁ + a₂₂x₂ + ... + a_2nx_n {? = ?} b₂, (1.2)

a_m1x₁ + a_m2x₂ + ... + a_mnx_n {? = ?} b_m;

требование неотрицательности:

x_j ? 0, j = 1, 2,……, n (1.3)



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

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

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

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

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

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

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

Вид корма	Ежедневное количество корма усл. ед.	Общее количество корма, усл.ед.
	Лисица	песец
1	2	3	180
2	4	1	240
3	6	7	426
Прибыль от реализации одной шкурки, руб.	16	12

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

Запишем математическую модель: x шт - лисицы, y шт - песцы

16x+12y > max (1.4)

180 (2)2x+3y

240 (3)4x+y

426 (4)6x+7y

x>0, y>0

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

90 - 1,5у х

2404(90 - 1,5у) + у

4266(90 - 1,5у) + 7у

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. Анализ сокращения или увеличения ресурсов:

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

б) на сколько можно увеличить или уменьшить запас легкодоступного ресурса, сохранив при этом полученную оптимальную стоимость ДФ?

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

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

В MS Excel позволяет составить отчет по результатам состоит из трех таблиц:

1 - клетки-мишени. Отображает начальное значение целевой функции и оптимальное (результат).

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

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

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

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

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

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

А также сообщать о стабильности, который состоит из двух таблиц:

1 - изменение клеток. В дополнение к имени переменной и адрес клеток, присутствующих в ее столбцах:

Полученное значение - это лучший план.

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

фактор доверия - значение коэффициентов целевой функции.

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

2 - Ограничения. В дополнение к имени переменной и адрес клеток, присутствующих в ее столбцах:

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

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

Ограничения на правой части - поставка ресурса.

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

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

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

* все необходимое, чтобы решить проблему формулы уже представленной в MS Excel;

* Решение задачи занимает в несколько раз меньше времени, чем ее собственной рукой решения;

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

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

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

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

Метод решения	Примечание	Целевая функция
1. Графический метод	Используется при двух переменных (x1, x2)	max, min
2. Симплексный метод	Формы записи: симплексная таблица, строчечная форма, строковая форма. Алгоритм решения: метод искусственного базиса (М-метод, двухфазный метод), правило прямоугольника, правило Креко	max, min
3. Двойственный симплекс-метод	Формы записи: симплексная таблица, строчечная форма, строковая форма. Алгоритм решения: метод искусственного базиса (М-метод, двухфазный метод)	Min
4. Двойственная задача	Алгоритм решения: симплекс-метод, теоремы двойственности	max, min
5. Метод Гомори	Алгоритм решения: метод отсечений	max, min

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

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

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

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

для решения ЗЛП состоит из умение находить начальный опорный план; наличие знака оптимальный план; умение идти на nehusha план поддержки.

Общая идея симплексного метода (метода последовательного улучшения плана) для решения ЗЛП состоит:

- от возможности найти оригинальную программу поддержки;

- оптимальность программы поддержки ;

- возможность перехода в программу поддержки nehusha.

Пусть ZLP будет представлена системой ограничений в канонической форме:

Говорят, что ограничение ЗЛП имеет предпочтительный вид, если при неотрицательной правой части левая часть ограничений содержит переменную, входящую с коэффициентом, равным единице, а в остальные ограничения равенства - с коэффициентом, равным нулю.

Пусть система ограничений имеет вид

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

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

В целевую функцию дополнительные переменные вводятся с коэффициентами, равными нулю

Пусть далее система ограничений имеет вид

Сведём её к эквивалентной вычитанием дополнительных переменных из левых частей неравенств системы. Получим систему

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

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

Как мы уже отмечали выше, в настоящее время одним из наиболее перспективных, но недостаточно распространенных методов численного решения задач линейного программирования является использование надстройки "поиск решений" MS Excel spreadsheets. В частности, "поиск решения", как мы показали в предыдущем примере, предоставляет возможности:

используйте планы больших аналитик (т. е. с большим количеством переменных параметров);

ограничение сложной формы;

поиск оптимального решения;

создание множества различных решений, которые хранятся в долгосрочной перспективе в виде скриптов;

автоматическая генерация отчетов по решению задачи.

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

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

Как мы уже отмечали выше, в настоящее время одним из наиболее перспективных, но недостаточно распространенных методов численного решения задач линейного программирования является использование надстройки "поиск решений" MS Excel spreadsheets. В частности, "поиск решения", как мы показали в предыдущем примере, предоставляет возможности:

используйте планы больших аналитик (т. е. с большим количеством переменных параметров);

ограничение сложной формы;

поиск оптимального решения;

создание множества различных решений, которые хранятся в долгосрочной перспективе в виде скриптов;

автоматическая генерация отчетов по решению задачи.

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

"Поиск решения" -это дополнение к Excel, то есть это может быть не стандартная установка электронной таблицы. Чтобы добавить его, просто используйте команду сервис, надстройки, поиск решения.

1.4 Основные формы записи задач линейного программирования

Рассмотрим формы записи задачи линейного программирования:

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

при ограничениях

x_j - произвольные (j=n₁+1,…,n) (1.10)

где c_j ,a_ij, b_i - заданные действительные числа; (1.5) - целевая функция; (1.6) - (1.10) -ограничения; - план задачи.
Пусть ЗЛП представлена в следующей записи:

maxZ=cx (1.11)

A₁x₁+ A₂x₂ +…+ A_nx_n=A₀ (1.12)

x₁?0, x₂ ?0,…, x_n?0 (1.13)

Чтобы задача (1.11) - (1.12) имела решение, система её ограничений (1.13) должна быть совместной. Это возможно, если r этой системы не больше числа неизвестных n. Случай r>n вообще невозможен. При r=n система имеет единственное решение, которое будет при оптимальным.

В этом случае проблема выбора оптимального решения теряет смысл. Выясним структуру координат угловой точки многогранных решений. Пусть r<n. В этом случае система векторов A₁,A₂,…,A_n содержит базис - максимальную линейно независимую подсистему векторов, через которую любой вектор системы может быть выражен как ее линейная комбинация. Базисов, вообще говоря, может быть несколько, но не более . Каждый из них состоит точно из r векторов. Переменные ЗЛП, соответствующие r векторам базиса, называют, как известно, базисными и обозначают БП. Остальные n - r переменных будут свободными, х обозначают СП. Не ограничивая общности, будем считать, что базис составляют первые m векторов A₁,A₂,…,A_n. Этому базису соответствуют базисные переменные а свободными будут переменные .

Если свободные переменные приравнять нулю, а базисные переменные при этом примут неотрицательные значения, то полученное частное решение системы (1.12) называют опорным решением (планом).

Теорема 1. Если система векторов A₁,A₂,…,A_n содержит m линейно независимых векторов A₁,A₂,…,A_m , то допустимый план

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

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



ГЛАВА 2. ПРАКТИЧЕСКАЯ РЕАЛИЗАЦИЯ ЗАДАЧ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ С ПОМОЩЬЮ MICROSOFT EXCEL

2.1 Электронные таблицы Microsoft Excel

Программа MS Excel предназначена для работы с таблицами данных, в основном с числами. При формировании таблицы вводятся, редактируются и форматируются текстовые и числовые данные, а также формулы. Наличие средств автоматизации облегчает эти операции. Созданные таблицы можно распечатать. Документ Excel называется книгой. Рабочая книга-это коллекция рабочих листов, каждый из которых имеет структуру таблицы и может содержать одну или несколько таблиц. В окне документа Microsoft Excel отображает только текущий рабочий лист.

Каждый рабочий лист имеет имя, которое отображается на листе ярлыка, отображаемого в нижней части. Используйте вкладки, чтобы переключиться на другие листы в той же книге. Чтобы переименовать лист, необходимо дважды щелкнуть по его метке. Рабочий лист состоит из столбцов и строк. Столбцы называются заглавными латинскими буквами, за которыми следует строка из 2 символов. Общий лист может содержать до 256 столбцов, пронумерованных от A до IV. Строки нумеруются последовательно, от 1 до 65536. На пересечении строк и столбцов ячеек формируются листы. Они минимальные детали, котор нужно хранить. Обозначение одной ячейки объединяет номера строк и столбцов, например A1. Этот персонаж действует как адрес. Адреса ячеек используются при записи формул. Выделенная ячейка называется активной ячейкой. Все операции ввода и редактирования выполняются в активной ячейке. Данные в соседних ячейках, можно ссылаться в формулах как на единое целое. Эта группа ячеек называется диапазоном. Наиболее часто используются прямоугольные диапазоны, образующие группы последовательных строк и группы последовательных столбцов на пересечении. Для выбора прямоугольного диапазона необходимо потянуть указатель с одного угла на противоположную диагональную линию.

Ввод, редактирование и форматирование данных

Отдельные ячейки могут содержать данные одного из трех типов: текст, число или формулы и оставаться пустыми. При сохранении книги в файл Excel записывает только прямоугольник на листы, расположенные рядом с левым верхним углом (ячейка A1) и содержащие все заполненные ячейки.

Ввод формулы всегда начинается с символа " = " (знак равенства). Ввод данных осуществляется непосредственно в текущую ячейку или в строку формул в верхней части окна, непосредственно под панелями инструментов. Поместите курсор ввода текста помечен. Если вы начинаете писать с буквенно-цифровых ключей, данные из текущей ячейки заменяются введенным текстом. Если щелкнуть строку формул или дважды щелкнуть текущую ячейку, старое содержимое ячейки не удаляется и его можно изменить. Чтобы завершить запись, сохраните данные с помощью кнопки Enter на панели формул или клавиши Enter. Чтобы отменить изменения и восстановить прежнее значение ячейки, используют кнопку отмена в строке формул или клавишу ESC. Легче использовать клавишу Delete для очистки текущей ячейки или выбранного диапазона. По умолчанию текстовые данные выровнены по левому краю, а числа выровнены по правому краю. Чтобы изменить Формат отображения данных в текущей ячейке или выбранном диапазоне, используют: Формат ячеек®. Вкладки в этом диалоговом окне позволяют выбрать формат для записи данных.

Расчеты в электронных таблицах

Расчеты в электронных таблицах Excel с помощью формул. Формула может содержать числовые константы, ссылки на ячейки и функции Excel, симптомы математических операций. Скобки позволяют изменять стандартную процедуру выполнения действий. Если ячейка содержит формулу, на листе отображается текущий результат вычисления этой формулы. Если сделать ячейку текущей, то сама формула отображается в строке формул. Ячейка, в которой находится курсор, называется текущей ячейкой. Право на использование формул в Excel заключается в том, что если значение ячейки действительно зависит от других ячеек таблицы, всегда следует использовать формулу, даже если операцию легко можно выполнить в "уме". Это гарантирует, что последующее редактирование таблицы не нарушит ее целостности и правильности расчетов, выполненных в нем. Формула может содержать ссылки, то есть адрес ячейки, содержимое которой используется в вычислениях. Это означает, что результат вычисления формулы зависит от количества, которое находится в другой ячейке. Таким образом, ячейка, содержащая формулу, является зависимой.

Использование стандартных функций.

Стандартные функции используются только в формулах Excel. Вызов функции должен указывать в Формуле имени функции, за которой следуют скобки в списке параметров. Отдельные параметры разделяются в списке точкой с запятой. В качестве числа параметров можно использовать адрес ячейки или произвольные выражения для вычисления функции, которые также можно использовать.

Палитра формул.

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

Печать документов Excel

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

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

Чтобы напечатать документ на бумаге, нажмите Печать или выберите файл ® область печати ® установить. В этом случае область печати можно задать вручную, т. е. печатать только нужную часть текста на бумаге.

Формулы в Microsoft Excel - это программируемый калькулятор таблиц. Все вычисления выполняются в формулах Excel. В Excel считает все, что начинается со знака "="формулу. Если написать "1+1" в ячейке, Excel не будет вычислять выражение. Однако, если написать "=1 + 1 " и нажать Enter, в ячейке появится результат вычисления выражения - число 2. После нажатия Enter формула не пропадает, это можно увидеть, если дважды щелкнуть по ячейке, или если выделить ее и нажать F2 или просто нажмите Ctrl+Апостроф. Его также можно увидеть на панели инструментов "панель формул", если снова выделить ячейку. После двойного щелчка, нажатия F2 или щелкнуть в строке формул, можно изменить формулу и нажмите клавишу Enter для завершения.

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

Если формула использует текст, она должна быть заключена в двойные кавычки. Если написать формулу "=мама", Excel выдаст ошибку, а если написать " = "мама "" - все ОК, исправьте формулу.

Чтобы вставить адрес ячейки (ссылку на ячейку) в формулу, не нужно писать его вручную. Проще поставить знак"=", затем щелкнуть левой кнопкой мыши по нужной ячейке или выбрать нужный диапазон ячеек. Excel автоматически вставит ссылку в формулу.

Если формула использует несколько ссылок, то каждая из них Excel дает свой цвет. Это удобно. Пример: напишите формулу "=A1+D1 " в любой ячейке, нажмите Enter, затем дважды щелкните по ячейке. В ячейке вы увидите формулу с разноцветными ссылками, а вокруг ячеек A1 и D1 будут прямоугольники соответствующих цветов. Гораздо легче найти, где ссылка указывает на цвет прямоугольника, чем увидеть буквы столбцов и номера строк. Переместите курсор мыши на один из разноцветных прямоугольников и перетащите левой кнопкой за границу в другое место. Вы увидите, что адреса ячеек в Формуле меняются также -- часто это самый быстрый способ подправить адреса в Формуле, особенно после копирования маркером автозаполнения.

В Excel есть бинарные и унарные операторы. Бинарные операторы работают с 2 значениями. Например, оператор " * " умножает число слева на число справа. Если опустить число слева или справа, Excel отобразит ошибку.

Унарные операторы работают на одном значении. Пример унарных операторов: унарный "+" (ничего не делает), унарный "-" (меняет знак числа справа на противоположный) или знак " % " (слева делит число на 100).

Арифметические операторы

«+» -- сложение (Пример: «=1+1»);

«-» -- вычитание (Пример: «=1-1»);

«*» -- умножение (Пример: «=2*3»);

«/» -- Деление (Пример: «=1/3»);

«^» -- Возведение в степень (Пример: «=2^10»);

«%» -- Процент (Пример: «=3 %» -- преобразуется в 0,03;

«=37*8 %» -- нашли 8 % от 37).

То есть если мы дописываем после числа знак «%», то число делится на 100.

Результатом вычисления любого арифметического выражения будет число.

Логические операторы

">" -- больше;

"<" -- меньше;

">=" -- больше, либо равно;

"<=" -- меньше, либо равно;

"=" -- равно (проверка на равенство);

"<>" -- неравно (проверка на неравенство).

Оператор объединения 2-х строк текста в одну

Оператор «&» (амперсанд) служит для «склеивания» между собой двух текстовых строк. Например, в ячейке A1 текст «мама», в ячейке A2 текст «мыла раму». В A3 пишем формулу «=A1 & A2». В результате в ячейке A3 появится текст «мамамыла раму». Как видим, пробел между двумя строками автоматически не ставится. Чтобы вставить этот пробел, нужно изменить формулу вот так: «=A1 & " " & A2». Точно так же работает оператор "СЦЕПИТЬ", выглядеть формула с его участием будет так: «=Сцепить(A1;" ";A2)».

Операторы ссылок

: (двоеточие). Ставится между ссылками на первую и последнюю ячейку диапазона. Такое сочетание является ссылкой на диапазон (A1:A15);

; (точка с запятой). Объединяет несколько ссылок в одну ссылку (СУММ(A1:A15;B1:B15));

(пробел). Оператор пересечения множеств. Служит для ссылки на общие ячейки двух диапазонов (B7:D7 C6:C8).

Выражения

Выражения в Excel бывают арифметические и логические.

Арифметическое выражение (например, «=2*(2+5)», результат -- 14) в результате дает числовое значение (положительное, отрицательное, дробное число). Логическое выражение (например, «=3>5», результат -- логическое значение «ЛОЖЬ»)в результате может дать лишь 2 значения: «ЛОЖЬ» или «ИСТИНА» (одно число либо больше другого, либо не больше, других вариантов нет).

Абсолютные и относительные ссылки

В ячейках таблицы, помимо текстов и чисел, могут помешаться вычисляемые формулы. В качестве операндов в этих формулах выступают имена ячеек таблицы. Например, в ячейке В3 может находиться формула =A1+B1. Сразу после занесения формулы в ячейку табличный процессор её вычисляет и отражает в ячейке полученное значение. При изменении значений в ячейках - операндах мгновенно происходит пересчёт формул.

В формулах используется два вида адресации: относительная и абсолютная.

1. Относительным адресом называется обозначение ячейки, составленное из номера столбца и номера строки (А1, В5, …).

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

Пример: в ячейке В2 находится формула =2*А4+В1 (обозначим В2>==2*А4+В1). Скопируем её в ячейку В4. Получим В4>==2*А5+В2. Почему имя столбца не изменилось?

Как изменился номер строки?

2. Абсолютным адресом называется обозначение ячейки $F$3 (ячейка «заморожена»).

При копировании формулы абсолютный адрес не изменяется.

Пример: в ячейке В2 находится формула =2*А4+$В$1. Скопируем её в ячейку В4. Получим В4>=2*А5+$В$1.

3. Смешанной ссылкой или адресом называется обозначение $F3 - заморожен «столбец», F$3 - заморожена «строка».

Встроенные функции электронной таблицы

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

В MS Excel имеется очень большая библиотека функций, которые разбиты по категориям.

Таблица определения функций электронной таблицы

Категория	Функция	Назначение
Математические	АВS	Возвращает модуль числа.
	СУММ	Суммирует аргументы.
	ЦЕЛОЕ	Округляет число до ближайшего меньшего целого.
	ОСТАТ	Возвращает остаток от деления.
	КОРЕНЬ	Возвращает значение квадратного корня.
Статистические	СРЗНАЧ	Возвращает среднее арифметическое аргументов
	СЧЕТ	Подсчитывает количество чисел в списке аргументов

Вставка функции в формулы производится командой ВСТАВКА - ФУНКЦИЯ или с помощью соответствующей кнопки на панели .

Пример: =СУММ(А1:В5), =МАКС(А1:А7)-МИН(А1:А7).

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

Для окончательных расчетов используют ограниченный набор функций, наиболее типичным из которых является суммирование функций (SUM). Это лишь одна из функций, для которых использование отдельной кнопки на панели инструментов Стандартная (AutoSum кнопка A).

Другие возможности для окончательных расчетов выбираются индивидуальный способ, с помощью выпадающего списка в строке формул или с помощью мастера функций. Все эти функции относятся к категории - статистические данные. К ним относятся Var (вычисляет дисперсию), MAX (максимальное число в диапазоне) Среднее (среднее арифметическое), SCORE (подсчет клеток с числами в диапазоне). Функции окончательных вычислений часто используются при использовании электронной таблицы Excel в качестве базы данных. Для расширения возможностей Excel использует специальный инструмент под названием надстройка.

Эти средства считаются внешними, по желанию, получить доступ с помощью обычных команд в строке меню (обычно через Службу или в меню Data). Подключать или отключать установленные надстройки, вы можете использовать инструменты ® Add-Ins. Подключение надстройку увеличивает нагрузку на компьютерную систему, поэтому обычно рекомендуется подключать только те дополнения, которые фактически используются.

Построение диаграмм и графиков

Программа Excel график, термин, используемый для обозначения всех видов графического представления числовых данных. Построение графического изображения производится на основе ряда данных. Так как группы клеток, называемые данные в одной строке или столбце. Объект граф представляет собой подключаемый модуль, встроенный на одном из листов книги. Для построения диаграммы с помощью мастера диаграмм, вызывается при нажатии на кнопку на Мастер диаграмм на стандартной панели инструментов. На первом шаге мастера выбирают форму диаграммы. Доступные формы перечислены на стандартного типа вкладок. Справа от выбранного типа указано Несколько вариантов отчетов (палитры). Второй шаг мастера необходимо выбрать данные, по которым строится график. Третий шаг мастера (после нажатия на кнопку Далее), чтобы выбрать проектную схему, которая определяет имя диаграммы, отображение разметки осей, линий сетки. В последнем шаге мастера (после нажатия кнопки Далее) указывает, следует ли использовать новый рабочий лист или один из диаграммы имеющихся в наличии для размещения. Чтобы открыть диалоговое окно для форматирования элемента диаграммы можно через меню Формат (для выбранного элемента) или через контекстное меню (команда Format). Чтобы удалить таблицу с помощью клавиши Delete .

2.2 Алгоритмы решения задач линейного программирования с помощью Microsoft Excel

Для того чтобы решить задачу ЛП в табличном процессоре Microsoft Excel, необходимо выполнить следующие действия:

1. Ввести условие задачи:

a) создать экранную форму для ввода условия задачи:

· переменных,

· целевой функции (ЦФ),

· ограничений,

· граничных условий;

b) ввести исходные данные в экранную форму:

· коэффициенты ЦФ,

· коэффициенты при переменных в ограничениях,

· правые части ограничений;

c) ввести зависимости из математической модели в экранную форму:

· формулу для расчета ЦФ,

· формулы для расчета значений левых частей ограничений;

d) задать ЦФ (в окне "Поиск решения"):

· целевую ячейку,

· направление оптимизации ЦФ;

e) ввести ограничения и граничные условия (в окне "Поиск решения"):

· ячейки со значениями переменных,

· граничные условия для допустимых значений переменных,

· соотношения между правыми и левыми частями ограничений.

2. Решить задачу:

a) установить параметры решения задачи (в окне "Поиск решения");

b) запустить задачу на решение (в окне "Поиск решения");

c) выбрать формат вывода решения (в окне "Результаты поиска решения").

Рассмотрим подробно использование MS Excel на примере решения следующей задачи.

Задача.

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

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

Цех	Необходимый фонд рабочего времени чел.-ч/т	Общий фонд рабочего времени чел.-ч. в месяц
	"Малышка"	"Вишня"
А. Производство	10	4	1000
В. Добавка приправ	3	2	360
С. Упаковка	2	5	600

Доход от производства 1 т. "Малышка" составляет 150 тыс.руб., а от производства "Вишня" - 75 тыс.руб. На настоящий момент нет никаких ограничений на возможные объемы продаж. Имеется возможность продать всю произведенную продукцию.

Требуется:

а) Сформулировать модель линейного программирования, максимизирующую общий доход фабрики за месяц.

б) Решить ее c помощью MS Excel.

Формальная постановка данной задачи имеет вид:

150х₁+75х₂> max

Ввод исходных данных

Создание экранной формы и ввод исходных данных

Экранная форма для решения в MS Excel представлена на рисунке 1.

Рис. 6 Введенные данные

В экранной форме на рис.1 каждой переменной и каждому коэффициенту задачи поставлена в соответствие конкретная ячейка на листе Excel. Имя ячейки состоит из буквы, обозначающей столбец, и цифры, обозначающей строку, на пересечении которых находится объект задачи ЛП. Так, например, переменным данной задачи соответствуют ячейки B4 (х₁), C4 (х₂), коэффициентам ЦФ соответствуют ячейки B6 (150), C6 (75), правым частям ограничений соответствуют ячейки D18(1000), D19 (360), D20 (600) и т.д.

Ввод зависимостей из формальной постановки задачи в экранную форму

Для ввода зависимостей определяющих выражение для целевой функции и ограничений используется функция MS Excel СУММПРОИЗВ, которая вычисляет сумму попарных произведений двух или более массивов.

Одним из самых простых способов определения функций в MS Excel является использование режима "Вставка функций", который можно вызвать из меню "Вставка" или при нажатии кнопки "f_x" (рис. 2) на стандартной панели инструментов.

Рис. 7 Окно Вставки функции

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

· курсор в поле D6;

· нажав кнопку "", вызовите окно"Мастер функций - шаг 1 из 2";

· выберите в окне "Категория" категорию "Математические";

· в окне "Функция" выберите функцию СУММПРОИЗВ (рис. 3);

Рис. 8 Окно Мастера функции

В появившемся окне "СУММПРОИЗВ" в строку "Массив 1" введите выражение $B$4:$C$4, а в строку "Массив 2" - выражение B6:C6 (рис. 4);

Рис. 9 Ввод аргументов функции

Левые части ограничений задачи представляют собой сумму произведений каждой из ячеек, отведенных для значений переменных задачи (B3, C3), на соответствующую ячейку, отведенную для коэффициентов конкретного ограничения (B13, C13 - 1-е ограничение; B14, С14 - 2-е ограничение и B15, С15 - 3-е ограничение). Формулы, соответствующие левым частям ограничений, представлены в табл.1.

Таблица 1

Формулы, описывающие ограничения модели (1)

Левая часть ограничения	Формула Excel
10х1+4х2 или В3*В13+С3*С13	=СУММПРОИЗВ(B4:C4;B13:C13)
3х1+2х2 или В3*В14+С3*С14	=СУММПРОИЗВ(B4:C4;B14:C14)
2х1+5х2 или В3*В15+С3*С15	=СУММПРОИЗВ(B4:C4;B15:C15)

После ввода всех данных мы получим следующее:

...