Справочная информация
ДокументыЗаконыИзвещенияУтверждения документовДоговораЗапросы предложенийТехнические заданияПланы развитияДокументоведениеАналитикаМероприятияКонкурсыИтогиАдминистрации городовПриказыКонтрактыВыполнение работПротоколы рассмотрения заявокАукционыПроектыПротоколыБюджетные организацииМуниципалитетыРайоныОбразованияПрограммыОтчетыпо упоминаниямДокументная базаЦенные бумагиПоложенияФинансовые документыПостановленияРубрикатор по темамФинансыгорода Российской Федерациирегионыпо точным датамРегламентыТерминыНаучная терминологияФинансоваяЭкономическаяВремяДаты2015 год2016 годДокументы в финансовой сферев инвестиционной
Задача 1
Задача
распределения ресурсов.
Если
финансы, оборудование, сырье и даже
людей полагать ресурсами, то значительное
число задач в экономике можно рассматривать
как задачи распределения ресурсов.
Достаточно часто математической моделью
таких задач является задача линейного
программирования.
Например:
Требуется
определить, в каком количестве надо
выпускать продукцию четырех типов
Прод1, Прод2, Прод3, Прод4, для изготовления
которой требуются ресурсы трех видов:
трудовые, сырье, финансы. Количество
ресурса каждого вида, необходимое для
выпуска единицы продукции данного типа,
называется нормой расхода. Нормы расхода,
а также прибыль, получаемая от реализации
единицы каждого типа продукции, приведена
ниже.Составим математическую модель,
для чего введем следущие обозначения:
x
j
—
количество
выпускаемой продукции j-го
типа, j=1,4
;
b
i
—
количество располагаемого ресурса
i-го
вида, i=1,3
;
a
ij
— норма расхода i-го
ресурса
для выпуска единицы продукции
j-го
типа;
c
j
— прибыль, получаемая от реализации
единицы продукции j-го
типа.
Теперь
приступим к составлению модели.
Для
выпуска единицы Прод1 требуется 6 единиц
сырья, значит, для выпуска всей продукции
Прод1 требуется 6 х
1
единиц сырья, где х
1
—
количество выпускаемой продукции
Прод1. С учетом того, что для других видов
продукции зависимости аналогичны,
ограничение по сырью будет иметь вид:
6х
1
+5х
2
+4х
3
В
этом ограничении левая часть равна
величине потребного
ресурса, а правая показывает количество
имеющегося
ресурса.
Аналогично можно составить ограничения
для остальных ресурсов и написать
зависимость для целевой функции. Тогда
математическая модель задачи будет
иметь вид:
F=60x
1
+70x
2
+120x
3
+130x
4
—>
max
x
1
+x
2
+x
3
+x
4
6x
1
+5x
2
+4x
3
+3x
4
4x
1
+6x
2
+10x
3
+13x
4
x
j
>=0;
j=1,4
6 Решение задач линейного программирования с помощью надстройки «Поиск решения» в Microsoft Excel
«Поиск решения» предназначен для решения задач
математического программирования. Если задача разрешима, то в общем случае будет
найдено приближенное решение. Для линейной задачи, если она разрешима, всегда
можно получить точное решение с использованием симплекс-метода. Для линейных
задач с целочисленными переменными «Поиск решения» также использует метод
ветвей и границ в сочетании с симплекс-методом .
Надстройка «Поиск решения» находится в выпадающем
меню «Сервис». Если она отсутствует, следует сначала в том же выпадающем меню
выбрать пункт «Надстройки», и, найдя «Поиск решения» в списке надстроек,
отметить его флажком.
Слайды и текст этой презентации
Слайд 1Решение задач линейного программирования
в MS Excel
Слайд 2Общая задача линейного программирования решается симплексным методомСимплекс
(лат. simplex — простой) – простейший выпуклый многогранник
в n-мерном пространстве с n+1 вершиной (например, тетраэдр в 3-мерном пространстве)
Слайд 3Если задача линейного программирования имеет оптимальное решение,
то оно соответствует хотя бы одной угловой
точке многогранника решений (и совпадает с одним из допустимых базисных решений системы ограничений)
На рисунке: оптимальное решение находится в одной из вершин многоугольника решений А, В, С, D
Слайд 4Геометрический смысл симплексного метода состоит в последовательном
переходе от одной вершины многогранника ограничений к
соседней, в которой целевая функция принимает лучшее (по крайней мере, не худшее) значение
Слайд 5Впервые симплексный метод был предложен американским ученым
Дж. Данцигом в 1949 г.Джордж Бернард Данциг
(1914-2005) – американский математик, разработал симплексный алгоритм, считается основоположником методов линейного программирования
Леонид Витальевич Канторович (1912-1986) – советский математик и экономист, лауреат Нобелевской премии по экономике 1975 года «за вклад в теорию оптимального распределения ресурсов». Один из создателей линейного программирования
Идеи симплексного метода были разработаны в 1939 г. российским ученым Л.В.Канторовичем
Слайд 6Симплексный метод позволяет решить любую задачу линейного
программированияВ настоящее время он используется для компьютерных
расчетовРассмотрим решение задачи линейного программирования в MS Excel
Слайд 8Сначала надстройку Поиск решения необходимо подключить (до
первого использования)В MS Excel 2003:
Сервис /
Надстройки /
Поиск решения / OK
После этого команда Поиск решения включена в меню Сервис
Слайд 9В MS Excel 2007:
1) Кнопка Office
(левый верхний угол окна программы)
2) Кнопка Параметры
Excel (внизу окна меню)3) Надстройки
1
2
3
Слайд 10В MS Excel 2007:
4) Кнопка Перейти
появится во вкладке Данные
появится во вкладке Данные
переменных(пока они пусты)
в ячейку А8
Слайд 18Решим в MS Excel задачу линейного программирования3.
левые части ограничений в системеВ ячейках В11:В13 введем правые части ограничений системы
Слайд 19Решим в MS Excel задачу линейного программирования3.
левые части ограничений в системе
Первое ограничение
Слайд 20Решим в MS Excel задачу линейного программирования3.
левые части ограничений в системе
Второе ограничение
Слайд 21Решим в MS Excel задачу линейного программирования3.
левые части ограничений в системе
Третье ограничение
Слайд 22Решим в MS Excel задачу линейного программирования4.
Вызовем окно диалога Поиск решенияПри этом удобно,
если активной ячейкой является ячейка со значением целевой функции
Слайд 23Решим в MS Excel задачу линейного программированияУстанавливаем
целевую ячейку А8 (там где вычисляется значение
целевой функции)Указываем направление оптимизации – минимизация (по условию)В поле Изменяя ячейки указываем ячейки переменных В2:В6
ограничения4) Нажимаем кнопку Добавить Появится окно Добавление
ограничения
ограничения5) Неотрицательность переменных: Нажать кнопку Добавить6) Остальные
ограничения:Нажать OK
нажать кнопку Выполнить
Решение транспортной задачи с помощью средства Поиск решения
Фирма
имеет четыре фабрики: А, В, С,
D и пять центров распределения
ее товаров: №1, №2, №3, №4, №5.
Производственные
возможности фабрик соответственно
составляют:
А
– 200, В – 150, С – 225,
D –
175 единиц продукции ежедневно.
Потребности
центров распределения соответственно
составляют:
№1
– 100, №2 – 200, №3 – 50, №4 – 250, №5 – 150 единиц
продукции ежедневно.
Хранение
на фабрике единицы продукции, не
поставленной в центр распределения,
составляет $0,75
в день.
Штраф
за просроченную поставку единицы
продукции, заказанной потребителем в
центре распределения, но там не
находящейся, равен $2,5
в день.
Стоимость
перевозки единицы продукции с фабрик
в пункты распределения представлена в
таблице:
Спланировать
перевозки так, чтобы минимизировать
суммарные транспортные расходы.
Модель
рассматриваемой задачи сбалансирована
(суммарный объем произведенной продукции
равен суммарному объему потребностей
в ней), значит не нужно учитывать издержки,
связанные как со складированием, так и
с недопоставками продукции. В противном
случае в модель следует ввести:
В
случае перепроизводства – фиктивный
пункт распределения, стоимость перевозок
единицы продукции, в который полагается
равной стоимости складирования, а
объемы перевозок – объемам складирования
излишков продукции на фабриках.
В
случае дефицита – фиктивную фабрику,
стоимость перевозок единицы продукции
с которой полагается равной стоимости
штрафов за недопоставку продукции, а
объемы перевозок – объемам недопоставок
продукции в пункты распределения.
x
ij
– объем перевозок с i-й
фабрики в j-й
центр распределения.
c
ij
– стоимость перевозки единицы продукции
с i-й
фабрики
в j-й
центр
распределения.
а
i
– объем
производства на i-й
фабрике.
в
j
– спрос в j-м
центре распределения.
Требуется
минимизировать суммарные транспортные
расходы, т.е.
Ограничения:
x
ij
0 , i
, j
Механизм решения задачи в Excel
с использованием средства
Поиск
решения
В
ячейки А1:Е4 введите стоимости перевозок.
А6:Е9
– отведите под значения неизвестных
(объемы перевозок).
В
ячейки G6:G9 введите объемы производства
на фабриках.
В
А11:Е11 – потребность в продукции в
пунктах распределения.
В ячейку
F10 – введите целевую функцию
В А10:Е10
–введите формулы, определяющие объем
продукции, ввозимой в центры распределения
В F6: F9 –
формулы, вычисляющие объем продукции,
вывозимой с фабрик.
|
СУММ(A6:E6) |
|||||||
|
СУММ(A7:E7) |
|||||||
|
СУММ(A8:E8) |
|||||||
|
СУММ(A9:E9) |
|||||||
|
СУММ(A6:A9) |
СУММ(B6:B9) |
СУММ(C6:C9) |
СУММ(D6:D9) |
СУММ(E6:E9) |
СУММПРОИЗВ(A1:E4;A6:E9) |
||
Сервис
Поиск
решения
В
окне диалога Поиск решения:Установить
целевую ячейку $F$10Равной
мин
имальному
значениюИзменяя
ячейки:
$А$6:$E$9Ограничения:$А$10:$E$10=$A$11:$E$11$А$6:$E$9>=0$F$6:$F$9=$G$6:$G$9
Щелкните
на кнопке Параметры…
и
установите флажок Линейная
модель
Нажмите
кнопку Выполнить
Оптимальное
решение транспортной задачи будет
отражено в диапазоне А6:Е9
Решите
транспортную задачу самостоятельно,
используя выше описанный механизм.
|
Excel Инструкция по использованию microsoft Excel для решения задач лп 5 3 Одноиндексные задачи лп 6 > 3 Ввод исходных данных 6 > 3 Решение задачи 13Некоторые понятия линейного программированияДокумент Мы приведем решение |
1.4. ПРИМЕРНЫЕ ВОПРОСЫ НА ЗАЩИТЕ РАБОТЫ
1. Каковы основные этапы решения задач ЛП в MS Excel?
2. Каков вид и способы задания формул для целевой ячейки и ячеек левых частей ограничений?
3. В чем смысл использования символа $ в формулах MS Excel?
4. В чем различие использования в формулах MS Excel символов ; и ?
5. Почему при вводе формул в ячейки ЦФ и левых частей ограничений в них отображаются нулевые значения?
6. Каким образом в MS Excel задается направление оптимизации ЦФ?
7. Какие ячейки экранной формы выполняют иллюстративную функцию, а какие необходимы для решения задачи?
8. Как наглядно отобразить в экранной форме ячейки, используемые в конкретной формуле, с целью проверки ее правильности?
9. Поясните общий порядок работы с окном «Поиск решения».
10. Каким образом можно изменять, добавлять, удалять ограничения в окне «Поиск решения»?
11. Какие сообщения выдаются в MS Excel в случаях: успешного решения задачи ЛП; несовместности системы ограничений задачи; неограниченности ЦФ?
12. Объясните смысл параметров, задаваемых в окне «Параметры поиска решения».
13. Каковы особенности решения в MS Excel целочисленных задач ЛП?
14. Каковы особенности решения в MS Excel двухиндексных задач ЛП?
15. Каковы особенности решения в MS Excel задач ЛП с булевыми переменными?
6.1 Работа с диалоговыми окнами «Поиск решения» и «Добавление ограничения»
Диалоговое окно «Поиска решения» представлено на рисунке
28.
Рисунок 28 — Диалоговое окно «Поиск решения»
В качестве целевой ячейки указывают адрес ячейки
электронной таблицы, в которой находится формула целевой функции, содержащая
ссылки на изменяемые ячейки (ячейки, в которых будут находиться значения
переменных). По умолчанию в поле «Установить целевую ячейку» находится адрес
той ячейки, в которой стоял курсор в момент обращения к «Поиску».
С помощью переключателя «Равной» можно выбрать
направление экстремизации, т.е. определить, будет задача решаться на максимум
или на минимум. Если установить целевую ячейку равной некоторому фиксированному
значению, то «Поиск решения» дает возможность решить систему уравнений и
неравенств. По умолчанию задача решается на максимум.
В поле «Изменяя ячейки» указывается одна или
диапазон изменяемых ячеек (переменных). Их еще называют влияющими ячейками. Они
должны быть расположены на активном листе таблицы. При решении линейных задач
во влияющих ячейках можно устанавливать любые исходные значения, но только
числовые.
При нажатии кнопки «Предположить» «Поиск решения» обычно
предлагает выбрать в качестве влияющих ячейки, на которые имеются ссылки в
целевой ячейке. Однако лучше самостоятельно указать в поле «Изменяя ячейки»
нужный диапазон. Если не указать влияющие ячейки, то при нажатии кнопки
«Выполнить» программа выдаст сообщение о том, что задача для поиска решения не
поставлена.
Перечисленные действия (установление целевой ячейки,
содержащей формулу, и влияющих ячеек) являются обязательными и, вообще говоря,
достаточными для использования «Поиска решения». Кроме того, задача, решаемая с
помощью «Поиска решения», обычно содержит систему ограничений, для ввода
которой используется окно «Ограничения». На каждую задачу может быть введено до
100 ограничений.
При первоначальной постановке задачи здесь доступна
только кнопка «Добавить». При попытке нажать кнопки «Изменить» или «Удалить»
будут выданы соответствующие сообщения об ошибках (отсутствии ограничений).
Нажатием на кнопку «Добавить» вызывается диалоговое окно «Добавление
ограничения», представленное на рисунке 29.
Рисунок 29 — Диалоговое окно «Добавление ограничения»
Центральную часть этого окна занимает поле с
раскрывающимся списком, в котором перечислены операторы, доступные при задании
ограничений. Они приведены в таблице 25.
По умолчанию предполагается, что задача приведена к
стандартной форме, т.е. если она ставится на максимум, то в ограничениях
предлагается использовать знак «>=», а если на минимум, то «<=». При
постановке задачи в смешанной форме эти знаки следует изменить.
Таблица 25 – Операторы, доступные при
задании ограничений
|
Оператор |
Описание |
|
<= |
меньше или равно |
|
>= |
больше или равно |
|
= |
равно |
|
цел |
целое |
|
двоич |
равно 0 или 1 |
Слева и справа от поля со списком этих операторов расположены
поля, в которых указываются соответственно левая и правая части ограничений.
При этом в левой части обязательно должна находиться ссылка на ячейку или
диапазон ячеек. В правой части могут находиться ссылка на ячейку или диапазон,
число или формула. При выборе операторов «цел» или «двоич» в правой части окна
появляются соответственно слова «целое» или «двоичное», и она становится
недоступной. Если в обеих частях введены диапазоны, число ячеек в них должно
совпадать, чтобы они сравнивались попарно.
Бизнес и финансы
БанкиБогатство и благосостояниеКоррупция(Преступность)МаркетингМенеджментИнвестицииЦенные бумагиУправлениеОткрытые акционерные обществаПроектыДокументыЦенные бумаги — контрольЦенные бумаги — оценкиОблигацииДолгиВалютаНедвижимость(Аренда)ПрофессииРаботаТорговляУслугиФинансыСтрахованиеБюджетФинансовые услугиКредитыКомпанииГосударственные предприятияЭкономикаМакроэкономикаМикроэкономикаНалогиАудитМеталлургияНефтьСельское хозяйствоЭнергетикаАрхитектураИнтерьерПолы и перекрытияПроцесс строительстваСтроительные материалыТеплоизоляцияЭкстерьерОрганизация и управление производством
Задача планирования производства красок
Для
производства красок для
наружных
и внутренних
работ
используют
два исходных продукта А и В. Максимально
возможные суточные запасы этих продуктов
составляют 6 и 8 тонн, соответственно.
Суточный
спрос на краску для
внутренних работ
никогда
не превышает спроса на краску для
наружных работ
более
чем на 1т.
Спрос
на краску для
внутренних работ
не
превышает 2т. в сутки.
Оптовые
цены одной тонны красок равны: 3000 руб.
для краски для
наружных работ
и
2000 руб. для краски для
внутренних работ
.
Какое
количество краски каждого вида следует
производить, чтобы доход от реализации
был максимальным?
Расходы
продуктов А и В на 1т. приведены в таблице:
|
исходный |
расход |
максимально |
|
|
для внутренних |
для наружных |
||
х 1
— суточный объем
производства краски для
внутренних работ
х 2
— суточный объем
производства краски для
наружных работ
f -суммарная
суточная прибыль от производства обоих
видов красок (целевая функция)
f
= 3000х 1 +2000х 2
Определить
при каких допустимых значениях х 1
и х 2
значение f — максимальное
Ограничения:
Решение
задачи в Excel
|
Переменные |
|||
|
Целевая |
3000*А3+2000*В3 |
||
|
Ограничения |
|||
Выполните:
Cервис, Поиск решения
Целевая
ячейка С4
Установить: М
аксимальному
значению
Изменяемые
ячейки: А3:В3
Ограничения:
После
ввода данных нажмите кнопку Выполнить
Полученное
решение:
|
Переменные |
|||
|
Целевая |
|||
|
Ограничения: |
|||
Вывод:
оптимальным является производство 3,3
т. краски для наружных работ и 1,3 т. краски
для внутренних работ в сутки. Этот объем
принесет прибыль 12,7 тыс. руб.
