Решение одноиндексных задач линейного программирования с использование MICROSOFT EXCEL

МИНИСТЕРСТВО ОБРАЗОВАНИЯ  И НАУКИ РОССИЙСКОЙ ФЕДЕРАЦИИ

 

ФЕДЕРАЛЬНОЕ ГОСУДАРСТВЕННОЕ  БЮДЖЕТНОЕ

 ОБРАЗОВАТЕЛЬНОЕ УЧРЕЖДЕНИЕ

ВЫСШЕГО ПРОФЕССИОНАЛЬНОГО  ОБРАЗОВАНИЯ

 

«БРАТСКИЙ ГОСУДАРСТВЕННЫЙ  УНИВЕРСИТЕТ»

 

ФАКУЛЬТЕТ ЭКОНОМИКИ И  УПРАВЛЕНИЯ

 

Кафедра экономики  и технологии бизнеса

 

                                            Лабораторная работа №1

                по дисциплине

                   «Экономико-математические методы»                                                               

 

 

 

РЕШЕНИЕ ОДНОИНДЕКСНЫХ ЗАДАЧ  ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ С ИСПОЛЬЗОВАНИЕ  MICROSOFT EXCEL

Вариант №10

 

 

 

 

Выполнил 

ст. гр. Р-09:           Н.В. Лисовская

                                                                                          

 

 

Проверил

к.э.н., доцент каф. ЭиТБ:           С.В. Либеровская

 

 

 

 

Братск 2013

Содержание

 

Введение                                                                                                         3

Теоретическая часть                                                                                      4

Практическая часть                                                                                       6

Заключение                                                                                                  11

Список использованных источников                                                        12

 

Введение

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

Линейное программирование является частным случаем математического программирования. Одновременно оно — основа нескольких методов решения задач целочисленного и нелинейного программирования. Одним из обобщений линейного программирования является дробно-линейное программирование.

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

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

Цель работы: приобретение навыков решения одноиндексных задач линейного программирования в табличном редакторе Microsoft Exсel.

 

 

Теоретическая часть

 

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

К числу задач линейного  программирования можно отнести  задачи:

• рационального использования  сырья и материалов;

• задачи оптимального раскроя;

• оптимизации производственной программы предприятий;

• оптимального размещения и концентрации производства;

• составления оптимального плана перевозок, работы транспорта;

• управления производственными  запасами;

• и многие другие, принадлежащие  сфере оптимального планирования.

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

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

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

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

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

Характерные черты для  ЛП следующие:

а) показатель оптимальности L(X) представляет собой линейную функцию  от элементов решения X=(х1, х2…хn);

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

Общая форма записи модели задачи ЛП:

Целевая функция (ЦФ)

L(X)=c1х1 +с2х2 +…+сnхn        max(min)

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

а11х1+а12х2+…+а1nxn ≤ (≥, =) b1

а21х1+а22х2+…+а2nxn ≤ (≥, =) b2

…

 

аm1х1+аm2х2+…+аmnxn ≤ (≥, =) bm

 

                  х1, х2,…хk ≥ 0 (k ≤ n)

 

При описании реальной ситуации с помощью линейной модели следует  проверять наличие у модели таких  свойств как пропорциональность и аддитивность.

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

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

Допустимое решение –  это совокупность чисел (план) Х = (х1, х2,…хn), удовлетворяющих ограничениям задачи.

Оптимальное решение –  это план, при котором ЦФ принимает  свое максимальное (минимальное) значение.

 

 

Практическая  часть

 

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

Характерные задачи линейного  программирования:

• Показатель оптимальности L(X) представляет собой линейную функцию от элементов решения X=(;
• Ограничительные условия, налагаемые на возможные решения, имеют вид линейных равенств или неравенств.

Найдем решение для  следующей одноиндексной задачи линейного программирования:

 

L(X) = 

 

 

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

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

В редакторе Microsoft Excel создаем экранную форму и вносим в нее исходные данные. Каждой переменной и каждому коэффициенту выделяем конкретную ячейку. Размещаем в экранной форме коэффициенты ЦФ, коэффициенты при переменных в ограничениях, правые части ограничений. Так коэффициенты ЦФ размещены в ячейках В5-F5. Коэффициенты при ограничениях размещены в ячейках В9-F9, В10- F10, В11- F11 и В12- F12. Правая часть ограничений представлена в ячейках Н9-Р12.

 

 

Рисунок 1 – Экранная форма  задачи (курсор на ячейке G5)

 

2. Решение задачи

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

1.Формула для ЦФ. В ячейку G5, в которой будет отображаться значение ЦФ, вводим формулу, по которой это значение будет рассчитано. Согласно (Рисунок 1) значение ЦФ определяется выражением

Используя обозначения соответствующих  ячеек в Excel, формулу для расчета ЦФ можно записать как сумму произведений каждой из ячеек, отведенных для значений переменных задачи (В2, С2, D2, E2, F2), на соответствующую ячейку, отведенную для коэффициентов ЦФ (B5, C5, D5, E5, F5), то есть B5*B2+C5*C2+D5*D2+E5*E2+F5*F2.

Чтобы задать данную формулу необходимо в ячейку F5 ввести следующее выражение и нажать клавишу ''Enter'':=СУММПРОИЗВ (В$2:F$2;B5:F5).

Символ $ перед номером  строки 2 означает, что при копировании этой формулы в другие места листа Excel номер строки 2 не изменится.

2.Формулы для левых частей ограничений. Левые части ограничений задачи представляют собой сумму произведений каждой из ячеек, отведенных для значений переменных задачи (В2, С2, D2, E2, F2), на соответствующую ячейку, отведенную для коэффициентов конкретного ограничения (В9, С9, D9, E9, F9) - 1-е ограничение; (В10, С10, D10, E10, F10) – 2-е ограничение; (В11, С11, D11, E11, F11) – 3-е ограничение и (В12, С12, D12, E12, F12)- 4-е ограничение. Формулы, соответствующие левым частям ограничений, представлены  в табл.1.

 

 

Левая часть ограничения	Формула Ехсеl
или B9*B2+C9*C2+D9*D2+E9*E2+F9*F2	=СУММПРОИЗВ (В$2:F$2;B9:F9)
или B10*B2+C10*C2+D10*D2+E10*E2+F10*F2	=СУММПРОИЗВ (В$2:F$2;B10:F10)
или B11*B2+C11*C2+D11*D2+E11*E2+F11*F2	=СУММПРОИЗВ (В$2:F$2;B11:F11)
или B12*B2+C12*C2+D12*D2+E12*E2+F12*F2	=СУММПРОИЗВ (В$2:F$2;B12:F12)

 

Таблица 1. Формулы, описывающие ограничения модели

 

После того как формулы  были введены, на экране в полях G9 B G11 появилось 0 (нулевое значение), в поле G10 появилось значение 890, а в поле G12 появилось значение 32458,82353.

 

2.2. Задание ЦФ. Дальнейшие действия производятся в окне «Поиск решения», которое вызывается из меню «Сервис». Перед тем как открыть окно «Поиск решения» курсор поставлен в поле G5.

 

1.4. Ввод ограничений и граничных условий.

1. Задание ячеек и переменных. В окно «Поиск решения» в поле «Изменяя ячейки» вписываем адреса $B$1:$F$1.
2. Задание граничных условий для допустимых значений переменных. В данном случае на значения переменных накладывается только граничное условие неотрицательности, то есть их нижняя граница должна быть равна нулю.

• Нажали кнопку «Добавить», после чего появилось окно «Добавление ограничения».
• В поле «Ссылка на ячейку» ввели адрес ячеек переменных $B$1:$F$1.
• В поле «Ограничение» ввели адреса ячеек нижней границы значений переменных, то есть $B$2:$F$2.

3) задание знаков ограничений.  Знаки  ≥, ≤, = задаем следующим  образом:

• Нажимаем кнопку «Добавить» в окне «Добавление ограничения».
• В поле «Ссылка на ячейку» вводим адрес ячейки левой части конкретного ограничения, например $G$10.
• В соответствии с условием задачи выбираем в поле знака необходимый знак, например ≥.
• В поле «Ограничение» вводим адрес ячейки правой части рассматриваемого ограничения, например $I$10.
• Аналогично вводим ограничения: $G$11 ≤ $I$11, $G$12 = $I$12, $G$13 ≥ $I$13.

Подтверждаем ввод всех перечисленных  выше условий нажатием кнопки ОК.

 

 

2.3. Решение задачи

Запуск задачи на решение  производится из окна «Поиск решений» путем нажатия кнопки «Выполнить».

 

Имя	X1	X2	X3	X4	X5
Значения	0	523,5294	0	0	0
Нижн.гр.	0	0	0	0	0	ЦФ
						Значение	Направл.
Коэф. ЦФ	10	0	40	13	56	0	min
ОГРАНИЧЕНИЯ
Вид						левая часть	Знак	правая часть
Огран. 1	7	0	16	5	25	0	≤	600
Огран.2	8	1,7	0	-0,5	4,7	890	=	890
Огран. 3	6	0	4	-7	6,3	0	≤	270
Огран. 4	84	62	80	0	14	32458,82353	≥	2300