ID: 4764

Название работы: Теория математического программирования в экономическом производстве

Категория: Конспект

Предметная область: Информатика, кибернетика и программирование

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

Язык: Русский

Дата добавления: 2012-11-25

Размер файла: 1.44 MB

Работу скачали: 19 чел.

Введение

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

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

Вначале изучается графический метод решения ЗЛП, позволяющий наглядно представить как суть математической постановки задачи, так и ее результат. Затем изучается решение задачи с использованием встроенного в Microsoft EXCEL for WINDOWS инструмента «Поиск решения». Этот инструмент позволяет решать более сложные задачи не только линейного программирования. Традиционный симплексный метод решения ЗЛП позволяет получить много результатов, полезных для экономического анализа рентабельности выпуска определенных видов продукции, анализа дефицитности используемых ресурсов, их взаимозаменяемости. Однако этот метод довольно трудоемкий. Решить эту проблему позволяет Microsoft EXCEL со своей встроенной возможностью модификации формул.

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

1. МЕТОДЫ РЕШЕНИЯ ЗАДАЧ

ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ

Задание 1. Построить математическую модель экономической задачи. Решить задачу с помощью построенной модели

1.  графическим методом,
   1.  с использованием инструмента “Поиск решения”,
   2.  симплексным методом.

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

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

Разберем решение одной задачи оптимального производственного планирования (или задачи об использовании ресурсов).

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

Ресурсы	Нормы расхода ресурсов на одно изделие		Общий запас ресурсов
		№1		№2
Рабочее время (чел.-час.) Кожа I  сорта (лоскут) Кожа II сорта (лоскут)	1 3 -	2 1 3	900 900 1200
Прибыль (грн.)	50	70

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

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

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

пар обуви – недельный план  выпуска модели №1,

пар обуви – недельный план выпуска модели №2.

Целевая функция задачи. Так как прибыль от выпуска 1 пары обуви модели №1 составляет 50 грн., а модели №2 – 70 грн., то общая недельная прибыль при выпуске  пар обуви модели №1 и  пар обуви модели №2 составит  (грн.). Таким образом, целевая функция задачи, которую необходимо максимизировать, имеет вид

.

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

•  Рабочее время, затрачиваемое на выпуск запланированной обуви, составит  (чел.-час.). С учетом общего фонда рабочего времени в 900 чел.-час., который нельзя превысить, получим неравенство:

.

•  Расход кожи I  сорта (в лоскутах) на изготовление запланированной партии обуви представится по аналогии с предыдущим неравенством:

.

•  Расход кожи II  сорта (в лоскутах) – соответственно:

.

Если обе части последнего неравенства разделить на 3, то получим:

.

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

.

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

пар обуви – недельный план  выпуска модели №1,

пар обуви – недельный план выпуска модели №2,

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

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

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

,     (1)

,     (2)

.     (3)

Для этого найдем по две пары точек, через которые проходит каждая из этих прямых:

1.  :  (0, 450),  (900, 0);

2.  :  (0, 900),  (300, 0);

3.   : (0, 400),  (500, 400).

Эти прямые с соответствующими метками изображены на рис. 1.1.

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

Рис. 1.1 - Решение задачи линейного программирования графическим методом

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

.

Для изображения этого вектора соединяем направленным отрезком точки с координатами (0, 0) и (500, 700). Произвольная линия уровня целевой функции (L)  проходит перпендикулярно к вектору .

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

.

Из первого уравнения выразим :

.      (4)

Затем подставим найденное выражение во второе уравнение:

,

откуда получим

Зная , с помощью (4) находим :

.

В результате приходим к выводу, что , а точка, соответствующая оптимальному решению, имеет координаты . Максимальное значение целевой функции:

(грн.).

Ответ. Для получения максимальной недельной прибыли, составляющей 34200 грн., фабрика должна выпускать 180 пар обуви модели №1 и 360 пар обуви модели №2 в неделю.

1.2 Решение задач линейного программирования с помощью инструмента “Поиск решения”

Согласно математической модели поставленной задачи подготовим лист EXCEL для применения инструмента «Поиск решения» (см. рис. 1.2):

1.  ячейки В2:С2 резервируем для оптимальных значений переменных  и  (оптимального плана задачи), которые будут найдены как результат применения процедуры «Поиск решения»;
2.  ячейку D3 резервируем для значения целевой функции на оптимальном плане;
3.  в ячейки В3:С3 вносим значения коэффициентов целевой функции;
4.  ячейки В5:С5, В6:С6, В7:С7 заполняем коэффициентами при переменных в левой части соответствующих ограничений;
5.  в ячейки F5:F7 записываем значения правых частей соответствующих ограничений;
6.  в ячейки Е5:Е7 вносим знак неравенства в соответствующем ограничении;
7.  ячейки D5:D7 резервируем для значений левых частей системы ограничений на оптимальном плане.

Внесем формулы, заметив, что значение целевой функции (ячейка D3) равно сумме произведений неизвестных значений переменных (ячейки В2:С2) на коэффициенты целевой функции (ячейки В3:С3), а значения левых частей системы ограничений (ячейки D5, D6 и D7) равны сумме произведений неизвестных значений переменных (ячейки В2:С2) на коэффициенты левых частей системы ограничений (ячейки В5:С5, В6:С6, В7:С7 соответственно). Для этого в целевую ячейку D3 вносим формулу

СУММПРОИЗВ($D$2;$C$2;B3;C3),

которую копируем в ячейки D5, D6 и D7 с модификациями.

Для внесения в ячейку D3 указанной формулы необходимо

1.  поставить курсор в ячейку D3;
2.  вызвать “Мастер функций” с помощью кнопки  (см. рис. 1.2);

а)      б)

Рис. 1.3 - Экранная форма «Мастер функций»

1.  среди встроенных категорий мастера функций выбрать «Математические» (рис. 1.3, а);
2.  среди выбираемых функций этой категории отметить
   «СУММПРОИЗВ» (рис. 1.3, б) и нажать «ОК»;
3.   в появившейся экранной форме (см. рис. 1.4) поставить курсор в «Массив 1», выделить на листе EXEL ячейки В2:С2 (соответствующие зарезервированным значениям переменных), затем присвоить им абсолютные адреса нажатием функциональной клавиши F4; перевести курсор в «Массив 2» и выделить на листе EXEL ячейки В3:С3 (соответствующие значениям коэффициентов целевой функции).

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

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

Рис. 1.5 - Программирование ячеек, соответствующих значению целевой функции и значениям левых частей системы ограничений

Если перечень процедур «Сервис» в меню Microsoft EXEL не содержит инструмент «Поиск решения», то для добавления этого инструмента в перечень необходимо віполнить следующие действия:

1) нажать «Сервис», затем «Надстройки» (рис. 1.6 а);

2) в появившейся экранной форме отметить «Поиск решения» (рис. 1.6, б).

а)                                                                            б) Рис. 1.6 - Добавление процедуры «Поиск решения» в меню «Сервис» Microsoft EXEL

В результате проделанных операций лист EXEL готов для запуска процедуры «Поиск решения». Выбираем в “Сервис” процедуру “Поиск решения” (см. рис. 1.7).

Рис. 1.7 - Запуск процедуры «Поиск решения»

В появившейся экранной форме «Поиск решения» (см. рис 1.8)

1)  устанавливаем целевую ячейку $D$3, отмечая её на листе EXEL;

2) отмечаем флажком тип оптимизации, исходя из условий задачи: в данном случае – это максимизация;

3) переводим курсор в «Изменяя ячейки» и выделяем на листе EXEL ячейки $В$2:$С$2, соответствующие зарезервированным значениям переменных;

4) переводим курсор в «Ограничения», нажимаем «Добавить»;

Рис. 1.8 - Экранная форма «Поиск решения»

Рис. 1.9 -  Экранная форма «Добавление ограничений»

Рис. 1.10 - Экранная форма «Параметры поиска решений»

5) в появившейся экранной форме «Добавление ограничений» (рис. 1.9)

а) делаем ссылки на ячейки (путем их выделения на листе EXEL), соответствующие левым частям системы ограничений $D$5:$D$7; эти ячейки содержат результат вычислений согласно введенным ранее формулам;

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

в) переводим курсор в «ограничение», ссылаясь на ячейки, соответствующие правым частям системы ограничений $F$5:$F$7, выделяя их на листе EXEL;

г) нажатие «ОК» возвращает нас в экранную форму «Поиск решение»;

6) нажимаем «Параметры», в появившейся экранной форме (рис. 1.10) отмечаем флажками «Линейная модель» и «Неотрицательные значения», после чего нажатие «ОК» возвращает нас к экранной форме «Поиск решения»;

7) нажимаем «Выполнить», в результате чего (рис. 1.11) на листе EXEL в ячейках В2:С2 высвечиваются искомые значения оптимальных переменных (оптимальный план), в ячейке D3  значение целевой функции на оптимальном плане, а в появившейся экранной форме, «Результаты поиска решения», предлагается сделать один из видов отчета, из которых выбираем отчет по устойчивости и нажимаем «ОК». Лист отчета по устойчивости представлен на рис. 1.12.

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

Рис. 1.12 - Экрана форма листа «Отчет по устойчивости»

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

Шаг 1. Выпишем математическую модель исходной задачи:

пар обуви – недельный план  выпуска модели №1,

пар обуви – недельный план выпуска модели №2,

Шаг 2. Приведем математическую модель исходной задачи к каноническому виду, вводя дополнительные неотрицательные переменные . Заметим, что количество дополнительных переменных соответствует количеству неравенств в системе ограничений. Так как все неравенства системы ограничений выражаются знаком «≤», то дополнительные переменные в систему ограничений войдут с коэффициентом «+1». В целевую же функцию они войдут с коэффициентом «0». Канонический вид записи данной задачи:

   (5)

Шаг 3. Приведение системы ограничений к предпочтительному виду.

Во-первых, все свободные элементы системы (5) – неотрицательные. Во-вторых, основная матрица системы (5)

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

Шаг 4. Составляем первую симплексную таблицу.

•  Заносим исходные данные в таблицу EXEL (см. первую симплексную таблицу на рис. 1.13 и 1.14):

1.  в ячейки D3:H3 вносим наименования переменных;
2.  в ячейки D2:H2 – коэффициенты целевой функции при соответствующих переменных;
3.  в ячейки D4:H6 – основную матрицу системы (5);
4.  в ячейки А4:А6 – наименования базисных переменных;
5.  в ячейки В4:В6 – коэффициенты целевой функции при базисных переменных;
6.  в ячейки С4:С6 – столбец свободных элементов.
   •  Найдем опорный план, соответствующий построенной симплекс-таблице. Для этого поставим в соответствие переменной базиса значение, находящее в столбце «» той же строки. Если переменная не входит в базис, то ее значение равно нулю. В данном случае

,

•  Заполняем ячейки С7:Н7:

1) ячейка С7 должна  содержать значение целевой функции на указанном опорном плане:

,

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

2) ячейки D7 – H7 должны содержать значения оценок оптимальности для указанного опорного плана:

,   ;

поэтому в ячейку D7 вносим формулу (см. рис. 1.14)

СУММПРОИЗВ($B$4:$B$6;D4:D6)-D2,

в которой ячейки В4:В6 имеют абсолютные значения, по той причине, что в формуле для  коэффициенты целевой функции , участвующие в суме произведений не зависят от . Затем копируем формулу с модификациями в ячейки E7:H7; результаты вычислений в этих ячейках показаны на рис. 1.13.

•  Проверка оптимальности опорного плана. Оценки оптимальности  содержат отрицательные значения (см. первую симплексную таблицу на рис. 1.13), поэтому указанный опорный план не является оптимальным. Выбираем среди оценок оптимальности наибольшее по модулю отрицательное значение. В данном случае – это «-70». Столбец, соответствующий этому значению оптимальности, является разрешающим столбцом; выделим его.
•  В ячейки I4:I6 вносим значения оценочных ограничений. Для й строки оценочное ограничение равно , где   свободный элемент этой строки, а   элемент матрицы, находящейся в разрешающем столбце й строки (см. рис. 1.14). Если =0 или , то оценочное ограничение такой строки не рассматриваем. Из положительных оценочных ограничений выбираем наименьшее. В данном случае – это «400» (см. рис. 1.13). Строка, соответствующая этому значению, является разрешающей строкой; выделим её. Элемент, стоящий на пересечении разрешающей строки и разрешающего столбца называется разрешающим элементом.

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

Во-первых, переменную  вводим в базис вместо переменной .

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

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

, ,  при ;    (*)

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

, при .   (**)

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

Согласно указанному алгоритму строим вторую симплексную таблицу.

•  Заполняем таблицу EXEL (см. вторую симплексную таблицу на рис. 1.13 и 1.14):

1) первые две строки симплексной таблицы не изменяются;

2) переменную   вводим в базис вместо переменной ;

3) в ячейках В11:В13 помещаем коэффициенты при базисных переменных; 

4) для заполнения ячеек С11:Н13 формулами (см. рис. 1.14) согласно соотношениям (*) и (**) вносим первоначально формулы в ячейки С11:С13 и копируем их с модификациями.

Заметим, что в ячейки С14:Н14 можно внести как формулы, аналогичные ячейкам С11:Н11 или С12:Н12 (см. рис. 1.14), так и формулы, аналогичные С7:Н7. Результат будет один и тот же.

•  Опорный план, соответствующий второй симплекс-таблице:

,

а значение целевой функции на нем  грн.

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

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

,

а значение целевой функции на нем  грн. – максимальным.

Ответ. Для получения максимальной недельной прибыли, составляющей 34200 грн., фабрика должна выпускать 180 пар обуви модели №1 и 360 пар обуви модели №2 в неделю.

Рис. 1.13 Результаты расчетов симплексным методом

Рис.1.14- Формулы расчета симплексного метода в таблицах EXCEL

2. ДВОЙСТВЕННАЯ ЗАДАЧА

ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ

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

2.1 Математическая модель двойственной задачи

Выпишем математическую модель прямой (исходной) задачи:

пар обуви – недельный план  выпуска модели №1,

пар обуви – недельный план выпуска модели №2,

Составим математическую модель двойственной задачи.

1) Данная прямая задача на максимум, в ней все неравенства системы ограничений имеют знак «≤», поэтому изменять форму записи математической модели прямой задачи нет необходимости.

2) Выпишем расширенную матрицу системы и строку коэффициентов целевой функции

.

3) Составляем транспонированную матрицу

.

4) Составляем математическую модель двойственной задачи

.

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

грн. – теневая цена 1 чел.-часа рабочего времени,

грн. – теневая цена 1 лоскута кожи I сорта;

грн. – теневая цена 1 лоскута кожи I сорта.

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

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

Шаг 1. Приведем математическую модель двойственной задачи к каноническому виду, вводя дополнительные неотрицательные переменные .  Поскольку все неравенства системы ограничений выражаются знаком «≥», то дополнительные переменные войдут в систему ограничений с коэффициентом «-1». В целевую функцию дополнительные переменные всегда входят с коэффициентом «0». Так как двойственная задача на минимум, то составим вспомогательную функцию . Канонический вид записи двойственной задачи:

.    (6)

Шаг 3. Приведение системы ограничений к предпочтительному виду.

Поскольку основная матрица системы (6)

не содержит единичную подматрицу, то система (6) не имеет предпочтительного вида. Поэтому введем неотрицательные искусственные переменные , которые включим в целевую функцию с коэффициентами «-10000». Абсолютная величина коэффициентов должна быть на порядок выше всех абсолютных величин коэффициентов целевой функции. В результате составим математическую модель расширенной задачи:

.   (7)

Итак, имеем: во-первых, все свободные элементы системы (7)  неотрицательные; во-вторых, основная матрица системы (7)

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

Рис. 2.1 Результаты вычислений методом искусственного базиса)

Рис.2.2 Формулы расчета метода искусственного базиса в таблицах EXCEL

Шаг 5. Решаем полученную задачу симплексным методом по алгоритму, описанному в п. 1.3. Соответствующие симплексные таблицы задачи и образцы формул для EXEL приведены на рис. 2.1 и рис. 2.2 соответственно.

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

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

,

а значение функции   максимальным. Поскольку , то

грн.

2.3 Экономический анализ результатов

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

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

Сравнение результатов, полученных разными способами. 

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

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

Целевые функции прямой и двойственной задач. Из теорем о связи между решениями прямой и двойственной задач следует, что минимальное значение целевой функции двойственной задачи  должно совпадать с максимальным значением целевой функции прямой задачи . В данном случае

==34200 грн.     (8)

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

Основные переменные прямой задачи. Для получения максимальной прибыли, фабрика должна выпускать  пар обуви модели №1 и  пар обуви модели №2 в неделю.

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

1) , поэтому ресурс рабочего времени дефицитен, и его увеличение выгодно (рентабельно), а именно: увеличение рабочего времени на
1 чел.-час. приведет к увеличению прибыли на 32 грн.;

2) , поэтому ресурс кожи I сорта является дефицитным, и его увеличение рентабельно, а именно: увеличение запаса кожи I сорта на 1 лоскут даст предприятию прибыль, составляющую 6 грн.;

3) , поэтому ресурс кожи II сорта не является дефицитным, а увеличение его запаса нерентабельно.

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

1. Третья (дополнительная) переменная  соответствует первому ограничению, причем  чел.–час., поэтому ресурс рабочего времени использован полностью, что свидетельствует о его дефицитности.

2. Четвертая переменная  соответствует второму ограничению, причем  лоскутов, поэтому ресурс кожи I сорта использован полностью, значит и  этот ресурс дефицитен.

3. Пятая переменная  соответствует третьему ограничению, и  лоскутов, поэтому 40 лоскутов кожи II сорта не использованы, значит этот ресурс недефицитен.

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

В данной задаче переменная  соответствует объему выпуска обуви модели №1, а   модели №2, причем , поэтому выпуск обеих видов изделий выгоден (рентабелен).

Взаимозаменяемость ресурсов. В следующую таблицу внесем значения коэффициентов  взаимозаменяемости ресурсов.

i \ k	1	2	3
1	1	3/16	0
2	5 ⅓	1	0
3	∞	∞	1

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

Коэффициенты  и  равны ∞. Это означает, что заменить уменьшение дефицитных ресурсов рабочего времени или ресурса кожи I сорта недефицитным ресурсом кожи II сорта не возможно.

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

3. МЕТОДЫ РЕШЕНИЯ ТРАНСПОРТНОЙ ЗАДАЧИ

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

.

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

,

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

Решить поставленную транспортную задачу

3.1 методом потенциалов,

3.2 с помощью инструмента «Поиск решения».

Рассмотрим поставленную задачу для следующих исходных данных:

30т, 20т, 40т,

20т, 30т, 20т, 30т,

.

Запишем их в виде таблицы.

Таблица 3.1

Пункты производства	Пункты потребления				Запасы
	3	1	4	2	30
	1	4	3	3	20
	2	2	4	4	40
Потребности	20	30	20	30	90 100

В нижнем правом углу этой таблицы внесем значения суммарных потребностей и суммарных затрат:

т, т.

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

Сбалансируем данную задачу, вводя фиктивный пункт производства  с запасом груза =100-90=10(т). При этом стоимость перевозок из этого пункта в любой из пунктов потребления равна 0 (см. табл. 3.2).

Таблица 3.2

Пункты производства	Пункты потребления				Запасы
	3	1	4	2	30
	1	4	3	3	20
	2	2	4	4	40
	0	0	0	0	10
Потребности	20	30	20	30	100 100

Составим математическую модель данной задачи.

1.  Переменные задачи: – планируемый объем перевозки (в тоннах) из го пункта производства в й пункт потребления (,). Совокупность переменных  образует матрицу

.

1.  Целевая функция задачи выражает транспортные расходы, которые необходимо минимизировать:

.

1.  Ограничения задачи: на вывоз груза

,     (9)

на удовлетворение потребностей в грузе

,     (10)

    неотрицательность переменных:

(,).      (11)

Совокупность переменных , удовлетворяющих ограничениям (9)-(11), образует допустимый опорный план. Матрица системы (9)  (10) имеет ранг на 1 меньший количества строк этой системы, то есть на 1 меньший суммы количеств пунктов производства и пунктов потребления, в данном случае это – 7. Это означает, что количество базисных переменных должно быть равно 7.

3.1 Метод потенциалов решения транспортной задачи

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

Таблица 3.3  Нулевая итерация транспортной задачи

														Запасы
		1			1			1			1
	0			3			1			4			2		30|0
				-2			30			-3			-1
			0			1			4			3				3	20|0
				20			-3			-2			-2
			3			2			2			4				4	40|20|0
															Ө
				2			2			20			20
			-1			0			0			0				0	10|0
					Ө
				0			0			0			10
Потребности		20          0			30         0			20         0			30        20         0

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

1.  Выбираем ячейку с наименьшей стоимостью (транспортным тарифом). Наименьшая стоимость равна 0, а ячеек, соответствующих этой стоимости  четыре: , , , . Загрузим, к примеру, ячейку  так, чтобы . Пересчитаем оставшиеся запасы =10-10=0 и оставшиеся потребности =30-10=20, а полученные значения запишем в соответствующих ячейках таблицы через черту.
2.  Поскольку запасы четвертого пункта производства исчерпаны, то загружать ячейки строки  пока не будем. Среди оставшихся ячеек выберем ячейки с наименьшей стоимостью. Имеем две ячейки со стоимостью 1. Загрузим вначале, например, ячейку : . Пересчитаем оставшиеся запасы  и оставшиеся потребности =3030=0. Затем загрузим ячейку : , 20-20=0, =2020=0.
3.  На данный момент исчерпаны запасы пунктов производства ,  и , а также удовлетворены потребности потребителей  и . В нашем распоряжении остались две ячейки с одинаковыми стоимостями:   и . Загрузим, например, ячейку :  , , = =20-20=0. Теперь загрузим ячейку : , , =20-20=0.
4.  Загруженные ячейки соответствуют базисным переменным транспортной задачи, их количество на данный момент равно 5, однако, как было отмечено выше, должно быть равно 7. Недостающие два элемента пополняем, загружая нулевым объемом перевозки две свободные ячейки с наименьшими тарифами. Причем необходимо позаботиться о том, чтоб ни одна из этих ячеек не образовывала цикла с имеющимися загруженными ячейками. Под циклом понимают замкнутую ломаную с прямыми углами преломления в вершинах. В качестве таких ячеек выберем  и .
5.  Опорный план нулевой итерации образует матрицу

.

Его элементы удовлетворяют системе ограничений (9)-(11). Значение целевой функции на этом плане равно

(у.е).

Является ли этот план оптимальным? Ответ на этот вопрос дает метод потенциалов.

Шаг 2. Проверка оптимальности опорного плана.

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

(,).    (12)

Так как базисных переменных 7, то совокупность равенств (12) образует систему из 8 уравнений с 7 неизвестными. Эта система имеет бесконечное множество решений, найдем одно из них:

•  для удобства возьмем ;
•  в строке  находится базисная переменная , поэтому согласно (12) ;
•  в столбце  находится еще одна (кроме ) базисная переменная , поэтому ;
•  по базисной переменной  найдем  ,
•  по базисной переменной     ;
•  по базисной переменной     ;
•  по базисной переменной     ;
•  по базисной переменной     .

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

(,),

а результат заносить в нижние левые углы ячеек  (,), отделяя их в рамку:

,

,

,

,

,

,

,

,

.

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

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

Шаг 3.

1.  Определим переменную, вводимую в базис. Среди найденных оценок оптимальности выберем наибольшее положительное значение. Таковым является 2, что соответствует 2. В базис необходимо вводить ту из переменных  или  , которой отвечает меньший тариф. В данном случае . Поэтому введем в базис любую из этих переменных, например, .
2.  Определим переменную, выводимую из базиса. Для этого построим цикл, проходящий через некоторые из загруженных ячеек и ячейку  (соответствующую вводимой в базис переменной ). Напомним, что под циклом понимают замкнутую ломаную с прямыми углами преломления в вершинах. Известно, что цикл в транспортной задаче можно построить единственным образом. В данном случае цикл выглядит так, как это показано в табл. 3.3. Вершину цикла в ячейке  отмечаем знаком «+», а далее остальные вершины обозначаем чередующимися знаками «-» или «+», последовательно передвигаясь по циклу в любом направлении. Среди ячеек, в которые попал знак «-», выбираем ячейку с наименьшим значением базисной переменной. В данном случае это значение равно нулю, оно обведено ромбом, а соответствует оно базисной переменной , которую будем выводить из базиса.
3.  Построение нового базиса.

Подготовим новую таблицу первой итерации (см. табл. 3.4).

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

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

,   (у.е).

Таблица 3.4  Первая итерация транспортной задачи

	-1			1			1			1
0			3			1			4			2	30
		-4			30			-3			-1
	2			1			4			3				3	20
		20			-1			0			0
	3			2			2			4				4	40
												Ө
		0			2			20			20
	-1			0			0			0				0	10
						Ө
		-2			0			0			10
	20			30			20			30

Является ли новый опорный план оптимальным? Для ответа на этот вопрос возвращаемся к шагу 2 и шагу 3, выполняя последовательно аналогичные действия. Результаты этих действий занесены в табл. 3.4.

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

Таблица 3.5  Вторая итерация транспортной задачи

	1			1			3			3
0			3			1			4			2	30
						Ө
		-2			30			-1			1
	0			1			4			3				3	20
		20			-3			0			0
	1			2			2			4				4	40
												Ө
		0			0			20			20
	-3			0			0			0				0	10
		-2			-2			0			10
	20			30			20			30

Для опорного плана второй итерации получим

,   (у.е).

Возвращаемся к шагу 2 и шагу 3, результаты выполненных действий занесены в табл. 3.5. Опорный план второй итерации не оптимален. Вводимая в базис переменная в этом случае – , а выводимая из базиса  . Заметим, что при построении таблицы третьей итерации (табл.3.6) значения переменных, задействованных циклом, пересчитываем, добавляя к тем из них, которые отмечены знаком «+» значение переменной, выводимой из базиса (то есть «20»), а из переменных, отмеченных знаком «-», вычитаем это значение. Вводимая в базис переменная принимает значение 20. Ячейка  окажется свободной.

Для опорного плана третьей итерации получим

,

(у.е).

Таблица 3.6  Третья итерация транспортной задачи

	1			1			3			2
0			3			1			4			2	30
						Ө
		-4			10			-1			20
	0			1			4			3				3	20
		20			-3			0			-1
	1			2			2			4				4	40
									Ө
		0			20			20			-1
	-2			0			0			0				0	10
												Ө
		-1			-1			1			10
	20			30			20			30

Из табл. 3.6 видим, что опорный план третьей итерации не оптимален. Вводимая в базис переменная в этом случае – , а выводимая из базиса  . Проводим пересчет базисных переменных. Результаты вычислений в четвертой итерации занесены в табл. 3.7. Для опорного плана этой итерации выполнено условие оптимальности: все оценки оптимальности неположительны.

В результате имеем

,

(у.е).

Таблица 3.7  Четвертая итерация транспортной задачи

	0			0			2			2
0			3			1			4			2	30
		-3			-1			-2			30
	1			1			4			3				3	20
		20			-3			0			0
	2			2			2			4				4	40
		0			30			10			0
	-2			0			0			0				0	10
		-2			-2			10			0
	20			30			20			30

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

Ответ. Наименьшие суммарные транспортные расходы, составляющие 180 у.е. будут соответствовать такому плану перевозок:

•  из пункта производства  необходимо перевозить 30 т груза в пункт потребления ;
•  из пункта производства   20 т груза в пункт потребления ;
•  из пункта производства   30 т груза в пункт потребления  и 10 т – в .

Так как пункт  является фиктивным, то потребитель останется не удовлетворен на 10 т груза.

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

.

3.2 Решение транспортной задачи с использованием инструмента “Поиск решения”

Транспортная задача уже была сведена к закрытой модели. Результат внесен в табл. 3.2. Согласно этой таблице подготовим лист EXCEL для применения инструмента «Поиск решения» (см. рис. 3.1).

1.  Ячейки В4:Е7 заполняем матрицей транспортных тарифов транспортной задачи, приведенной к закрытому виду.
2.  В ячейках F4:F7 записываем объемы запасов  на предприятии  ().
3.  В ячейках В8:Е8 вносим объемы потребностей  потребителя  ().
4.  Ячейки B11:E14 резервируем для значений переменных модели, которые будут найдены после выполнения процедуры «Поиск решения»;
5.  Ячейка F15 (целевая ячейка) резервируется для вычисления оптимального значения целевой функции модели.

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

После заполнения исходных данных в целевую ячейку F15 вносим формулу СУММПРОИЗВ(В4:Е7; B11:E14), в ячейку F11 – СУММ(В11:Е11), которую копируем с модификациями в ячейки F12:F14, и в ячейку В15 – СУММ(В11:В14), которую копируем с модификациями в ячейки С15:Е15. Результат представлен на рис. 3.2.

Рис. 3.2  Формулы расчета в таблице EXEL

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

Рис. 3.4  Результаты работы процедуры «Поиск решения» (первый вариант)

Таким образом, все подготовительные процедуры закончены, поэтому выбираем в «Сервис»  инструмент «Поиск решения». Заполняем появившуюся экранную форму так, как это показано на рис. 3.3, выполняя действия, аналогичные описанным в п. 1.2.

Результат решения транспортной задачи с использованием инструмента «Поиск решения» представлен на рис. 3.4.. Оптимальное решение транспортной задачи в этом случае можно представить матрицей

,

а минимальное значение целевой функции на этом плане равно

(у.е).

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

,

Минимальное значение целевой функции при этом не изменяется, а именно:

(у.е).

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

Рис. 3.5  Результаты работы процедуры «Поиск решения» (второй вариант)

Ответ. Наименьшие суммарные транспортные расходы составляют 180 у.е. Это отвечает двум вариантам плана перевозок. Первый вариант:

•  из пункта производства  необходимо перевозить 30 т груза в пункт потребления ;
•  из пункта производства   20 т груза в пункт потребления ;
•  из пункта производства   30 т груза в пункт потребления  и 10 т – в ;
•  при этом плане потребитель останется не удовлетворен на 10 т груза.

Второй вариант:

•  из пункта производства  необходимо перевозить 30 т груза в пункт потребления ;
•  из пункта производства   10 т груза в пункт потребления  и 10 т – в ;
•  из пункта производства   10 т груза в пункт потребления  и 30 т – в ;
•  при этом плане потребитель останется не удовлетворен на 10 т груза.

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

Задание 1. Построить математическую модель экономической задачи. Решить задачу с помощью построенной модели

1.  с использованием инструмента “Поиск решения”,
   1.  графическим методом,
   2.  симплексным методом.

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

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

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

Ресурсы	Нормы расхода ресурсов на одно изделие		Общий объем ресурсов
		А		В
Доски (м2)	3	4	1700
Машинное время (час.)	0,2	0,5	160
Прибыль от реализации одного изделия (грн.)	20	40

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

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

Машина вида	Время обработки единицы изделия (час.)		Общий объем машинного времени (час.)
		А		В
I II III	0,5 0,4 0,2	0,25 0,3 0,4	40 36 36
Прибыль от реализации одного изделия (грн.)	50	30

Фирме надо определить план выпуска изделий А и В, при котором прибыль от их реализации будет максимальной.

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

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

Ресурсы	Нормы затрат ресурсов на одно изделие		Общий объем ресурсов
		стол		шкаф
Древесина (м3):
I вида	0,2	0.1	40
II вида	0.1	0,3	60
Трудоемкость (чел.-час.)	1,2	1,5	371,4
Прибыль от реализации одного изделия (грн.)	120	160

1.  На промышленном комплексе по производству мяса откармливают свиней двух пород. Все данные представлены в таблице.

Виды корма	Требуемое количество корма (ц) для породы свиней		Запасы корма, ц
		I		II
Грубые (сенная мука, травяные)	2	3	1000
Сочные (корнеплоды, картофель)	4	2	1200
Комбикорма	1	1	380
Продуктивность, ц	3	2,5

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

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

Тип оборудования	Затраты времени (станко-часы) на обработку одного изделия вида:		Общий фонд рабочего времени оборудования (час.)
		А		В
Фрезерное Токарное Шлифовальное	1 0,5 0,6	0,8 0,1 1,2	168 180 144
Прибыль от реализации одного изделия (грн.)	140	180

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

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

Вид сырья	Нормы расхода сырья (кг) на одно изделие		Общий объем сырья (кг)
		А		В
I II III	12 4 3	4 4 12	300 120 252
Прибыль от реализации одного изделия (грн.)	30	40

1.  В цехе по производству консервированных фруктов изготавливаются два вида компотов из трех видов фруктов (яблоки, груши и сливы). Перед отправкой в торговую сеть компоты разливают в банки: компот I вида – в 5-литровые, II вида – в 3-литровые. Все данные, необходимые для решения задачи, приведены в таблице.

Фрукты	Расход фруктов (кг) для компота вида		Запас, кг
		I		II
Яблоки	1	0,5	200
Груши	0,3	0,25	65
Сливы	0,75	1	200
Прибыль от реализации 1 банки компота, грн.	3	2

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

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

Ресурсы	Нормы расхода ресурсов на одно изделие		Общий объем ресурсов
		А		В
Доски (м2)	2	3	1200
Машинное время (час.)	0,2	0,5	160
Прибыль от реализации одного изделия (грн.)	30	40

Сколько полок каждого типа следует выпускать в неделю, чтобы прибыль от их реализации была наибольшей?

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

Вид корма	Количество единиц корма, которое ежедневно должны получать		Общий объем корма
		лисица		песец
I	2	3	180
II	4	1	240
III	6	7	426
Прибыль от реализации одной шкурки (грн.)	320	240

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

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

Тип оборудования	Производительность (т/час.)  вида продукции		Фонд времени (час.)
		А		Б
Плавильная печь Травильный агрегат Прокатный стан	7 6 2	6 4 1	4200 3000 900
Прибыль от реализации       1 т продукции (тыс. грн.)	4	3

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

1.  В цехе предприятия решено установить дополнительное оборудование двух видов – I и II. Площадь, необходимая для установки одного комплекта оборудования соответствующего вида, цена такого комплекта, а также общий объем ресурсов (производственных площадей и денежных ресурсов), выделяемых предприятием, приведены в таблице.

Ресурсы	Нормы расхода ресурсов на один комплект оборудования вида		Общий объем ресурсов в день
		I		II
Производственные площади (м2)	2	1,5	7
Денежные ресурсы (тыс. грн)	2	3	10

Приобретение одного комплекта оборудования 1го вида позволяет увеличить выпуск продукции в смену на 3 единицы, а одного комплекта оборудования 2го вида – на 4 единицы. Определить такой набор дополнительного оборудования, который дает возможность максимально увеличить выпуск продукции.

1.  Предприятие располагает производственными мощностями четырех видов. Нормы затрат мощностей (в часах) каждого вида на единицу продукции каждого их двух типов, общий запас таких мощностей и прибыль от реализации единицы продукции №1 и №2 приведены в таблице.

Мощности (в час.)	Нормы затрат мощностей (в часах) на единицу продукции типа		Общий запас мощностей (час.)
		№1		№2
М1 М2 М3 М4	2 1 - 1	1 1 1 -	16 10 6 7
Прибыль от реализации единицы продукции (грн.)	30	40

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

1.  На промышленном комплексе по производству мяса откармливают свиней двух пород. Все данные представлены в таблице.

Виды корма	Требуемое количество корма (ц) для породы свиней		Запасы корма, ц
		I		II
Грубые (сенная мука, травяные)	2	5	900
Сочные (корнеплоды, картофель)	4,5	2	1150
Комбикорма	1	1,5	340
Продуктивность, ц	4	5

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

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

Тип оборудования	Затраты времени (станко-часы) на обработку единицы продукции вида:		Общий фонд рабочего времени оборудования (час.)
		1		2
Фрезерное Токарное Шлифовальное	1 2 1	- 1 2	100 280 320
Прибыль от реализации единицы продукции (грн.)	80	60

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

Вид сырья	Нормы затрат сырья (т) на 1 т карамели		Общий объем сырья (т)
		А		В
Сахарный песок Патока Фруктовое пюре	0,8 0,5 -	0,6 0,8 0,1	80 60 8
Прибыль от реализации       1 т. карамели (тыс. грн.)	1,5	2

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

Вид сырья	Нормы затрат сырья (кг) на одно изделие		Общий объем сырья (кг)
		А		В
I II III	5 2 2	2 2 5	300 150 300
Прибыль от реализации одного изделия (грн.)	30	40

Фирме надо определить план выпуска изделий А и В, при котором прибыль от их реализации будет максимальной.

1.  Трикотажная фабрика для изготовления свитеров и кофточек использует чистую шерсть, силон и нитрон, запасы которого составляют соответственно 190, 120 и 80 кг. Количество пряжи каждого вида (в кг), необходимой для изготовления 10 изделий, а также прибыль, получаемая от их реализации, приведены в таблице.

Вид сырья	Затраты пряжи на 10 шт.
		Свитера	Кофточки
Шерсть	3	2
Силон	2	1
Нитрон	1	1
Прибыль (у.е.)	50	30

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

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

Ресурсы	Нормы расхода ресурсов на одно изделие		Общий объем ресурсов
		X		V
Металлические стержни (кг) Листовой металл (кг) Рабочее времени (чел.-час.)	2 5 1	5 2 2	10 000 10 000 4 000
Прибыль от реализации одной детали (грн.)	90	120

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

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

Ресурсы	Нормы расхода ресурсов на одно изделие		Общий объем ресурсов
		А		В
Доски (м2)	6	4	2000
Машинное время (час.)	0,25	0,5	180
Прибыль от реализации одного изделия (грн.)	100	160

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

1.  Автозавод выпускает две модели автомобилей: «Каприз» и (более дешевую) «Фиаско». В таблице приведены данные по нормам затрат ресурсов на одну модель каждого типа. В ней же указаны прибыль от реализации одной модели каждого типа и общий запас ресурсов, которым может располагать фирма в течение недели

Ресурсы	Нормы расхода ресурсов на одну модель автомобиля		Общий объем ресурсов в неделю
		«Каприз»		«Фиаско»
Рабочее время (чел.-час.) - неквалифицированных рабочих - квалифицированных рабочих Затраты на комплектующие (у.е.)	30 40 500	40 20 1500	40000 32000 900000
Прибыль от реализации одного автомобиля (у.е.)	1000	750

Рабочие, осуществляющие доставку, работают пять дней в неделю и могут забрать с завода не более 210 машин в день. Какой объем выпуска каждой модели Вы бы рекомендовали? Что бы Вы рекомендовали для повышения прибыли фирмы?

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

Ресурсы	Нормы расхода ресурсов на одно изделие		Общий объем ресурсов
		1		2
Оборудование (станко-час.) Сырьё (кг) Электроэнергия (кВт/час.)	0,2 1 2	0,3 4 4	78 850 880
Цена одного изделия (грн.)	30	100

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

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

Артикул ткани	Нормы затрат ткани (м) на одно изделие вида		Общий объем ткани (м)
		1		2
I II III	1 - 3	- 1 2	150 150 600
Цена  одного изделия (грн.)	80	60

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

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

Ресурсы	Нормы расхода ресурсов на 1 м ткани артикула		Общий объем ресурсов
		1		2
Производительность станков (станко-часы) Пряжа (кг) Красители (кг)	0,06 1,0 0,01	0,03 1,5 0,01	600 15000 120
Цена 1 м ткани (грн.)	80	50

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

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

Ткань	Нормы расхода ткани на одно изделие		Общий объем ресурсов (м2)
		платье		костюм
Вид №1 (м2)	1,5	1,6	139
Вид №2 (м2)	0,5	1	65
Прибыль от реализации одного изделия (грн.)	30	50

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

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

Вид работ	Продолжительность выполнения (дни) для типового проекта		Количество объектов строительства, в которых можно одновременно вести работы
		А		В
Закладка фундамента Монтажные работы Другие работы	20 8 30	30 7 15	15 4 12
Жилая площадь (м2)	3000	2000

Составить план строительства, максимизирующий введение жилой площади в течение года (300 рабочих дней).

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

Ресурсы	Время лечения одного больного		Общий объем ресурсов
		Приступы		Травмы
Хирургическая палата (час.) Томографический сканер  (час.) Места (дни)	- 1 4	2 1 10	2600 2600 14600

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

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

Ресурсы	Нормы расхода ресурсов на 1 кг лака		Общий объем ресурсов в день
		матового		полировочного
Рабочее время (чел-час.)	0,1	0,2	400
Химическая смесь (г)	0,05	0,02	100
Цена продажи 1 кг, грн.	13	16
Издержки производства на 1 кг, грн.	9	10

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

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

Тип вагона	Кол-во вагонов (шт) каждого типа в составе:		Парк вагонов, шт.	Число пассажиров в одном вагоне, чел.
		скором			пассажирском
багажный	1	-	1	12
почтовый	1	-	-	18
жесткий	4	58	8	88
купейный	6	40	4	79
мягкий	4	32	2	35

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

Тип вагона	Кол-во вагонов (шт) каждого типа в составе:		Парк вагонов, шт.	Число пассажиров в одном вагоне, чел.
		скором			пассажирском
багажный	1	-	1	12
почтовый	1	-	-	18
жесткий	4	58	8	88
купейный	6	40	4	79
мягкий	4	32	2	36

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

Вид работ	Продолжительность выполнения (дни) для типового проекта		Количество объектов строительства, в которых можно одновременно вести работы
		А		В
Закладка фундамента Монтажные работы Другие работы	20 10 30	30 5 15	10 5 12
Жилая площадь (м2)	3000	2000

Составить план строительства, максимизирующий введение жилой площади в течение года (300 рабочих дней).

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

.

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

,

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

Решить поставленную транспортную задачу

3.1 методом потенциалов,

3.2 с помощью инструмента «Поиск решения».

№ вар	ПАРАМЕТРЫ МОДЕЛИ
		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.  Гасс С. Линейное программирование. - М.: Наука, 1961.  303 с.
3.  Кузнецов А. В., Холод И. И. Математическое программирование. - Минск: Высшая школа, 1984. – 221 с.
4.  Сакович В.А. Исследование операций (детерминированные методы и модели): Справочное пособие. - Мн.: Выш. шк., 1984.-256с.
5.  Таха Х. Введение в исследование операций. В 2 кн.  Кн.1.  Пер. с англ. – М.: Мир, 1985.-479с., ил.
6.  Цегелик Г.Г. Лiнiйне програмування.- Л.: Свiт, 1995. – 216 с.
7.  Методические указания к практическим занятиям по дисциплине «Математическое программирование» (линейное программирование) для студентов экономических специальностей / Сост. Туровцев Г.В., Нудный И.П. – Запорожье, ЗГИА, 1984.-31с.
8.  Математическое программирование. Конспект лекций для студентов экономических специальностей дневного и заочного отделений /Глущевский В.В., Исаенко А.Н. – Запорожье: ЗГИА, 2003. – 150с. 
9.  Исследование операций. Методические указания к выполнению практических и лабораторных заданий (тема: "Решение задач линейного программирования с использованием Microsoft EXCEL for WINDOWS") для студентов ЗГИА экономических специальностей дневного и заочного отделений /Глущевский В.В., Исаенко А.Н. – Запорожье: ЗГИА, 2003. – 40с.

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

1.