4767

Решение задач линейного программирования с использованием Microsoft EXCEL for WINDOWS

Конспект

Информатика, кибернетика и программирование

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

Русский

2012-11-25

18.9 MB

1250 чел.

Введение

Линейное программирование – наиболее изученный раздел дисциплины Методы исследования операций. Математические модели большинства экономических задач относятся к классу задач линейного программирования (ЗЛП). Любая ЗЛП, приведенная к канонической форме, может быть решена с помощью универсального алгоритма – «Симплексного метода». Однако, ручной счет по данному методу – трудоемкий процесс. Умение использовать Microsoft EXCEL for WINDOWS для автоматизации вычислений значительно упрощает и ускоряет процесс решения ЗЛП. Пакет EXCEL позволяет в полностью автоматическом режиме найти оптимальное решение ЗЛП в любой первоначальной форме (инструмент “Поиск решения”). Кроме того, используя встроенную возможность модификации формул, EXCEL реализует пошаговое решение ЗЛП симплексным методом, значительно упрощая расчеты и избавляя от возникновения случайных арифметических ошибок.


1. Решение ЗЛП с помощью инструмента “Поиск решения”

При решении ЗЛП с использованием встроенного инструмента “Поиск решения” изначально необходимо представить исходную математическую модель в удобном для заполнения таблиц EXCEL виде. Рассмотрим использование данной процедуры на примере решения “Задачи об использовании сырья”.

Задача об использовании сырья

Небольшая фабрика изготовляет два вида красок: для наружных (Е) и внутренних (I) работ. Продукция обоих видов поступает в оптовую продажу. Для производства красок используются два исходных продукта А и В. Максимально возможные суточные запасы этих продуктов составляют 6 и 8 тонн соответственно. Расходы продуктов А и В на 1 тонну соответствующих красок приведены в таблице:

Исходный продукт

Расход исходных продуктов (в тоннах) на 1 тонну краски

Максимально возможный запас продукта, тонн

краска Е

краска I

А

1

2

6

В

2

1

8

Изучение рынка сбыта показало, что суточный спрос на краску I никогда не превышает величину спроса на краску Е более чем на 1 тонну. Кроме того, установлено, что спрос на краску I никогда не превышает 2 тонн в сутки. Оптовые цены одной тонны красок равны: 3 тыс. грн. для краски Е, 2 тыс. грн. для краски I.

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

Решение:

Пусть Х1, Х2 – планируемый к производству суточный объём производства краски Е и I соответственно (в тоннах). Тогда целевая функция математической модели будет выражать суммарную прибыль от реализации краски обоих видов, а система ограничений – производственные и маркетинговые ограничения, накладываемые на переменные модели.

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

Подготовим лист EXCEL к использованию процедуры “Поиск решения”:

  1.  в ячейках C2:D2 записываются наименования переменных модели (в общем случае количество ячеек в данном диапазоне равно количеству переменных в соответствующей математической модели);
  2.  ячейки C3:D3 резервируются для значений переменных модели, которые будут найдены после выполнения процедуры “Поиск решения”;
  3.  в ячейках C4:D4 записывают коэффициенты при переменных модели в целевой функции модели F(X1, Х2);
  4.  в ячейки C6:D9 (число строк диапазона равно количеству ограничений в системе ограничений математической модели, число столбцов – числу переменных) заносим матрицу коэффициентов при переменных X1 и Х2  в системе ограничений модели;
  5.  в ячейках G6:G9 записаны правые части системы ограничений модели;
  6.  ячейка Е4 (целевая ячейка) резервируется для вычисления оптимального значения целевой функции модели.

Для рассматриваемого примера лист EXCEL будет иметь вид (рис. 1):

После занесения исходных данных на лист EXCEL в целевую ячейку Е4 записывают формулу: СУММПРОИЗВ($C$3:$D$3;C4:D4), которую затем копируют с модификацией в ячейки Е6:Е9 (результат представлен на рис. 2):

Примечание: для вызова встроенной функции СУММПРОИЗВ необходимо выполнить последовательность действий:

  1.  установить курсор в нужную ячейку (в нашем примере – в ячейку Е4);
  2.  вызвать “Мастер функций” (кнопка fx), далее “Математические” и выбрать “СУММПРОИЗВ”;
  3.  в появившейся экранной форме (см. рис. 3) установить курсор в “Массив 1” и выделить на листе EXCEL диапазон зарезервированных для значений переменных ячеек, поставив им абсолютные адреса ($C$3:$D$3) нажатием функциональной клавиши F4; перевести курсор в “Массив 2” и выделить диапазон ячеек, в которых записаны коэффициенты при переменных в целевой функции (C4:D4), после чего нажать “ОК”.

Таким образом, после завершения всех подготовительных операций выбираем в “Сервис” процедуру “Поиск решения” (см. рис. 4). В появившейся экранной форме (см. рис 5) устанавливаем целевую ячейку - $Е$4, затем отмечаем флажком тип оптимизации (исходя из условий задачи) – максимизация; переводим курсор в “Изменяя ячейки” и выделяем на листе EXCEL диапазон зарезервированных для значений переменных ячеек ($C$3:$D$3); после чего, установив курсор в “Ограничения”, нажимаем “Добавить” и в появившейся экранной форме (см. рис. 6) отмечаем диапазон ячеек:

  1.  “Ссылка на ячейку” - $Е$6:$Е$9 (здесь записаны результаты суммирования левых частей неравенств в системе ограничений);
  2.  знак выбирается согласно построенной математической модели, причем, если не все ограничения имеют одинаковые знаки, то каждая группа таких ограничений программируется отдельно, для чего удобно ограничения с одинаковыми знаками располагать изначально рядом друг с другом;
  3.  “Ограничение:” - $G$6:$G$9 (здесь записаны правые части неравенств в системе ограничений модели).

По нажатию “ОК” возвращаемся к экранной форме “Поиск решения”. Выбираем пункт “Параметры”, где отмечаем флажком “Линейная модель” и ”Неотрицательные значения” (см. рис. 7), затем по нажатию “ОК” возвращаемся к экранной форме “Поиск решения”.

После выбора опции “Выполнить” EXCEL проводит расчеты и результаты вычислений заносятся в ячейки C3:D3 и Е4, которые были зарезервированы для значений искомых переменных и оптимального значения целевой функции.

Окончательно лист EXCEL будет иметь вид (см. рис. 8):

Замечание. Если “Поиск решения” закончил работу конфликтно, то возможны следующие ситуации:

  1.  целевая функция не ограничена на множестве допустимых решений сверху (снизу) для задачи максимизации (минимизации); в этом случае ;
  2.  неправильно введены формулы в ячейки либо допущена ошибка при заполнении формы “Поиск решения”; в данной ситуации необходимо перепроверить правильность введенных формул и вновь запустить “Поиск решения”.

Кроме поиска оптимального решения можно также получить дополнительную информацию, например, значения двойственных переменных. Для этого необходимо выделить интересующий тип отчета (в данном случае – “Устойчивость”) и нажать “ОК” (см. рис 8). Выбрав затем лист EXCEL “Отчет по устойчивости 1” (см. рис 9), в таблице “Ограничения” в столбце “Теневая цена” и будут записаны значения двойственных переменных.


Таким образом, в результате использования встроенного инструмента “Поиск решения” было найдено оптимальное решение исходной (а также и двойственной) задачи, а именно:

Итак, оптимальный план производства предусматривает выпуск 10/3т. краски Е и 4/3т. краски I, прибыль от реализации которой будет максимальной и составит  тыс. грн.


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

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

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

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

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

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


Этап 3.

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

, при i = r.     (*)

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

,  при i ≠ r  (**)

где  - элемент новой симплекс-таблицы, aij, - элемент предыдущей симплекс-таблицы, ark - разрешающий элемент , aik - элемент разрешающего столбца, arj - элемент разрешающей строки.

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

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

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



3. Решение транспортной задачи

с помощью инструмента “Поиск решения”

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

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

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

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

,   (a)

где  - количество груза перевозимого из i-го пункта производства в j-й пункт потребления; - стоимость транспортировки одного изделия (единицы груза) из пункта производства i в пункт потребления j (i=1,2,…, m,  j=1,2,…,n).

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

    (b)

0; i=1,2,…, m,  j=1,2,…,n   (c)

Условия (b) и (c) образуют систему ограничений: первая группа ограничений (b) указывает, что суммарный объем перевозок из некоторого исходного пункта равен произведенному количеству этой продукции; вторая группа ограничений (b) требует, чтобы суммарные перевозки продукции в некоторый пункт потребления полностью удовлетворили спрос на эту продукцию. Условия баланса (a) означают, что суммарный объем производства равен суммарному спросу.

Модель транспортной задачи называется закрытой, если , и открытой - в противном случае.

Для разрешимости транспортной задачи необходимо и достаточно, чтобы ее модель была закрытой.

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

В случае, если , тогда вводится фиктивный (n+1)-й пункт назначения с потребностью  и соответствующие тарифы считаются равными нулю: сin+1 = 0  ().

Если , вводится фиктивный (m+1)-й пункт отправления с запасом груза , а cm+1, j = 0,

С помощью этих преобразований открытая транспортная задача сводится к закрытой.

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

Для строительства четырех дорог используется гравий из трех карьеров. Запасы гравия в каждом из карьеров соответственно равны 120, 280 и 160 тонн потребности в гравии для строительства каждой из дорог соответственно равны 130, 220, 60 и 70 тонн известны также тарифы перевозок 1 тонны гравия из каждого карьера к каждой из строящихся дорог, которые задаются матрицей:

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


Решение:

Пусть xij – количество тонн гравия, перевозимое из i-го карьера Аi на строительство j-й дороги Вj,

Запасы гравия в карьерах (120+280+160=560) больше, чем потребности в нем (130+220+60+70=480) на строящихся дорогах. Следовательно, модель исходной транспортной задачи является открытой. Чтобы получить закрытую модель, введем дополнительный пункт назначения В5 с потребностями, равными 560-480=80 тонн. Тарифы перевозки 1 тонны гравия из всех карьеров в пункт В5 полагаем равным нулю. В результате получаем закрытую модель транспортной задачи, которая может быть решена с помощью процедуры “Поиск решения”.

Подготовим лист EXCEL к использованию процедуры “Поиск решения”:

  1.  в ячейках B4:F6 записывается матрица транспортных тарифов транспортной задачи, приведенной к закрытому типу (в общем случае размерность диапазона ячеек равна ), значения которых выступают коэффициентами при переменных в целевой функции модели;
  2.  в ячейках G4:G6 и B7:F7 записаны правые части системы ограничений модели (запасы в карьере Аi и потребности на строительстве дороги Вj соответственно);
  3.  ячейки B10:F12 резервируются для значений переменных модели, которые будут найдены после выполнения процедуры “Поиск решения”;
  4.  ячейка G13 (целевая ячейка) резервируется для вычисления оптимального значения целевой функции модели.

Для рассматриваемого примера лист EXCEL будет иметь вид (рис. 13).

После занесения исходных данных на лист EXCEL в целевую ячейку G13 записывают формулу: СУММПРОИЗВ(B4:F6;B10:F12), а в ячейку G10 - СУММ(B10:F10), которую копируют в ячейки G11:G12, и в ячейку B13 - СУММ(B10:B12), которую копируют в ячейки С13:F13. Результат представлен на рис. 14.

Таким образом, после завершения всех подготовительных операций выбираем в “Сервис” процедуру “Поиск решения”. Заполнение соответствующей экранной формы для транспортной задачи аналогично ранее рассмотренному случаю (см. п.1, рис. 5-7) и показано на рис. 15.

Окончательный результат решения транспортной задачи с использованием процедуры “Поиск решения” показан на рис. 16.


Таким образом, оптимальное решение исходной задачи можно представить матрицей:

,

а минимальное значение целевой функции при данном плане равно: F(X*)=790.

Ответ: Оптимальный план перевозок предусматривает транспортировку из 1го карьера 120 т гравия для строительства 1й дороги, из 2го карьера 220 т для строительства 2й дороги, из 3го карьера 10т для строительства 1й дороги, 60 т для 3ей дороги, 70 т для 4й дороги. При этом плане остается неиспользованным 60 т гравия во 2м карьере и 20 т гравия в 3м карьере, а общая минимальная стоимость перевозок составляет 790 условных денежных единиц.


Варианты индивидуальных заданий

Задание 1. Построить математическую модель экономической задачи. Решить задачу с помощью построенной модели симплексным методом, а также с использованием процедуры “Поиск решения”. Сделать выводы в терминах постановки задачи.

  1.  Фирма производит две модели А и В книжных полок Их производство ограничено наличием сырья (доски) и временем машинной обработки. Для каждого изделия модели А требуется 3 м2 досок, а для каждого изделия модели В — 4 м2 досок. Фирма может получить от своих поставщиков до 1700 м2 досок в неделю. На каждое изделие модели А требуется 12 мин. машинного времени, а на изделие модели В — 30 мин. В неделю можно использовать 160 час. машинного времени. Если каждое изделие модели А приносит 2 грн. прибыли, а каждое изделие модели В — 4 грн. прибыли, то сколько изделий каждой модели фирме необходимо выпускать в неделю для получения максимальной прибыли от их реализации.
  2.  Фирма производит дна продукта А и В, рынок сбыта которых неограничен. Каждый продукт должен быть обработан каждой из машин І, ІІ и ІІІ. Время обработки в часах для каждого из изделий А и В приведены ниже:

Изделие

Время обработки изделий (час) на машине типа:

І

ІІ

ІІІ

А

0,5

0,4

0,2

В

0,25

0,3

0,4

Время работы машин І, ІІ и ІІІ соответственно 40, 36 и 36 часов в неделю. Прибыль от реализации изделий составляет соответственно 5 и 3 грн. Фирме надо определить план выпуска изделий А и В, при котором прибыль от их реализации будет максимальной.

  1.  Аудитории и лаборатории университета рассчитаны не более, чем на 5000 студентов. Университет принимает не более 4000 студентов своей страны, но разрешает прием любого количества иностранных студентов. Персонал университета составляет 440 человек. Для обучения 12 студентов данной страны или 10 иностранных студентов требуется один преподаватель. Необходимо, чтобы 40% студентов данной страны и 80% иностранных студентов могли разместиться в аудиториях, где имеется 2800 мест. Университет получает 2000 долларов в год из правительственных средств на каждого студента своей страны и берет плату в размере 3000 долларов в год за каждого иностранного студента.

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

  1.  Завод-производитель высокоточных элементов для автомобилей выпускает два различных типа деталей: Х и V. Завод располагает фондом рабочего времени в 4000 чел-часов в неделю. Для производства одной детали типа Х требуется 1 чел-час, а для производства одной детали типа V — 2 чел-часа. Производственные мощности завода позволяют выпускать максимум 2250 деталей типа Х и 1750 деталей типа V в неделю. Каждая деталь типа Х требует 2 кг металлических стержней и 5 кг листового металла, а для производства одной детали типа V необходимо 5 кг металлических стержней и 2 кг листового металла. Уровень запасов каждого вида металла составляет 10000 кг в неделю. Кроме того, еженедельно завод поставляет 600 деталей типа Х своему постоянному заказчику. Существует также профсоюзное соглашение, в соответствии с которым общее число производимых в течение одной недели деталей должно составлять не менее 1500 штук.

Сколько деталей каждого типа следует производить, чтобы максимизировать общий доход за неделю, если доход от производства одной детали типа Х составляет 30 грн., а доход от производства одной детали типа V — 40 грн.?

  1.  Компания производит полки двух размеров — А и В. Агенты по продаже считают, что в неделю на рынке может быть реализовано до 550 полок. Для каждой полки типа А требуется 2 м2 материала, а для полки типа В — Зм2 материала. Компания может получить до 1200 м2 материала в неделю. Для изготовления одной полки типа А требуется 12 минут машинного времени, а для изготовления одной полки типа В — 30 минут. Машину можно использовать 160 часов в неделю. Если прибыль от продажи полки типа А составляет 3 грн., а от полки типа В - 4 грн., то сколько полок каждого типа следует выпускать в неделю чтобы прибыль от их реализации была наибольшей?
  2.  Автозавод выпускает две модели: «Каприз» и (более дешевую) «Фиаско». На заводе работает 1000 неквалифицированных и 800 квалифицированных рабочих, каждому из которых оплачивается 40 часов в неделю. Для изготовления модели «Каприз» требуется 30 часов неквалифицированного и 50 часов квалифицированного труда, а для «Фиаско» требуется 40 часов неквалифицированного и 20 часов квалифицированного труда. Каждая модель «Фиаско» требует затрат в размере 500 долларов на сырье и комплектующие изделия, тогда как каждая модель «Каприз» требует затрат в размере 1500 долларов, суммарные затраты не должны превосходить 900000 долларов в неделю. Рабочие, осуществляющие доставку, работают пять дней в неделю и могут забрать с завода не более 210 машин в день.

Каждая модель «Каприз» приносит фирме 1000 долларов прибыли, а каждая модель «Фиаско» — 500 долларов прибыли. Какой объем выпуска каждой модели Вы бы рекомендовали? Что бы Вы рекомендовали для повышения прибыли фирмы?

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

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

Вид сырья

Нормы расхода сырья (кг) на одно изделие

Общее количество сырья (кг)

А

В

I

12

4

300

II

4

4

120

III

3

12

252

Прибыль от реализации одного изделия (грн.)

30

40

  1.  Фирма производит две модели А и В книжных столов. Их производство ограничено наличием сырья (доски) и временем машинной обработки. Для каждого стола модели А требуется 6 м2 досок, а для каждого стола модели В — 5 м2 досок. Фирма может получить от своих поставщиков до 2000 м2 досок в неделю. На каждый стол модели А требуется 15 мин. машинного времени, а на изделие модели В — 30 мин. В неделю можно использовать 180 час. машинного времени. Если каждое изделие модели А приносит 5 грн. прибыли, а каждое изделие модели В — 8 грн. прибыли, то сколько изделий каждой модели фирме необходимо выпускать в неделю для получения максимальной прибыли от их реализации.
  2.  Для производства столов и шкафов мебельная фабрика использует необходимые ресурсы. Нормы затрат ресурсов на одно изделие данного вида, прибыль от реализации одного изделия и общее количество имеющихся ресурсов каждого вида приведены в таблице.

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

Ресурсы

Нормы затрат ресурсов на одно изделие

Общее количество ресурсов

стол

шкаф

Древесина (м3):

I вида

0,2

0.1

40

II вида

0.1

0,3

60

Трудоемкость (человеко-час)

1,2

1,5

371,4

Прибыль от реализации одного изделия (грн.)

6

8

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

Тип оборудования

Затраты времени (станко-часы) на обработку одного изделия вида:

Общий фонд рабочего времени оборудования (час.)

А

В

Фрезерное

10

80

168

Токарное

5

10

180

Шлифовальное

6

12

144

Прибыль от реализации одного изделия (грн.)

14

18

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

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

Вид заготовки

Количество заготовок (шт.) при раскрое

по способу 1

по способу 2

I

2

6

II

5

4

III

2

3

Величина отходов (см 2)

12

16

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

Вид корма

Количество единиц корма, которое ежедневно должны получать

Общее количество корма

Лисица

Песец

I

2

3

180

II

4

1

240

III

6

7

426

Прибыль от реализации одной шкурки (грн.)

16

12

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

  1.  Фирма имеет возможность рекламировать свою продукцию, используя местные радио- и телевизионную сеть. Затраты на рекламу в бюджете фирмы ограничены величиной 1000 грн. в месяц. Каждая минута радиорекламы обходится в 5 грн., а каждая минута телерекламы — в 100 грн. Фирма хотела бы использовать радиосеть по крайней мере в два раза чаще, чем сеть телевидения. Опыт прошлых лет показал, что объем сбыта, который обеспечивает каждая минута телерекламы, в 25 раз больше сбыта, обеспечиваемого одной минутой радиорекламы. Определите оптимальное распределение финансовых средств, ежемесячно отпускаемых на рекламу, между радио- и телерекламой.
  2.  Фирма производит два вида продукции — А и В. Объем сбыта продукции вида А составляет не менее 60% общего объема реализации продукции обоих видов. Для изготовления продукции А и В используется одно и то же сырье, суточный запас которого ограничен величиной 100кг. Расход сырья на единицу продукции А составляет 2 кг, а на единицу продукции В — 4 кг. Цены продукции А и В равны 20 и 40 грн. соответственно. Определите оптимальное распределение сырья для изготовления продукции А и В.
  3.  Фирма производит ковбойские шляпы двух фасонов. Трудоемкость изготовления шляп фасона А вдвое выше трудоемкости изготовления шляп фасона В. Если бы фирма выпускала только шляпы фасона А, суточный объем производства мог бы составить 500 шляп. Суточный объем сбыта шляп обоих фасонов ограничен диапазоном от 150 до 200 штук. Прибыль от продажи шляп фасона А равна 8 долл., а фасона В — 5 долл. Определите, какое количество шляп каждого фасона следует производить, чтобы максимизировать прибыль от их реализации?
  4.  Частная производственная фирма специализируется на производстве технических лаков. Представленная ниже таблица содержит информацию о ценах продажи и соответствующих издержках производства единицы полировочного и матового лаков.

Лак

Цена продажи 1 кг, грн.

Издержки производства 1 кг, грн.

Матовый

13

9

Полировочный

16

10

Для производства одного кг матового лака необходимо - 6 минут трудозатрат, а для производства одного кг полировочного лака — 12 минут. Резерв фонда рабочего времени 400 чел-часов в день. Размер ежедневного запаса необходимой химической смеси равен 100г, тогда как ее расход на 1 кг матового и полировочного лаков составляет 0,05 и 0,02г соответственно. Технологические возможности завода позволяют выпускать не более 3000 кг лака в день. В соответствии с соглашением с основным оптовым покупателем, компания должна поставлять ему 5000кг матового лака и 2500кг полировочного лака за каждую рабочую неделю (состоящую из 5 дней). Кроме того, существует профсоюзное соглашение, в котором оговаривается минимальный объем производства в день, равный 2000кг. Администрации данной компании необходимо определить ежедневные объемы производства каждого вида лака, которые позволяют получать максимальный общий доход в неделю.

  1.  Менеджер секции деликатесов крупного бакалейного магазина только что узнал, что в его отделе имеется 112 фунтов майонеза, из которых у 70 истекает срок хранения, и их нужно использовать. Чтобы реализовать майонез, менеджер решил производить два продукта: паштет из ветчины и деликатесный паштет. Для изготовления 1 лотка паштета из ветчины требуется 1,4 фунта майонеза, а для одного лотка деликатесного паштета — 1,0 фунта майонеза. Менеджер получил заказ на 10 лотков ветчинного паштета и 8 лотков деликатесного. Кроме того, он решил изготовить хотя бы по 10 лотков каждого продукта для запаса. Изготовление 1 лотка каждого продукта обходится в 3 долл., но при реализации лоток паштета из ветчины стоит 5 долл., а деликатесного паштета — 7 долл.

Найти решение, которое будет минимизировать затраты.

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

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

Вид заготовки

Количество заготовок (шт.) при раскрое

по способу 1

по способу 2

I

3

5

II

4

4

III

2

3

Величина отходов (см 2)

10

14

  1.  Менеджер секции деликатесов крупного бакалейного магазина только что узнал, что в его отделе имеется 112 фунтов майонеза, из которых у 70 истекает срок хранения, и их нужно использовать. Чтобы реализовать майонез, менеджер решил производить два продукта: паштет из ветчины и деликатесный паштет. Для изготовления 1 лотка паштета из ветчины требуется 1,4 фунта майонеза, а для одного лотка деликатесного паштета — 1,0 фунта майонеза. Менеджер получил заказ на 10 лотков ветчинного паштета и 8 лотков деликатесного. Кроме того, он решил изготовить хотя бы по 10 лотков каждого продукта для запаса. Изготовление 1 лотка каждого продукта обходится в 3 долл., но при реализации лоток паштета из ветчины стоит 5 долл., а деликатесного паштета — 7 долл.

Найти решение, которое будет максимизировать прибыль.

  1.  В цехе предприятия решено установить дополнительное оборудование, для размещения которого выделено 7 м2 площади.  На приобретение оборудования предприятие может израсходовать 10 тыс. грн. , при этом оно может купить оборудование 2-х видов. Комплект оборудования 1го вида стоит 2000 гривен, а 2го вида – 3000 гривен. Приобретение одного комплекта оборудования 1го вида позволяет увеличить выпуск продукции в смену на 3 единицы, а одного комплекта оборудования 2го вида – на 4 единицы. Зная, что для установки одного комплекта оборудования 1го вида требуется 2м2 площади, а оборудования 2го вида – 1,5 м2 площади, определить такой набор дополнительного оборудования, который дает возможность максимально увеличить выпуск продукции.
  2.  . Для изготовления изделий №1 и №2 склад может отпустить не более 80 кг металла, причем на изделие №1 расходуется 2 кг, а на изделие №2 – 1кг металла. Требуется спланировать производство так, чтобы была обеспечена наибольшая прибыль, если изделий №1 надо изготовить не более 30шт., а изделий №2 – не более 40шт., причем изделие №1 стоит 5 грн., а изделие № 2 – 3 грн.
  3.  Из пункта А в пункт В ежедневно отправляются пассажирские и скорые поезда. В таблице указаны количества вагонов различных типов, из которых ежедневно можно комплектовать поезда, и число пассажиров, на которые рассчитаны вагоны. Определить оптимальное число скорых и пассажирских поездов, при котором количество перевозимых пассажиров будет максимальным.

Тип

вагона

Парк вагонов, шт.

Кол-во вагонов (шт) каждого типа в составе:

Число пассажиров в одном вагоне, чел.

скором

пассажирском

багажный

12

1

1

-

почтовый

18

1

-

-

жесткий

88

4

8

58

купейный

79

6

4

40

мягкий

35

4

2

32

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

Тип

вагона

Парк вагонов, шт.

Кол-во вагонов (шт) каждого типа в составе:

Число пассажиров в одном вагоне, чел.

скором

пассажирском

багажный

12

1

1

-

почтовый

18

1

-

-

жесткий

88

4

8

58

купейный

79

6

4

40

мягкий

36

4

2

32

  1.  Предприятие располагает производственными мощностями (в часах)  четырех видов в следующем количестве: М1=16, М2=10, М3=6, М4=7. Нормы затрат мощностей каждого вида составляют на единицу продукции №1: 2, 1, 0, 1, на единицу продукции №2: 1, 1, 1, 0. Прибыль от реализации единицы продукции №1 равна 3 грн., от единицы продукции №2 – 4 грн. Составить план производства продукции двух видов, при котором доход предприятия от реализации всей продукции оказался бы максимальным.
  2.  Швейная мастерская изготавливает костюмы и платья из двух видов тканей. На платье расходуется ткани одного вида 1,5м2, второго – 0,5м2; на костюм, соответственно, 1,6м2 и 0,8м2. Доход от реализации одного платья – 3 грн., костюма – 5 грн.. Определить сколько платьев и костюмов надо сшить мастерской, чтобы добиться наивысшей рентабельности производства, если запас ткани первого вида 141м2, второго – 64 м2.
  3.  В некоторой больнице лечат два вида болезней: приступы и травмы позвоночника. Для лечения больных используют три вида ресурсов:
    •  одна хирургическая палата, которую можно использовать 2600 часов в год;
    •  один компьютерный томографический сканер, который можно использовать 2600 часов в год;
    •  40 мест, которые можно использовать 365 дней в году.

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

Ресурсы

Место (дни)

Томография (час)

Хирургия (час)

Приступы

4

1

0

Травмы

10

1

2

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

  1.  Частная производственная фирма специализируется на производстве технических лаков. Представленная ниже таблица содержит информацию о ценах продажи и соответствующих издержках производства единицы полировочного и матового лаков.

Лак

Цена продажи 1 кг, грн.

Издержки производства 1 кг, грн.

Матовый

13

9

Полировочный

16

10

Для производства одного кг матового лака необходимо - 6 минут трудозатрат, а для производства одного кг полировочного лака — 12 минут. Резерв фонда рабочего времени 400 чел-часов в день. Размер ежедневного запаса необходимой химической смеси равен 100г, тогда как ее расход на 1 кг матового и полировочного лаков составляет 0,05 и 0,02г соответственно. Технологические возможности завода позволяют выпускать не более 3000 кг лака в день. В соответствии с соглашением с основным оптовым покупателем, компания должна поставлять ему 5000кг матового лака и 2500кг полировочного лака за каждую рабочую неделю (состоящую из 5 дней). Кроме того, существует профсоюзное соглашение, в котором оговаривается минимальный объем производства в день, равный 2000кг. Администрации данной компании необходимо определить ежедневные объемы производства каждого вида лака, которые позволяют получать максимальную недельную прибыль.

  1.  Частная производственная фирма специализируется на производстве технических лаков. Представленная ниже таблица содержит информацию о ценах продажи и соответствующих издержках производства единицы полировочного и матового лаков.

Лак

Цена продажи 1 кг, грн.

Издержки производства 1 кг, грн.

Матовый

13

9

Полировочный

16

10

Для производства одного кг матового лака необходимо - 6 минут трудозатрат, а для производства одного кг полировочного лака — 12 минут. Резерв фонда рабочего времени 400 чел-часов в день. Размер ежедневного запаса необходимой химической смеси равен 100г, тогда как ее расход на 1 кг матового и полировочного лаков составляет 0,05 и 0,02г соответственно. Технологические возможности завода позволяют выпускать не более 3000 кг лака в день. В соответствии с соглашением с основным оптовым покупателем, компания должна поставлять ему 5000кг матового лака и 2500кг полировочного лака за каждую рабочую неделю (состоящую из 5 дней). Кроме того, существует профсоюзное соглашение, в котором оговаривается минимальный объем производства в день, равный 2000кг. Администрации данной компании необходимо определить ежедневные объемы производства каждого вида лака, позволяющие минимизировать суммарные издержки производства в неделю.

  1.  Менеджер секции деликатесов крупного бакалейного магазина только что узнал, что в его отделе имеется 112 фунтов майонеза, из которых у 70 истекает срок хранения, и их нужно использовать. Чтобы реализовать майонез, менеджер решил производить два продукта: паштет из ветчины и деликатесный паштет. Для изготовления 1 лотка паштета из ветчины требуется 1,4 фунта майонеза, а для одного лотка деликатесного паштета — 1,0 фунта майонеза. Менеджер получил заказ на 10 лотков ветчинного паштета и 8 лотков деликатесного. Кроме того, он решил изготовить хотя бы по 10 лотков каждого продукта для запаса. Изготовление 1 лотка каждого продукта обходится в 3 долл., но при реализации лоток паштета из ветчины стоит 5 долл., а деликатесного паштета — 7 долл.

Найти решение, которое будет максимизировать доход.

  1.  Менеджер секции деликатесов крупного бакалейного магазина только что узнал, что в его отделе имеется 112 фунтов майонеза, из которых у 70 истекает срок хранения, и их нужно использовать. Чтобы реализовать майонез, менеджер решил производить два продукта: паштет из ветчины и деликатесный паштет. Для изготовления 1 лотка паштета из ветчины требуется 1,4 фунта майонеза, а для одного лотка деликатесного паштета — 1,0 фунта майонеза. Менеджер получил заказ на 10 лотков ветчинного паштета и 12 лотков деликатесного. Кроме того, он решил изготовить хотя бы по 10 лотков каждого продукта для запаса. Изготовление 1 лотка каждого продукта обходится в 3 долл., но при реализации лоток паштета из ветчины стоит 5 долл., а деликатесного паштета — 7 долл.

Найти решение, которое будет максимизировать прибыль.

Задание 2. В трех пунктах производства А1, А2, А3 сосредоточен однородный груз в количествах соответственно равных а1, а2, а3 тонн. Данный груз потребляется в четырех пунктах В1, В2, В3, В4, а потребность в нем в этих пунктах составляют b1, b2, b3, b4, тонн соответственно. Известна матрица тарифов по перевозке 1 тонны груза из iго пункта производства в jй пункт потребления:

.

Составить план перевозок:

,

при котором суммарные транспортные расходы будут минимальными.


№ вар

ПАРАМЕТРЫ МОДЕЛИ

a1

a2

a3

b1

b2

b3

b4

c11

c12

c13

c14

c21

c22

c23

c24

c31

c32

c33

c34

1

25

50

20

15

15

40

30

1

8

2

3

4

7

5

1

5

3

4

4

2

46

30

35

20

30

16

10

1

2

6

3

4

8

1

5

9

7

3

4

3

60

70

20

30

30

30

50

2

4

5

1

2

3

9

4

3

4

22

5

4

30

20

40

50

20

20

15

5

2

4

1

3

5

6

7

11

5

3

1

5

45

15

20

30

25

25

10

9

4

1

4

5

6

7

10

2

1

4

3

6

60

65

70

40

60

70

30

2

4

3

2

3

1

2

3

5

4

1

5

7

50

40

20

30

25

25

20

3

2

4

1

2

3

1

5

3

2

7

4

8

20

10

40

35

25

10

15

4

1

2

6

5

3

4

8

2

5

1

4

9

50

10

10

25

25

20

10

5

6

4

2

1

5

3

8

1

2

4

1

10

45

25

20

30

15

30

40

2

1

5

1

4

2

6

3

1

5

2

4

11

60

70

10

40

25

35

20

5

4

1

2

6

3

1

2

4

5

3

2

12

25

25

30

20

25

25

15

4

8

6

7

2

1

5

1

1

3

5

4

13

20

20

40

30

25

15

20

6

4

1

2

5

8

3

1

5

4

2

6

14

60

10

40

30

40

20

10

1

2

4

5

6

8

2

3

2

5

7

1

15

30

50

20

15

10

40

30

3

1

5

6

4

2

1

5

3

7

4

5

16

45

35

70

20

60

55

55

6

1

4

5

2

3

2

1

4

5

2

3

17

30

70

50

10

40

20

60

5

1

4

2

6

3

8

2

4

5

1

3

18

70

10

20

45

10

35

20

6

1

5

4

2

3

2

5

4

7

9

2

19

20

50

40

45

20

45

5

4

5

3

2

8

4

1

6

2

5

4

1

20

30

20

45

25

25

30

20

1

5

3

4

2

1

5

7

4

2

1

4

21

60

10

50

30

40

40

25

5

1

9

3

2

7

5

6

1

2

4

3

22

30

70

20

65

15

30

5

6

4

2

1

4

5

3

8

5

1

3

5

23

50

40

60

35

45

50

30

2

4

1

5

3

2

5

6

7

4

5

9

24

40

30

20

25

35

25

15

1

5

2

4

8

3

6

7

4

2

1

5

25

50

40

60

40

60

25

35

2

4

1

9

8

3

6

10

2

4

5

7

26

20

30

50

45

25

20

15

6

4

1

5

7

10

2

3

5

6

11

2

27

25

35

50

30

10

30

25

5

8

4

3

1

2

7

5

2

1

2

6

28

50

40

20

20

40

30

25

2

4

5

8

9

7

3

1

6

2

5

2

29

25

45

30

40

20

25

20

6

4

5

8

1

2

3

7

5

1

2

4

30

30

20

45

25

25

30

20

8

7

5

1

2

12

4

5

8

6

2

4


Список рекомендуемой литературы

  1.  Акулич И.Л. Математическое программирование в примерах и задачах: Учеб. пособие для студентов эконом. спец. вузов. - М.: Высш. шк., 1986.-319с., ил.
  2.  Сакович В.А. Исследование операций (детерминированные методы и модели): Справочное пособие. - Мн.: Выш. шк., 1984.-256с.
  3.  Таха Х. Введение в исследование операций: в 2-х книгах. Кн.1. Пер. с англ. – М.: Мир, 1985.-479с., ил.
  4.  Методические указания к практическим занятиям по дисциплине «Математическое программирование» (линейное программирование) для студентов экономических специальностей / Сост. Туровцев Г.В., Нудный И.П. – Запорожье, ЗГИА, 1984.-31с.
  5.  Математическое программирование. Конспект лекций для студентов экономических специальностей дневного и заочного отделений /Глущевский В.В., Исаенко А.Н. – Запорожье: ЗГИА, 2003. – 150с.

Рис. 1 Представление исходных данных в таблицах EXCEL

Рис. 2 Программирование целевой ячейки

Рис. 3 Вызов функции СУММПРОИЗВ

Рис. 4 Вызов процедуры “Поиск решения”

Рис. 5 Экранная форма Поиск решения

Рис. 6 Экранная форма Добавление ограничения

Рис. 7 Экранная форма Параметры

Рис. 8 Результаты работы процедуры Поиск решения

EMBED PBrush  

Рис. 9 Отчет по устойчивости

EMBED PBrush  

Рис. 10 Начальная симплекс-таблица

EMBED PBrush  

Рис. 11 Результаты расчетов

EMBED PBrush  

Рис.12 Формулы расчета в таблицах EXCEL

Рис. 14 Программирование целевой ячейки

EMBED PBrush  

EMBED PBrush  

Рис. 13 Представление исходных данных в таблицах EXCEL

Рис. 15 Экранная форма Поиск решения

EMBED PBrush  

EMBED PBrush  

Рис. 16 Результаты работы процедуры Поиск решения

EMBED PBrush  

  1.  

 

А также другие работы, которые могут Вас заинтересовать

69114. Рядки. Поняття рядка та оголошення змінних рядкового типу. Операції над рядками та рядкові вирази. Процедури та функції обробки рядків 79 KB
  Один з різновидів одновимірних масивів — масив символів, або рядок, — посідає особливе місце у багатьох мовах програмування. І це не випадково, адже алгоритми перетворення рядків застосовуються для вирішення вкрай широкого кола задач: редагування та перекладу текстів, алгебричних перетворень формул...
69115. Записи. Запис та його оголошення. Доступ до компонентів та операцій над записами. Масиви записів. Записи з варіантами 100 KB
  Визначальною характеристикою масиву є однорідність, тобто однотипність його елементів. Проте реальний світ насичений неоднорідними структурами даних. Прикладами таких структур можуть стати: календарна дата, що скла-дається з номера дня, номера року та назви місяця...
69116. Множини. Поняття множин та множинного типу даних. Оголошення змінних множинного типу. Операції над множинами 96.5 KB
  Математичне поняття множини широко використовується в задачах, для яких існує ефективне програмне розв’язання. Так, у багатьох комбінаторних задач серед усіх підмножин деякої множини необхідно знайти ті, які задовольняють певну умову. При розв’язанні задач на графах користуються поняттями...
69117. Фізичний і логічний файли. Технологія роботи з файлами. Тинпи файлів і оголошення файлових змінних. Установка відповідності між фізичним і логічним файлами. Системні операції з файлами 141 KB
  Дані, що використовувались у задачах із попередніх розділів, існували протягом одного сеансу роботи певної програми. Такі дані зберігаються в оперативній пам’яті комп’ютера. Проте бльшість програм оперує із даними, що залишаються доступними як після завершення роботи програми, так і після перевантаження...
69118. Буферізація даних. Натипізовані файли 56 KB
  При зчитувані даних із файла зна чення його чергового компонента копіюється в поточний елемент буфера. У відповідь на цей запит операційна система виділяє буфер із буферного пула і в нього зчитується певна кількість блоків даних із фізичного файла.
69119. Динамічні змінні та динамічна пам’ять. Розподіл оперативної пам’яті. Поняття покажчика та його оголошення. Стандартні функції для роботи з адресами 93.5 KB
  Змінні величини, що розглядались у попередніх розділах, були статичними. Статичні змінні характеризуються тим, що їх значення зберігаютъся в ділянках оперативної пам’яті, які визначаються на етапі компіляції программ і не змінюються під час її виконання.
69120. Спискові структури даних. Визначення лінійного списку та його різновидів. Робота зі стеком, з чергою та лінійним списком 111 KB
  Визначення лінійного списку та його різновидів. Визначення лінійного списку та його різновидів 3. Визначення лінійного списку та його різновидів Як приклад розглянемо таку задачу. Кожен компонент списку крім останнього містить покажчик на наступний або на наступний попередній компонент.
69121. Дерева. Основні поняття. Алгоритм роботи з бінарними деревами 80 KB
  Розглянуті у розділі 10.2 списки, стеки та черги палежать до лінійних динамічних структур даних. Визначальною характеристикою лінійних структур є те, що зв’язок між іншими компонентами описується в терминах «попередній-наступний», тобто для кожного компонента лінійної структури...