Особенности реализации в excel симплекс метода. Решение ЗЛП симплекс-методом в Excel

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

Задача . Решить задачу табличным симплекс-методом .

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

Порядок выполнения работы :

I. Проверка выполнения условий, необходимых для решения задачи табличным симплекс-методом в чистом виде.

II. Оформление исходных данных.

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

Шапка таблицы: столбец базисных переменных (B ), столбец свободных членов, имеющиеся переменные.

Следующая строка таблицы соответствует первому ограничению. Базисная переменная , найденная в первом ограничении, свободный член, коэффициенты при переменных соответствующего ограничения. Аналогичным образом заполняются 2 и 3 строки.

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

Рис. 26 . Исходная симплекс таблица.

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

Рис. 27 . Значение целевой функции и начальный опорный план.

III. Нахождение оптимального плана и оптимального значения целевой функции.

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

Рис. 28 . Выбор ведущего столбца.

Рис. 29 . Составление отношений.

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

Рис. 30 . Результат отношений.

Выберите наименьшее из отношений. Строку, в которой получился наименьший результат, назовите ведущей (рис. 31). Данная строка показывает, какую переменную необходимо исключить из базиса.

Рис. 31 . Выбор ведущей строки.

На пересечении ведущей строки и ведущего столбца получается ведущий элемент (рис. 32).

Рис. 32 . Ведущий элемент.

Рис. 33 . Новый базис.

Для получения 1 в ячейке С13 необходимо каждый элемент ведущей строки поделить на ведущий элемент.

В ячейку С13 запишите формулу = С5/2 (рис 34), нажмите Enter.

Рис. 34 . Получение 1 в ячейке С13.
Растяните формулу (рис. 35).

Рис. 35 . Первая строка второй симплексной таблицы.
Затем получите нуль в ячейке С14.

Для этого во второй симплексной таблице 1 (ячейка С13) умножьте на элемент предыдущей таблицы, соответствующий элементу ячейки С14, взятый с противоположным знаком и сложите с этим же элементом.

Так как элемент, соответствующий элементу ячейки С14 равен 1 (ячейка С6), то это означает, что все элементы первой строки второй симплексной таблицы умножаются на (-1) и складывается с соответствующими элементами первой симплексной ьаблицы. Запишите в ячейку С14 формулу =C13*(-1)+C6 (рис. 36).

Рис. 36 . Элемент С14 второй симплексной таблицы.
Аналогичным образом получите остальные элементы базисного столбца (рис. 37 и рис. 38).

Рис. 37 . Элемент С15 второй симплексной таблицы.

Рис. 38 . Элемент С16 второй симплексной таблицы.

Растяните формулы базисного столбца по строкам, получите вторую симплексную таблицу (рис. 39).

Рис. 39 . Первая и вторая симплексные таблицы.

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

Рис. 40 . Значение целевой функции и опорного плана второй симплексной таблицы.

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

Рис. 41 . Первая, вторая и третья симплексные таблицы.

Задание. Воспользуйтесь материалами лабораторной работы №3. Выполните проверку, используя программу MathCad.

1. Преобразовываем неравенства в равенства

2. Находим начальное допустимое базисное решение

3. На основе условия оптимальности определяется вводимая переменная. Если вводимых переменных нет, то процесс закончен.

4. На основе условия допустимости выбираем исключаемая переменная

5. Вычисляем элементы новой ведущей строки

новая ведущая строка = текущая строка/ведущий элемент

6. Вычисляем элементы остальных строк, включая z-строку

новая строка = текущая строка – ее коэффициенты в ведущем столбце * новую ведущую строку

Переходим к шагу 3.

Для удобства записи итерационного процесса все значения записываем в Симплекс-таблицу.

2. Пример решения задачи лп с использованием пакета ms excel

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

Для нахождения решения в подобных моделях, можно использовать средство MS EXCEL – ПОИСК РЕШЕНИЯ.

Рассмотрим, как составить модель линейного программирования и найти ее решение на примере.

2.1. Постановка задачи

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

2.2. Построение математической модели

Обозначим через х 1 и х 2 количество единиц деталей видов А и Б, планируемое к выпуску. Тогда время обработки х 1 деталей вида А на первом станке составляет 1* х 1 ; х 2 деталей вида Б соответственно 2*х 2 . Суммарное время работы станка I для изготовления планируемого количества деталей равно х 1 +2*х 2 , оно ограничено 16 часами работы этого станка в течение одного цикла производства. Поэтому должно выполняться неравенство:

х 1 +2*х 2 <=16;

Аналогично для станков II и III получаем неравенства соответственно:

х 1 + х 2 <=10;

3*х 1 + х 2 <=24;

Кроме того, по смыслу определения веденных величин х 1 и х 2 , должны выполняться условия: х 1 >=0; х 2 >=0;

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

Любое решение (х 1 ; х 2) системы ограничений называется планом выпуска продукции или допустимым планом задачи.

Прибыль от реализации х 1 единиц деталей вида А равна 4 . х 1 , а прибыль от реализации х 2 единиц деталей вида Б равна 2х 2. Суммарная прибыль от реализации продукции, выпущенной согласно плану (х 1 ; х 2) равна:

F (х 1 ; х 2 )=4х 1 +2х 2 (тыс. руб).

Линейная функция F (х 1 ; х 2 ) называется целевой функцией задачи.

По условию задачи требуется найти такой план (х 1 ; х 2) при котором прибыль была бы максимальной.

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

F (х 1 ; х 2 )=4х 1 +2х 2 → max

Оптимизационные модели используются, чтобы найти ответы на вопросы типа:

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

Скачать заметку в формате или , примеры в формате

Целью оптимизации всегда является «максимизация» или «минимизация». Самая распространенная и понятная форма математической оптимизации - это линейное программирование, секретная разработка советских инженеров конца 1930-х годов, ставшая популярной в ходе Второй мировой войны. Кстати, слово «программирование» в данном словосочетании является пережитком военной терминологии того времени и не имеет ничего общего с компьютерным программированием.

Начнем с любимого примера экономистов - пушек и масла. Идет 1941-й год, вы – хозяин французской молочной фермы. Днем вы доите коров и производите сливочное масло, ночью – собираете автоматы. Ваша цель – максимальная прибыль, чтобы как можно дольше производить автоматы. От посредника из Сопротивления вы получаете за каждый автомат по 195 денежных единиц (чтобы не напрягать Excel несуществующими франками, допустим, что это доллары). За каждую бочку масла на рынке вам платят по $150.

Условия и ограничения. Себестоимость одной бочки масла – $100, а одного автомата – $150. Месячный бюджет на производство - $1800. Вы храните продукцию в 21-кубометровом подвале. Автомат занимает ½ м 3 , бочка масла 1½ м 3 . Сколько автоматов и бочек масла вам нужно продать за месяц, чтобы получить максимальную прибыль?

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

Представим области допустимых значений графически. Во-первых, количество пушек и бочек масла должно быть неотрицательным. Во-вторых, максимально можно произвести $1800/$150 = 12 автоматов или $1800/$100 = 18 бочек масла (рис. 1). Общее название этого треугольника – политоп – фигура с плоскими сторонами (например, бриллиант). В-третьих, подвал может вместить не более 21/(½) = 42 автоматов или 21/(1½) = 14 бочек масла (рис. 2).

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

(195 – 150) * N автоматов + (150 – 100) * N бочек масла = С,

где С – константа.

Например, при С = 450, линия будет проходить через координаты (0;10) и (9;0). Графически идея максимизации прибыли реализуется перемещением линии уровня параллельно самой себе в направлении увеличения значений по осям Х и Y (рис. 3). Любопытно, что для политопа оптимум всегда лежит в одной из вершин (или единственного решения не существует вовсе). На этом свойстве основан алгоритм симплексного метода. Решение задачи в Excel начинают с создания области модели (рис. 4). Формула целевой функции в ячейке В1 =СУММПРОИЗВ(C4:D4;C10:D10).

Рис. 3. Линия уровня и функция для оптимизации прибыли: а) некое произвольное начальное положение; б) линия уровня в оптимальном положении

У вас всё готово, чтобы нажать кнопку ДАННЫЕ –> Поиск решения . (Если вы не видите этой кнопки, установите надстройку Поиск решения; см. , глава 1). В открывшемся окне Параметры поиска решения задайте выделенные опции и нажмите Найти решение .

Рис. 5. Окно Поиск решения

Excel обновит лист и внесет на него результаты расчета (рис. 6).

Что произойдет, если добавить нелинейность? Допустим ваш посредник предлагает $500, если число автоматов в месяц будет более 5. Просто добавьте функцию ЕСЛИ в ячейку с прибылью (В1). Теперь целевая функция выглядит так: =СУММПРОИЗВ(C4:D4;C10:D10)+ЕСЛИ(C4>5;500;0). Жмем Поиск решения . Неудача, Excel сообщает об ошибке – условия линейности не выполнены (рис. 7).

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

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

К сожалению, с эволюционным алгоритмом все же возникают некоторые проблемы:

Время работы существенно больше, чем при симплекс-методе
Нет никакой гарантии, что он найдет оптимальное решение. Все, что в его силах - это контроль лучшего решения в популяции, пока не закончится время, либо популяция не изменится в достаточной степени для продолжения, либо вы принудительно не остановите «Поиск решения» нажатием кнопки ESC.
Эволюционный поиск решения работает довольно медленно. А если области допустимых значений сложные, он часто ругается, не найдя даже места, с которого начать.
Если вы хотите заставить эволюционный алгоритм хорошо работать в Excel, вам придется определить жесткие границы для каждой переменной решения. Даже если ваше решение более или менее неограниченное, вам все же нужны ограничения.

Принимая во внимание последний пункт, для решения задачи с автоматами и маслом вам нужно добавить ограничение, согласно которому оба решения не должны быть больше 25 (рис. 8). Установив основные параметры модели, кликните на кнопку Параметры . Проработав около минуты, эволюционный алгоритм выдал ожидаемое решение – 6 автоматов и 9 бочек масла. Поскольку без бонуса оптимально сделать лишь три автомата, а бонус выплачивается при производстве более 5 автоматов, очевидно, что оптимальным будет выбор 6 автоматов.

Рассмотрим теперь более сложный пример. Вы работаете в компании, которая производит апельсиновый сок, смешивая натуральные соки разных сортов (рис. 9). Чтобы ваш сок отвечал самым изысканным требованиям:

отношение по шкале Брикс/кислотность должно оставаться в пределах 11,5–12,5;
уровень кислотности должен оставаться между 0,75–1%;
уровень вяжущего вкуса должен быть 4 или ниже;
цвет должен находиться в рамках 4,5–5,5.

Шеф сообщил вам, что на январь и февраль он ожидает спросу на уровне 600 000 галлонов сока в месяц, а в марте – 700 000 галлонов. И еще, имеется договор со штатом Флорида, предоставляющий налоговые льготы при условии, что компания покупает не менее 40% сока каждый месяц у фермеров, выращивающих сорт Valencia . Договор следует соблюсти.

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

Создайте оптимизационную модель (рис. 10). Формулы можно изучить на соответствующем листе, приложенного Excel-файла. Кликните Поиск решения , и введите параметры (рис. 11). Нажмите Найти решение .

Рис. 11. Заполненное окно Поиск решения для задачи смешивания

Запустив Поиск решения , вы находите оптимальную стоимость закупок - $1,23 млн. (рис. 12). Обратите внимание, что заказ флоридской Valencia проходит по нижней границе условия. Очевидно, эта сделка - не лучший вариант, но приходится смириться. Второй по популярности сорт - это Verna из Мексики, которая чертовски дешева, но ровно настолько же ужасна.

Вы представляете результаты расчета шефу, но он остается недоволен, и говорит о том, что не хочет выходить за бюджет $1,17 млн. Вы возвращаетесь к компьютеру и начинаете понимать, что стоимость перестала быть целевой функцией. Теперь это условие! А какова цель? Вы можете снизить стоимость закупок только смягчив требования к качеству. Вы решаете сформулировать их в терминах процентного сокращения, и делаете новую модель (рис. 13).

Обратите внимание, что в ячейках В26:29 и F26:F29 теперь не константы, а формулы. Ваша новая цель – минимизация процента снижения качества в ячейках G26:G29. Точнее, вы бы хотели минимизировать максимальное из значений в ячейках G26:G29. Однако, если в ячейку D2 поместить формулу =МАКС(G26:G29), модель не будет работать. Напоминаю, функция МАКС не является линейной. Здесь доступна маленькая хитрость – можно внести дополнительное условие в модель: $G$26:$G$29<=$D$2 (рис. 14), а ячейку D2 оставить пустой. Т.е., ячейка D2 будет оптимизироваться не благодаря наличию в ней формулы, а последовательными циклами, запускаемыми этим дополнительным условием.

Нажмите Найти решение . Симплексный алгоритм будет пытаться приблизить D2 к 0 как целевую функцию модели, в то время как ограничения по вкусу и цвету будут пытаться увеличить ее насколько возможно, чтобы получить пригодную для работы смесь. Где же остановится значение D2? Самое меньшее из возможных значений - максимальный процент из четырех сниженных в диапазоне G26:G29. Мы видим (рис. 15, ячейки С26:Е29), что снижение расходов на 5% потребовало выйти за ограничения качества по всем четырем параметрам.

Вы представили данные шефу, который увидел, что сокращение расходов на 5% не стоит снижения качества сока, поэтому он согласовал ваш первый вариант. Но, когда вы принесли его в отдел снабжения, сотрудники возмутились. Как можно было так раздробить поставки!? Снабженцы настаивают, чтобы вы укрупнили партии: не более 4 поставщиков ежемесячно! И вы садитесь за новую модель. К сожалению, использовать функции ЕСЛИ или СЧЁТ вы не можете, так как хотите остаться в рамках линейной модели. Поэтому вам снова приходится прибегнуть к ухищрениям (рис. 16). Вы добавляете в модель область С33:Е43, которую определяете, как бинарную (значения в ней могут быть только 0 или 1), и оставляете ее пустой. А также область F33:H43, где каждая ячейка равна произведению значения из областей С33:Е43 на G5:G15. В параметры Поиск решения (рис. 17) вы добавляете еще одно условие $С$15:$Е$15 <= $F$33:$H$43 и еще одну область переменных – $C$33:$E$43.

Как в этом случае будет работать оптимизационный алгоритм? Когда он стартует все значения в областях С5:Е15, С33:Е43 и F33:H43 равны нулю. Допустим, что алгоритм пытается в ячейку С7 поместить значение 240. Сработает условие С7 <= F35, которое приведет к увеличению значения в F35, которое, в свою очередь, определяется формулой F35 = C35*$G7. Поскольку G7 – константа, а С35 – бинарная переменная, последней присваивается значение 1. Условие С7 <= F35 выполнено, т.к., 240 <= 1200. Таким образом вы моделируете неудобное условие «если… то»: «если заказ сделан, то бинарная переменная включается».

Нажмите Найти решение . Вы заметите, что решение задачи требует больше времени из-за добавления бинарных переменных. Если по какой-то причине Поиск решения слишком затянул свой поиск, вы всегда можете нажать ESC и увидеть лучшее из найденных решений на данный момент.

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

Инженеры сообщили, что на производстве появились новые «снижатели кислотности». Данная технология способна нейтрализовать 20% кислоты в соке, протекающем через прибор. Это не только снижает процент кислоты, но и повышает индекс Брикс/кислотность на 25%. Но для «снижателя» нужна энергия и расходные материалы стоимостью $20 за 1000 галлонов сока. Не весь сок, поступающий от поставщиков, нужно прогонять через этот процесс, однако, если поставка по какому-нибудь заказу прогоняется через ионообменник, то должен быть обработан весь ее объем. Постройте модель с участием ионообменника для снижения стоимости.

Проблема с новым правилом заключается в том, что естественный способ его моделирования - нелинейный, что приведет к использованию медленного алгоритма оптимизации. Но, как и в предыдущем примере, можно ввести бинарную переменную в области С25:Е35, которая бы «включалась» при необходимости понизить кислотность партии (рис. 18). Поскольку, нельзя использовать произведение «индикатор понижения кислотности (бинарный) * объем партии», вы создаете область С37:Е47, которая вам пригодятся для уравнивания объемов, подлежащих снижению кислотности, без прямого участия в формулах самих этих объемов. Итак, области С25:Е35 и С37:Е47 не содержат формул. В области G25:I35 используются формулы =С25:Е35*G5:G15 (это ограничение партии общим доступным объемом сока), а в области К25:М35 =Е5:E15-GG5:15*(1-Е25:E35). Это условие заработает только если партия подлежит снижению кислотности.

Также в модели со «снижателем кислотности» были изменены формулы в ячейках С16:Е16 (теперь они учитывают затраты на снижение кислотности по формуле «индикатор (бинарный) * объем партии * $20) и в ячейках С50:Е51 (теперь они учитывают повышение коэффициента Брикс/кислотность на 25% и снижение кислотности на 20% для обработанных партий). В параметрах Поиска решения появились новые переменные и дополнительные условие (рис. 19). К сожалению, нажав кнопку Найти решение , вы узнаете, что надстройка Поиск решения не может справиться с задачей (рис. 20). Модель стали слишком сложной.

Рис. 19. Параметры Поиска решения в модели со «снижателем кислотности»

Рис. 20. Поиск решения не справляется с задачей

Вам нужно загрузить и установить OpenSolver (как это сделать см. , глава 1). OpenSolver «подхватит» установки, введенные только что в окне Поиск решения . Поэтому просто нажмите кнопку Solver . Полученное решение – $1 235 927 более чем на $ 100 000 лучше предыдущего минимума – $1 338 913.

До сих пор мы считали, что поставляемая продукция имеет точно указанные параметры. Резонно предположить, что эти параметры подвержены вариации, характеризуемой среднеквадратичным отклонением (рис. 21; подробнее см. ). Самое известное и широко используемое распределение случайной величины - это нормальное распределение, иначе называемое «колоколообразной кривой». Скажем, в случае с соком из Египта среднее значение отношения Брикс/кислотность будет 13, а среднеквадратичное отклонение (также называемой стандартным отклонением) - 0,9 (рис. 21). В данном примере 13 - это центр распределения вероятности, 68% заказов будут в пределах ±0,9 от 13, а 95% будут в пределах ±1,8 от 13.

Ваша цель - предложить план смешивания стоимостью меньше $1,25 миллиона, который наилучшим образом соответствует ожиданиям по качеству в свете вариабельности поставок.

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

Сценарий - это один из возможных ответов на вопрос: «Если это - распределения, основанные на статистике, на что же будет похож конкретный заказ?» Каждый сценарий включает сорок параметров десяти сортов сока (рис. 22). Чтобы получить один такой параметр, воспользуйтесь функцией НОРМ.ОБР (подробнее о функции см. ). Например, в ячейке В33 отношение Брикс/кислотность для сорта Hamlin определяется формулой =НОРМ.ОБР(СЛЧИС();H5;N5). Введите аналогичные формулы в область В33:СW76, сгенерировав 100 сценариев. Поиск решения не сможет работать с этими формулами, так как они нелинейны, поэтому скопируйте их в буфер и вставьте, но уже, как значения.

Цель минимизировать значение в ячейке D2. Т.е., найти решение, которое менее всего снижает границы качества для 100 сценариев. Как и в примерах на рис. 13–15, в ячейке D2 нет формулы. Оптимизация выполняется заданием параметров в окне Поиск решения. Все, что нужно - это поместить во все сценарии границы качества, а не просто ожидаемые значения характеристик. Таким образом, в отношение Брикс/кислотность вы добавляете условия B78:CW80 >= B26 и =< F26, затем проделываете то же самое с кислотностью, вяжущей составляющей вкуса и цветом (рис. 24). Нажмите Найти решение . Решение найдется довольно быстро. Если вы генерировали случайные значения сами, а не использовали те, что находятся в файле для загрузки, ваше решение может отличаться. Для моей сотни сценариев наилучшим показателем, который мне удалось получить, является изменение качества на 133%.

Рис. 24. Настройка Поиска решения для модели с вариабельностью характеристик

Если вы хотите расширить свои знания в области линейного программирования, рекомендую книгу The AIMMS optimization modeling book . Не пропустите две главы про трюки и подсказки – они поистине гениальны.

Написано по материалам книги Джона Формана . – М.: Альпина Паблишер, 2016. – С. 129–186. Насчет секретности разработки и Второй мировой – это, похоже, личное мнение автора книги. См. Википедию . – Прим. Багузина .

Размер: px

Начинать показ со страницы:

Транскрипт

1 Решение задачи линейного программирования графическим методом, симплекс-методом и через «Поиск решения» в Ecel ЗАДАНИЕ. Предприятие выпускает два вида продукции: Изделие и Изделие. На изготовление единицы Изделия требуется затратить a кг сырья первого типа, a кг сырья второго типа, a кг сырья третьего типа. На изготовление единицы Изделия требуется затратить a кг сырья первого типа, a кг сырья второго типа, a кг сырья третьего типа. Производство обеспечено сырьем каждого типа в количестве b кг, b кг, b кг соответственно. Рыночная цена единицы Изделия составляет c тыс. руб., а единицы Изделия - c тыс.руб. Требуется:) построить экономико математическую модель задачи;) составить план производства изделий, обеспечивающий максимальную выручку от их реализации при помощи графического метода решения задачи линейного программирования.) составить план производства изделий, обеспечивающий максимальную выручку от их реализации при помощи табличного симплекс метода решения задачи линейного программирования. 4) составить план производства изделий, обеспечивающий максимальную выручку от их реализации, используя надстройку «Поиск решения» в среде MS EXCEL. РЕШЕНИЕ.) Математическая модель задачи. Переменные задачи В задаче требуется определить оптимальное число изделий каждого вида, обеспечивающее максимальную прибыль от их реализации, а значит, переменными задачи являются количество каждого вида изделий: количество изделий вида; количество изделий вида.

2 Целевая функция Критерием эффективности служит параметр прибыли, который должен стремиться к максимуму. Чтобы рассчитать величину прибыли от реализации изделий, необходимо знать: выпускаемое количество изделий каждого вида, т.е. и; прибыль от их реализации согласно условию, соответственно и тыс. руб. Таким образом, прибыль от реализации выпускаемых изделий вида равна тыс.руб., а от реализации изделий вида тыс.руб. Поэтому запишем ЦФ в виде суммы прибыли от продажи каждого из видов изделий: Z () = + Ограничения Возможное оптимальное количество изделий каждого вида и ограничивается следующими условиями: Заданными ресурсами -, и, которые используются на выпуск каждого вида изделия, не могут превышать общего запаса ресурсов; количество каждого вида изделия не может быть отрицательным. Запишем эти ограничения в математической форме: по расходу ресурса: по расходу ресурса: + 00, по расходу ресурса: + не отрицательность количества выпускаемых костюмов задаётся так:,). Таким образом, математическая модель этой задачи имеет вид Z () = ; + 00; + ; 0; 0. ГРАФИЧЕСКИЙ МЕТОД РЕШЕНИЯ ЗАДАЧИ Так как переменные задачи и входят в целевую линейную функцию и ограничения задачи линейны, то соответствующая задача оптимизации задача линейного программирования. Построим в декартовой системе координат X OX многоугольник решений, или допустимых планов, который является пересечением полуплоскостей - решений каждого из неравенств системы ограничений.

3 (): Сначала строится разделяющая прямая + 7 = 60. Для этого находим две точки, через которые она проходит: Подставим точку (0;0) в неравенство (): верно, поэтому стрелки указывают на полуплоскость к нулю. (): Разделяющая прямая + 00, найдём точки: = Подставим точку (0;0) в неравенство (): верно, поэтому стрелки указывают на полуплоскость к нулю. (): +. Разделяющая прямая +, найдём точки: = 0 66,4 0 Подставим точку (0;0) в неравенство (): 0 - верно, поэтому стрелки указывают на полуплоскость к нулю. Находим многоугольник, в котором пересекаются, накладываются друг на друга все построенные полуплоскости. Многоугольник допустимых решений заштриховывается.

4 Построим градиент и линию уровня функции цели: Z(X) = + g(;). Градиент всегда изображается с началом в т.(0;0). Любая линия уровня перпендикулярна градиенту. Удобно построить линию уровня Z = 0, также проходящую через начало координат: + = 0. Перемещаем мысленно или с помощью линейки линию уровня так, чтобы найти угловые точки многоугольника допустимых планов, координаты которых доставляют максимальное значение функции цели. В данной задаче линия уровня перемещается в направлении за градиентом, поэтому её значения будут увеличиваться от линии к линии. Следовательно, в точке А будет наибольшее значение. Найдём координаты точки А, как точки пересечения разделяющих прямых: + + Второе уравнение умножим на (-): = 00 = + = 00 = 996 сложим уравнения 4

5 = 8 = 696 = = 8 = 4 Следовательно, A (8;4), Z (8;4) = = Ответ: изделия вида необходимо выпускать в количестве 8 единиц, а изделия вида в количестве 4 единицы. При этом прибыль от их реализации максимальная и составит 4660 тыс. руб.) СИМПЛЕКС МЕТОД Приводим задачу к каноническому виду, для этого в каждое неравенство вводим дополнительную переменную со знаком плюс:, 4,. Z () = = 60; = 00; + + = ; 0; 0. Дальнейшее решение будем вести в симплекс таблицах. Таблица Так как задача на нахождение максимального значения, то в индексной строке выбираем наибольшую по модулю отрицательную оценку это столбец с переменной (таблица). Выделяем его. Далее находим оценочные отношения, путём деления столбца С на столбец D, которые записываем в предпоследний столбец таблицы, из которых выбираем наименьшее из них это 66,4 третья строка. Выделяем её. В последнем столбце запишем пересчитывающие коэффициенты: 0,4; = 0,6 =, которые необходимы при пересчёте всех невыделенных элементов. Третью строку делим на. Из базиса выводим переменную,

6 при этом в базис вводим переменную. Все невыделенные элементы пересчитываем по методу Гаусса, например для первой строки: 60 0,4 = 47, 0,4 = 0 и так все элементы. В результате перейдём к таблице. Таблица Так как в индексной строке присутствует отрицательная оценка, план не оптимален. Требуется улучшение плана. Выделяем столбец с переменной. Далее находим оценочные отношения делением столбца С на столбец Е, среди которых наименьшее 4 - вторая строка. Выделяем её. Элементы строки делим на,4. Из базиса выводим переменную 4, при этом в базис вводим переменную. Получим таблицу. Таблица Так как в индексной строке все оценки положительные или равны нулю, план оптимален: Z (8;4) = 4660, ответ такой же как и при решении графическим методом. 4) ПРИМЕНЕНИЕ НАДСТРОЙКИ «ПОИСК РЕШЕНИЯ» MS EXCEL Для решения рассмотренной задачи в среде Ecel заполним ячейки исходными данными (в виде таблицы) и формулами математической модели. Ecel позволяет получить оптимальное решение без ограничения размерности системы неравенств и целевой функции. 6

7 Таблица в режиме чисел Таблица в режиме формул Здесь: В9:С9 результат (оптимальное количество изделий каждого вида); В6:С6 коэффициенты целевой функции; В0 значение целевой функции; В:С коэффициенты ограничений; D:D4 правая часть ограничений; B:B4 вычисляемые (фактические) значения левой части ограничений. Решим задачу с помощью команды меню Сервис / Поиск решения. Итак, делаем активной ячейку B0. Выполняем команду Сервис / Поиск решения. На экране появляется диалоговое окно Поиск решения. 7

8 В поле Установить целевую будет показана ссылка на активную ячейку, то есть на B0. Причём эта ссылка абсолютная (мы видим $B$0). В секции Равной: устанавливаем переключатель максимальному значению. Можно задать не только максимальное/минимальное значения, но и любую произвольную величину, введя её в специальное поле значению в секции Равной:. Ограничения устанавливаются с помощью кнопки Добавить, которая вызывает диалоговое окно их ввода Добавление ограничения. В поле ввода Ссылка на ячейку: указывается адрес ячейки, содержащей формулу левой части ограничения. Затем выбирается из списка знак соотношения. В поле Ограничение: указывается адрес ячейки, содержащей правую часть ограничения. Щёлкаем на кнопку Добавить и повторяем для следующего ограничения. После ввода всех ограничений следует щёлкнуть кнопку ОК. Так как все переменные несут условие не отрицательности, то их положительность задаём через кнопку Параметры в окне диалога Поиск решения. После щелчка на ней, на экране окно Параметры поиска решения. 8

9 Устанавливаем флажки Линейная модель и Неотрицательные значения, соглашаясь с остальными установками по умолчанию. Щёлкаем на кнопке ОК. После этого произойдёт переключение в окно Поиск решения, в котором необходимо щёлкнуть кнопку Выполнить для решения поставленной задачи. Ecel предъявит окно Результаты поиска решения с сообщением о том, что решение найдено, или о том, что не может найти подходящего решения. Если вычисления оказались успешными, Ecel предъявит следующее окно итогов. Их можно сохранить или отказаться (Восстановить исходные значения). Кроме того, можно получить один из трёх видов отчётов (Результаты, Устойчивость, Пределы), позволяющие лучше осознать полученные результаты, в том числе, оценить их достоверность. После найденного решения, в ячейках В9:С9 количество изделий каждого вида. Покажем это. появится оптимальное 9

10 При сохранении отчёта выбрали вид отчёта Отчёт по результатам. Из отчёта видно, что ресурс не используется полностью на 0 кг, а ресурсы и используются полностью. Получили оптимальный план, при котором изделий первого вида необходимо выпустить в количестве 8 шт., а изделий второго вида в количестве 4 шт. При этом прибыль от их реализации максимальная и составит 4660 тыс.руб. 0

Линейное программирование Задача 1... 2 Задача 2... 3 Задача 3... 5 Задача 4... 7 Задача 5... 10 Задача 6... 12 Задача 7... 15 Задача 8... 19 Задача 9... 21 Задача 10... 24 Задача 11... 27 Задача 1. Составить

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

1 Лабораторная работа 3 Решение задач. Подбор параметров, поиск решения 1. Реализация математической модели в Excel Математическая модель это описание состояния поведения некоторой реальной системы (объекта,

Решить задачу линейного программирования, где 3x12x2 8 x14x2 10 x1 0 x 2 0 LX3x14x2 max а) геометрическим способом, б) перебором базисных решений, в) симплекс-методом. Графическое решение задачи L X 3x14

ЛАБОРАТОРНАЯ РАБОТА СРЕДСТВА ПОДДЕРЖКИ ПРИНЯТИЯ РЕШЕНИЙ КАК ФУНКЦИИ EXCEL Команда Подбор параметра Задание 1. Рассмотрим задачу, составленную на основании задачи по использованию функции ЧПС. Вас просят

Линейная производственная задача. Предприятие может выпускать четыре вида продукции, используя при этом три вида ресурсов. Известны технологическая матрица A затрат 7 8 ресурсов на производство единицы

1 Симплексный метод решения ЗЛП Шаг 1. Формулировка ЗЛП (формирование целевой функции и системы ограничений). Для определенности будем считать, что решается задача на отыскание максимума. Ниже приведем

Линейная алгебра 08.12.2012 Линейные модели в экономике Линейное программирование Линейная алгебра (лекция 13) 08.12.2012 2 / 25 Задача линейного программирования: F (x 1, x 2,..., x n) = n c j x j max(min),

) Задача о планировании производства. Производственному участку может быть запланировано к изготовлению на определённый плановый период времени два вида изделий: A и B. На производство единицы изделия

Контрольная работа Задача 5 На предприятии имеется сырье видов 1, 2, 3 Из него можно изготавливать изделия типов А и В Пусть запасы видов сырья на предприятии составляют b 1, b 2, b 3 ед соответственно,

ФЕДЕРАЛЬНОЕ АГЕНТСТВО ЖЕЛЕЗНОДОРОЖНОГО ТРАНСПОРТА ФЕДЕРАЛЬНОЕ ГОСУДАРСТВЕННОЕ БЮДЖЕТНОЕ ОБРАЗОВАТЕЛЬНОЕ УЧРЕЖДЕНИЕ ВЫСШЕГО ОБРАЗОВАНИЯ Московский государственный университет путей сообщения Императора

Задача. Решить графически ma F Находим точки пересечения прямых определяющих неравенства. Отсюда Точка пересечения не принадлежит области. Построим область допустимых решений. Построим вектор направления

ВАРИАНТ 5 Для изготовления различных изделий А, В, С предприятие использует различных вида сырья. Используя данные таблицы: Вид сырья Нормы затрат сырья Кол-во сырья А В С I II III 18 6 5 15 4 12 8 540

ФЕДЕРАЛЬНОЕ АГЕНТСТВО ЖЕЛЕЗНОДОРОЖНОГО ТРАНСПОРТА ФЕДЕРАЛЬНО ГОСУДАРСТВЕННОЕ ОБРАЗОВАТЕЛЬНОЕ УЧРЕЖДЕНИЕ ВЫСШЕГО ПРОФЕССИОНАЛЬНОГО ОБРАЗОВАНИЯ «МОСКОВСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ ПУТЕЙ СООБЩЕНИЯ имени

Лабораторная работа 4 Тема работы: Решение задачи об оптимальном распределении ресурсов при выпуске продукции с использованием процедуры Поиск решения Microsoft Excel. Цель работы: Научиться использовать

АНО ВПО «Региональный финансово-экономический институт» ИТОГОВЫЙ ЭКЗАМЕН по учебной дисциплине «Методы оптимальных решений» http://elearning.rfei.ru 1 Уважаемые студенты! Итоговым контролем изученного

УДК 518.85 НЕКОТОРЫЕ МЕТОДЫ РЕШЕНИЯ ЗАДАЧ ДРОБНО-ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ В.В. Листопад Национальный университет пищевых технологий, г. Киев, Украина, [email protected] В докладе приведены три способа

Практическая работа 8 Решение задач линейного программирования графическим методом. Цель работы: Научиться решать задачи линейного программирования графическим методом. Содержание работы: Основные понятия.

Князева А., Лыкова Н.П. ГОУ ВПО «Российский государственный гуманитарный университет» Филиал в г. Самаре ПОСТАНОВКА ЗАДАЧ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ И ИХ РЕШЕНИЕ С ПОМОЩЬЮ MS EXCEL Временем рождения линейного

ЗАДАНИЕ ПРАКТИЧЕСКОЙ РАБОТЫ 4 И ПРАКТИЧЕСКОЙ РАБОТЫ 5 Задачи линейной оптимизации Построение экономико-математических моделей (ЭММ). Решение задач линейной оптимизации с использованием информационных технологий.

Лабораторная работа Тема: Построение графиков функций Цель работы: Изучение графических возможностей пакета Ms Ecel Приобретение навыков построения графика функции на плоскости средствами пакета Задание

Рассмотрим первый способ решения СЛУ по правилу Крамера для системы трех уравнений с тремя неизвестными: Ответ рассчитывается по формулам Крамера: D, D1, D2, D3 это определители Определителем третьего

8. Фонд оценочных средств для проведения промежуточной аттестации обучающихся по дисциплине (модулю): Общие сведения 1. Кафедра М и ММЭ 2. Направление подготовки 01.03.02 (010400.62) Прикладная математика

АНАЛИЗ ДАННЫХ В MS EXCEL Гедранович Валентина Васильевна 27 июня 2012 г. Аннотация Глава 11 из УМК: Гедранович, В.В. Основы компьютерных информационных технологий: учеб.-метод. комплекс / В.В. Гедранович,

ПРИМЕНЕНИЕ MS EXCEL ПРИ РЕШЕНИИ ЗАДАЧ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ Сулейманова И.И., Сагадеева Э.Ф. ФГБОУ ВО Башкирский ГАУ MS EXCEL APPLICATION IN SOLVING LINEAR PROGRAMMING PROBLEMS Suleymanova I.I., Sagadeeva

Лекции Глава Функции нескольких переменных Основные понятия Некоторые функции многих переменных хорошо знакомы Приведем несколько примеров Для вычисления площади треугольника известна формула Герона S

Министерство образования и науки Российской Федерации Федеральное государственное бюджетное образовательное учреждение высшего образования «НИЖЕГОРОДСКИЙ ГОСУДАРСТВЕННЫЙ ТЕХНИЧЕСКИЙ УНИВЕРСИТЕТ ИМ. Р.

ФЕДЕРАЛЬНОЕ АГЕНТСТВО ПО ОБРАЗОВАНИЮ Государственное образовательное учреждение высшего профессионального образования «ВОРОНЕЖСКИЙ ГОСУДАРСТВЕННЫЙ ПЕДАГОГИЧЕСКИЙ УНИВЕРСИТЕТ» Кафедра ИНФОРМАТИКИ И МЕТОДИКИ

ФЕДЕРАЛЬНОЕ АГЕНТСТВО ЖЕЛЕЗНОДОРОЖНОГО ТРАНСПОРТА Государственное образовательное учреждение высшего профессионального образования «МОСКОВСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ ПУТЕЙ СООБЩЕНИЯ» Институт экономики

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

Практическая работа 13 Тема: ЗАДАЧИ ОПТИМИЗАЦИИ (ПОИСК РЕШЕНИЯ) В MICROSOFT EXCEL Цель занятия. Изучение технологии поиска решения для задач оптимизации (минимизации, максимизации). Задание 13.1. Минимизация

Глава 8 Уравнение линии в пространстве Как на плоскости, так и в пространстве, любая линия может быть определена как совокупность точек, координаты которых в некоторой выбранной в пространстве системе

Тема. Определители. Решение систем линейных уравнений по формулам Крамера При умножении определителя на число на это число умножаются все элементы определителя первые две строки все элементы какой-нибудь

ПРИБЛИЖЕННЫЕ МЕТОДЫ РЕШЕНИЯ НЕЛИНЕЙНЫХ УРАВНЕНИЙ Отделение корней Пусть дано уравнение f (0, () где функция f (C[ a; Определение Число f () 0 x называется корнем уравнения () или нулем функции f (,

8 Фонд оценочных средств для проведения промежуточной аттестации обучающихся по дисциплине (модулю): Общие сведения 1 Кафедра Математики и математических методов в экономике 2 Направление подготовки 380301

УЧЕБНОЕ ИЗДАНИЕ В ЭЛЕКТРОННОМ ВИДЕ С.Ю. Белецкая, В.Н. Фролов МЕТОДИЧЕСКИЕ УКАЗАНИЯ к практическим занятиям по дисциплине «Методы оптимизации и математическое программирование» для аспирантов направления

Анализ «Что если» СПбГУ, ЭФ каф. ИСЭ Порошин А.Н. Анализ "что-если" Анализ "что-если" это процесс поиска ответов, например, на следующие вопросы: "Что будет, если процентная ставка кредита поднимется с

ФОНД ОЦЕНОЧНЫХ СРЕДСТВ ДЛЯ ПРОВЕДЕНИЯ ПРОМЕЖУТОЧНОЙ АТТЕСТАЦИИ ОБУЧАЮЩИХСЯ ПО ДИСЦИПЛИНЕ (МОДУЛЮ) Общие сведения. Кафедра Информатики, вычислительной техники и информационной безопасности. Направление

Вычисляемые поля и вычисляемые элементы в Excel 2013 В процессе анализа данных с использованием сводных таблиц часто возникает потребность во включении в отчет значений, полученных в результате вычислений,

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

ФЕДЕРАЛЬНОЕ АГЕНТСТВО ЖЕЛЕЗНОДОРОЖНОГО ТРАНСПОРТА ФЕДЕРАЛЬНОЕ ГОСУДАРСТВЕННОЕ ОБРАЗОВАТЕЛЬНОЕ УЧРЕЖДЕНИЕ ВЫСШЕГО ПРОФЕССИОНАЛЬНОГО ОБРАЗОВАНИЯ «МОСКОВСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ ПУТЕЙ СООБЩЕНИЯ» (МИИТ)

ФЕДЕРАЛЬНОЕ АГЕНСТВО ЖЕЛЕЗНОДОРОЖНОГО ТРАНСПОРТА ФЕДЕРАЛЬНО ГОСУДАРСТВЕННОЕ ОБРАЗОВАТЕЛЬНОЕ УЧРЕЖДЕНИЕ ВЫСШЕГО ПРОФЕССИОНАЛЬНОГО ОБРАЗОВАНИЯ «МОСКОВСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ ПУТЕЙ СООБЩЕНИЯ» (МИИТ)

МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РОССИЙСКОЙ ФЕДЕРАЦИИ Федеральное государственное автономное образовательное учреждение высшего профессионального образования «Национальный исследовательский ядерный университет

Ускоренное освоение методов линейного программирования в режиме диалога с программой, выполняющей арифметические операции Богомазов Р. Ю., Беседин Н. Т. Юго-западный государственный университет 1. Цель

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

Г р а ф и ч е с кое решение систем уравнений Аналитическая геометрия изучает геометрические объекты по их уравнениям. MS Excel предоставляет широкие возможности визуализации различных уравнений. В Excel

ФЕДЕРАЛЬНОЕ АГЕНТСТВО ЖЕЛЕЗНОДОРОЖНОГО ТРАНСПОРТА Федеральное Государственное Бюджетное Образовательное Учреждение Высшего Профессионального Образования «МОСКОВСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ ПУТЕЙ СООБЩЕНИЯ»

МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РОССИЙСКОЙ ФЕДЕРАЦИИ федеральное государственное автономное образовательное учреждение высшего профессионального образования «Казанский (Приволжский) федеральный университет»

Вопрос. Неравенства, система линейных неравенств Рассмотрим выражения, которые содержат знак неравенства и переменную:. >, - +х -это линейные неравенств с одной переменной х.. 0 - квадратное неравенство.

«MICROSOFT OFFICE EXCEL» Дисциплина «Программные средства профессиональной деятельности» Лектор: Ст. преподаватель кафедры «Электропривода и электрооборудования» Воронина Наталья Алексеевна Назначение

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

Министерство образования и науки Российской Федерации Федеральное государственное бюджетное образовательное учреждение высшего образования «Ивановский государственный политехнический университет» Институт

ЛАБОРАТОРНЫЕ РАБОТЫ ПО MS EXCEL 2007 ЛАБОРАТОРНАЯ РАБОТА 1.... 1 ЛАБОРАТОРНАЯ РАБОТА 2... 3 ЛАБОРАТОРНАЯ РАБОТА 3... 4 ЛАБОРАТОРНАЯ РАБОТА 4... 7 ЛАБОРАТОРНАЯ РАБОТА 5... 8 ЛАБОРАТОРНАЯ РАБОТА 6... 10

Раздел 7. УРАВНЕНИЯ ПРЯМОЙ И ПЛОСКОСТИ В ПРОСТРАНСТВЕ Лекция 4. Тема: Уравнения прямой и плоскости в пространстве 7. Система координат в пространстве Рассмотрим прямоугольную декартову систему координат

4 Методы нахождения первоначальной крайней точки 4. Переход к решению двойственной задачи Рассмотрим метод решения задач линейного программирования путем перехода к двойственной задаче и решения полученной

МИНИСТЕРСТВО ОБРАЗОВАНИЯ РОССИЙСКОЙ ФЕДЕРАЦИИ КУРГАНСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ КАФЕДРА «ИНФОРМАТИКА» РЕАЛИЗАЦИЯ ОПТИМИЗАЦИОННЫХ МОДЕЛЕЙ В СРЕДЕ EXCEL Методические указания к проведению лабораторных

ФЕДЕРАЛЬНОЕ АГЕНСТВО ЖЕЛЕЗНОДОРОЖНОГО ТРАНСПОРТА ФЕДЕРАЛЬНОЕ ГОСУДАРСТВЕННОЕ БЮДЖЕТНОЕ ОБРАЗОВАТЕЛЬНОЕ УЧРЕЖДЕНИЕ ВЫСШЕГО ПРОФЕССИОНАЛЬНОГО ОБРАЗОВАНИЯ «МОСКОВСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ ПУТЕЙ СООБЩЕНИЯ

NovaInfo.Ru - 58, 2017 г. Физико-математические науки 1 ГРАФИЧЕСКИЙ МЕТОД РЕШЕНИЯ ЗАДАЧ ЛП Голубцова Владислава Олеговна Графический метод довольно прост и нагляден для решения задач линейного программирования

Кафедра математики и информатики Элементы высшей математики Учебно-методический комплекс для студентов СПО, обучающихся с применением дистанционных технологий Модуль 6 Элементы линейного программирования

Работа со списками в MS EXCEL Цель: Приобрести навыки поиска и агрегирования данных в списке. Краткая теория Компьютерные информационные технологии широко используются для анализа данных и подготовку управленческих

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

Образцы базовых задач по ЛА Метод Гаусса Определенные системы линейных уравнений Решите систему линейных уравнений методом Гаусса x 6 y 6 8, 6 x 6 y 6 Решите систему линейных уравнений методом Гаусса 6

Практическая работа 3.7. Использование мастера функций MS Excel. Построение диаграмм Цель работы. Выполнив эту работу, Вы научитесь: вводить формулы в ячейки таблицы; использовать Мастер функций MS Excel

Глава 8 Базы данных в OpenOffice.org Calc В этой главе мы изучим возможности пакета OpenOffice.org Calc при работе с базами данных. Довольно часто возникает необходимость хранить и обрабатывать данные

ОБРАЗЕЦ ОФОРМЛЕНИЯ ОТЧЕТА Разработчик доц., к.ф.-м.н. Манита Л.А. Московский институт электроники и математики НИУ ВШЭ Отчет студентов группы МЭ-63 Воробьянинова Ипполита Матвеевича, Изнуренкова Авессалома

Число газет Лабораторно-практическая работа ТЕМА: «MS Excel. Построения, форматирования и редактирования диаграмм, графиков». ЦЕЛЬ УРОКА: научиться строить, форматировать и редактировать диаграммы, графики.

ФЕДЕРАЛЬНОЕ АГЕНСТВО ЖЕЛЕЗНОДОРОЖНОГО ТРАНСПОРТА ФЕДЕРАЛЬНО ГОСУДАРСТВЕННОЕ ОБРАЗОВАТЕЛЬНОЕ УЧРЕЖДЕНИЕ ВЫСШЕГО ПРОФЕССИОНАЛЬНОГО ОБРАЗОВАНИЯ «МОСКВОСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ ПУТЕЙ СООБЩЕНИЯ» (МИИТ)

БЕЛОРУССКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ МЕХАНИКО-МАТЕМАТИЧЕСКИЙ ФАКУЛЬТЕТ Кафедра нелинейного анализа и аналитической экономики В. И. БАХТИН, И. А. ИВАНИШКО, А. В. ЛЕБЕДЕВ, О. И. ПИНДРИК ЛИНЕЙНОЕ ПРОГРАММИРОВАНИЕ

Симплекс-метод решения задач линейного программирования Основным численным методом решения задач линейного программирования является так называемый симплекс-метод. Термин «симплекс-метод» связан с тем

Решение ЗЛП симплексным методом с использованием таблиц EXCEL

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

Первая симплексная таблица на рабочем листе EXCEL будет иметь вид (рис. 10):

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

Этап 1. Выбрать разрешающие столбец и строку и выделить разрешающий элемент (см. рис. 11).

Этап 2. Заменить в новой таблице столбцы “Базис” и ”С б ” согласно правилам их заполнения.

Элементы разрешающей строки делятся на разрешающий элемент и записываются в соответствующей по номеру строке новой таблицы:

, при i = r . (*)

Все остальные элементы новой таблицы рассчитываются по формулам:

, при i ≠ r (**)

где - элемент новой симплекс-таблицы, a ij , - элемент предыдущей симплекс-таблицы, a rk - разрешающий элемент, a ik - элемент разрешающего столбца, a rj - элемент разрешающей строки.

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

Этап 4. Элементы последней строки новой таблицы заполняются или по формулам (**), или по правилу заполнения данной строки.

Результаты расчетов в таблицах EXCEL для нашего примера приводятся на рис 11, а формулы, использовавшиеся при данных расчетах – на рис. 12.

Акулич И.Л. Математическое программирование в примерах и задачах: Учеб. пособие для студентов эконом. спец. вузов. - М.: Высш. шк., 1986.-319с., ил.

Сакович В.А. Исследование операций (детерминированные методы и модели): Справочное пособие. - Мн.: Выш. шк., 1984.-256с.

Таха Х. Введение в исследование операций: в 2-х книгах. Кн.1. Пер. с англ. – М.: Мир, 1985.-479с., ил.

Методические указания к практическим занятиям по дисциплине «Математическое программирование» (линейное программирование) для студентов экономических специальностей / Сост. Туровцев Г.В., Нудный И.П. – Запорожье, ЗГИА, 1984.-31с.

Математическое программирование. Конспект лекций для студентов экономических специальностей дневного и заочного отделений /Глущевский В.В., Исаенко А.Н. – Запорожье: ЗГИА, 2003. – 150с.