Особенности реализации в excel симплекс метода. Линейное программирование в Excel. Решение задач линейного программирование с помощью Excel

Урок 1. Решение задачи линейного программирования в Excel с помощью надстройки "Поиск решения"

Экономико-математические методы и модели. Задача распределения ресурсов. Классический пример и решения задачи линейного программирование. Описание как пользоваться надстройкой Поиск решения в Excel. Условие задачи здесь - , еще примеры решения задач по ЭМММ -

#ЭМММ #Excel #Матпрограммирование #ПоискРешения #Easyhelp

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

Использование надстройки Поиск решения для решения задач линейного программирования. Поставьте класс, если видео оказалось Вам полезно.

Простая задача линейного программирования №2. Симплекс-метод для поиска максимума.

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

.

Простая задача линейного программирования №1. Симплекс-метод для поиска минимума.

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

- Простая задача линейного программирования №3. Симплекс-метод для поиска минимума.
- Решение задачи линейного программирования алгоритмом двойственного симплекс-метода
- Решения прямой, двойственной задач ЛП, построение двойственной задачи ЛП.
- Решение задачи линейного программирования с неоднотипными неравенствами симплекс-методом
- Задача линейного программирования с системой уравнений

Лекция 2: Задача линейного программирования. Задача о ресурсах

Рассматривается решение задачи линейного программирования симплекс-методом.
Лекция и тесты в НОУ ИНТУИТ

Линейное программирование

Решение задачи линейного программирования с помощью Поиск решения MS Excel
Текстовый материал на сайте находится по адресу:

Урок 2. Решение двойственной задачи линейного программирования в Excel

Анализ устойчивости для прямой и двойственной задач линейного программирования в Excel. Условие задачи смотрите здесь - , еще примеры решений задач здесь -

#Excel #матпрограммирование #easyhelp

Симплекс-метод Excel VBA (Решение задачи линейного программирования с помощью макросов)

Демонстрация работы макроса в Excel. Решение задачи линейного программирования Симплекс-методом.
Заказать макрос - [email protected]

Решение лабораторных работ в Excel на заказ

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

линейное программирование. Симплексная таблица. Разрешающий элемент. Разрешающая строка. Разрешающий столбец. Симплексное отношение
Графический метод решения задач оптимизации.

Программа, реализующая симплекс-метод

Программа доступна по ссылке ниже:

Решение транспортной задачи в Excel с помощью надстройки "Поиск решения"

Задача линейного программирования. Транспортная задача. Решение в Excel, анализ устойчивости. Условие задачи здесь - , еще примеры решения задач по мат.программированию здесь -

#excel #матпрограммирование #ТранспортнаяЗадача #ЛинейноеПрограммирование #ПоискРешения #easyhelp #АнализУстойчивости

Двойственный метод

Методы оптимизации 12. Линейное программирование, симплекс-метод

Вирішуємо симплекс-метод вручну

Вирішуємо симплекс-метод вручну

Простая задача линейного программирования №3. Симплекс-метод для поиска минимума.

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

Простая задача линейного программирования №1. Симплекс-метод для поиска минимума.
- Простая задача линейного программирования №2. Симплекс-метод для поиска максимума.
- Решение задачи линейного программирования алгоритмом двойственного симплекс-метода
- Решения прямой, двойственной задач ЛП, построение двойственной задачи ЛП.
- Решение задачи линейного программирования с неоднотипными неравенствами симплекс-методом
- Задача линейного программирования с системой уравнений

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

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

Если данное видео принесло вам реальную пользу и вы хотите отблагодарить автора:
WMR: R370550256930
WMZ: Z939960413056

В нашей подборке вы можете найти больше видеоуроков по работе с электронными таблицами Microsoft Excel:

Еще больше других обучающих видеоуроков вы сможете найти на нашем сайте:

Решение задач линейного программирование с помощью Excel

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

Как известно, метод Жордана-Гаусса, он же метод последовательного исключения неизвестных, является модификацией метода Гаусса решения систем линейных алгебраических уравнений (СЛАУ).

Метод базируется на элементарных преобразованиях (переводящих систему в эквивалентную), к которым относятся:

• прибавление к обеим частям уравнения системы другого уравнения той же системы, умноженного на число, отличное от нуля;
• перестановка местами уравнений в системе;
• удаление из системы уравнений вида 0 = 0.

В отличие от метода Гаусса, на каждом шаге одна переменная исключается из всех уравнений, кроме одного.

Шаг метода состоит в следующем:

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

Алгоритмизировать это можно так:

Для СЛАУ в матричном виде A*x=b (матрица A размерности m*n , совсем необязательно квадратная) составляется следующая таблица:

В таблице выбран разрешающий элемент a r,s ≠0 , тогда r - разрешающая строка, s - разрешающий столбец.

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

1. вычисляются элементы разрешающей строки: a" r,j =a r,j /a r,s - то есть, r-строка таблицы делится на разрешающий элемент;

2. все элементы разрешающего столбца, кроме a r,s , равного единице, становятся равны нулю;

3. элементы вне разрешающих строки и столбца вычисляются по формуле, изображённой ниже:

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

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

Возможны следующие случаи:

1. В процессе исключений левая часть уравнения системы обращается в 0, а правая b≠0 , тогда система не имеет решения.

2. Получается тождество 0 = 0 - уравнение является линейной комбинацией остальных и строка нулей может быть вычеркнута из системы.

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

Запрограммируем метод в Excel одной формулой, изменять которую должно быть не слишком трудоёмко. Например, для решения СЛАУ

заполним коэффициентами системы ячейки листа от A1 до D4 включительно, выберем разрешающий элемент a 1,1 =1 , а первый шаг метода сделаем в ячейке A6 , куда загоним "универсальную" формулу для преобразования Жордана-Гаусса:

ЕСЛИ(СТРОКА($A$1)=СТРОКА(A1);A1/$A$1;
ЕСЛИ(СТОЛБЕЦ($A$1)=СТОЛБЕЦ(A1);0;(A1*$A$1-
ДВССЫЛ(АДРЕС(СТРОКА(A1);СТОЛБЕЦ($A$1)))*
ДВССЫЛ(АДРЕС(СТРОКА($A$1);СТОЛБЕЦ(A1))))/$A$1))

На следующем шаге разрешающим элементом может быть, например, a 2,2 =1 (ячейка B7). Нам останется скопировать формулу из A6 в A11 (по пустой строке оставляем, чтоб визуально разделить шаги метода), войти в режим редактирования формулы (двойной щелчок по ячейке или выбрать её и нажать клавишу F2) и поправить (аккуратно перетащить мышкой за границу) все закреплённые ссылки с ячейки A1 на B7 .

Конечно, можно заменить везде в формуле закреплённую ссылку $A$1 на конструкцию вида ДВССЫЛ(ЯЧЕЙКА) , образующую динамический адрес ссылки. Скажем, ДВССЫЛ(F8) , а в ячейке F8 будет автоматически формироваться адрес ячейки разрешающего элемента по заданным пользователем номеру строки и столбца. Тогда для этих номеров строки и столбца придётся предусмотреть отдельные ячейки, например, так:

Увы, всё это ничего не даст - вместо $A$1 мы просто вынуждены будем закрепить в формуле ДВССЫЛ($F$8) и всё равно потом перетаскивать столько же ссылок при копировании формулы. Кроме того, "вручную" введённые номера строки и столбца придётся ещё и проверять на допустимость (хотя бы как на рисунке), так что, не будем умножать сущностей.

Посмотреть метод в работе можно на двух первых листах приложенного файла Excel (2 разных примера).

На преобразовании Жордана-Гаусса основан и такой универсальный метод решения линейных задач оптимизации, как симплекс-метод . Описания его обычно страшны, длинны и перегружены теоремами. Попробуем сделать простое описание и разработать пригодный для расчёта в Excel алгоритм. На самом деле, симплекс-метод уже встроен в стандартную надстройку Пакет анализа, и программировать его "вручную" не нужно, так что наш код имеет, скорее, учебную ценность.

Сначала минимум теории.

Если вектор-столбцы СЛАУ линейно независимы, соответствующие им переменные являются базисными , а остальные – свободными . Например, в СЛАУ

переменные x 2 и x 4 - базисные, а x 1 и x 3 - свободные. Базисные переменные между собой независимы, а свободные можно сделать, например, нулями и получить { x 2 =2, x 4 =1 } – базисное решение системы.

Выбирая различные разрешающие элементы, можно получить решения СЛАУ с различными базисами. Любое неотрицательное базисное решение СЛАУ называется опорным .

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

Алгоритм симплекс-метода состоит в следующем:

1. Задача ЛП преобразуется к каноническому виду:

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

добавляются дополнительные балансовые переменные , число которых соответствует числу ограничений-неравенств m (ограничения на неотрицательность значений неизвестных не учитываются). После этого неравенства со знаком " ≤ " превращаются в равенства, например, система ограничений вида

2*x 1 +3*x 2 ≤20
3*x 1 +x 2 ≤15
4*x 1 ≤16
3*x 2 ≤12
x 1 ,x 2 ≥0

примет вид

2*x 1 +3*x 2 +x 3 =20
3*x 1 +x 2 +x 4 =15
4*x 1 +x 5 =16
3*x 2 +x 6 =12
x 1 ,x 2 ,...,x 6 ≥0

То есть, "экономический" смысл балансовых переменных очень прост – это "остатки" неиспользованных ресурсов каждого вида.

Если в исходной задаче искался не минимум, а максимум, целевая функция Z заменятся на Z 1 = -Z . Решения задач совпадают, при этом min Z = - max Z 1 . Например, цель

Z(x 1 ,x 2)=2*x 1 +5*x 2 (max)

переписывается в виде

Z 1 (x 1 ,x 2)=-2*x 1 -5*x 2 (min)

Если в исходной задаче были уравнения-неравенства со знаками " ≥ " вместо " ≤ ", обе части каждого такого неравенства умножаются на -1 , а знак неравенства меняется на противоположный, например,

3*x 1 +x 2 +x 4 ≥15

превращается в

3*x 1 -x 2 -x 4 ≤15

Канонический вид модели получен, для него выписывается симплекс-таблица :

В левом столбце записываются базисные переменные (БП), если они ещё не выделены – пусто.

2. С помощью шагов Жордана–Гаусса ищется первоначальный опорный план, т.е. СЛАУ приводится к базисному виду с неотрицательными свободными членами b i >0 . При этом целевая функция Z должна быть выражена только через свободные неизвестные (нулевые коэффициенты в Z-строке стоят только под переменными x i , которые есть в базисе). При выборе разрешающего элемента a r,s в строку r столбца БП выписываем переменную x s , если там уже была переменная – вычеркиваем её (выводим из базиса).

3. Выписываем под столбцами x i опорный план X * : под свободными переменными - нули, под базисными – соответствующие базисной переменной коэффициенты из столбца b .

Ниже выписываем вектор R по правилу: под базисными переменными – нули, под свободными R i =Z i .

Если все R i ≥0 , найдено оптимальное решение X * и значение цели Z min = -q , иначе нужен новый план, а у вас он есть, товарищ Жюков? (п. 4).

4. Для выбора разрешающего столбца s выбираем максимальную по модулю отрицательную компоненту вектора R , разрешающий столбец s выбран. Затем анализируем коэффициенты s-го столбца матрицы системы ограничений. Если все a i,s ≤0 , решения нет и Z min стремится к минус бесконечности, иначе переходим к п.5.

5. Для выбора разрешающей строки r составляем неотрицательные отношения b i /A i,s ≥0 , i=1,2,...,m , и выбираем среди них наименьшее. Если минимум достигается для нескольких строк, за разрешающую можно принять любую из них, при этом, в новом опорном плане значения некоторых базисных переменных станут равными 0, т.е., получаем вырожденный опорный план.

6. Выполняем преобразование Жордана-Гаусса с разрешающим элементом a r,s и переходим к п.3

Геометрически симплекс-методу соответствует кратчайший обход вершин n-мерного выпуклого многогранника, образующего область допустимых решений задачи:

Здесь мы перешли от опорного плана C , представляющего собой одну из вершин многомерного многоугольника, к оптимальному плану E=X * .

Запрограммировать это всё в Excel нелегко, но можно. В прилагаемом документе приведены 3 примера, реализующие решение задач симплекс-методом. Правда, при выполнени шага менять уже придётся 3 формулы, на листе первого примера на симплекс-метод они выделены жёлтым цветом: расчёт отношений для выбора разрешающей строки в ячейке I2 , заполнение столбца БП в ячейке A12 , шаг преобразования Жордана-Гаусса в ячейке B12 . Как и в примере на преобразование Жордана-Гаусса, изменение формул связано только с необходимостью сослаться на новую строку, содержащую адрес ячейки с разрешающим элементом (для первого шага - ячейка C9).

x 1

+x 2

+x 3

x 1

+x 2

+x 3

x 1

+x 2

+x 3

≤ = ≥

≤ = ≥

≤ = ≥

×

Предупреждение

Очистить все ячейки?

Закрыть Очистить

Инструкция ввода данных. Числа вводятся в виде целых чисел (примеры: 487, 5, -7623 и т.д.), десятичных чисел (напр. 67., 102.54 и т.д.) или дробей. Дробь нужно набирать в виде a/b, где a и b (b>0) целые или десятичные числа. Примеры 45/5, 6.6/76.4, -7/6.7 и т.д.

Симплекс метод

Примеры решения ЗЛП симплекс методом

Пример 1. Решить следующую задачу линейного программирования:

Правая часть ограничений системы уравнений имеет вид:

Запишем текущий опорный план:

Данный опорный план не является оптимальным, так как в последней строке есть отрицательные элементы. Самый большой по модулю отрицательный элемент (-3), следовательно в базис входит вектор x при . min (40:6, 28:2)=20/3 соответствует строке 1. Из базиса выходит вектор x 3 . Сделаем исключение Гаусса для столбца x 2 , учитывая, что ведущий элемент соответствует строке 1. Обнулим все элементы этого столбца, кроме ведущего элемента. Для этого сложим строки строки 2, 3, 4 со строкой 1, умноженной на -1/3, 1/6, 1/2, соответственно. Далее делим строку с ведущим элементом на ведущий элемент.

Данный опорный план не является оптимальным, так как в последней строке есть отрицательный элемент (-3), следовательно в базис входит вектор x 1 . Определяем, какой вектор выходит из базиса. Для этого вычисляем при . min(44/3:11/3, 62/3:5/3)=4 соответствует строке 2. Из базиса выходит вектор x 4 . Сделаем исключение Гаусса для столбца x 1 , учитывая, что ведущий элемент соответствует строке 2. Обнулим все элементы этого столбца, кроме ведущего элемента. Для этого сложим строки строки 1, 3, 4 со строкой 2, умноженной на 1/11, -5/11, 9/11, соответственно. Далее делим строку с ведущим элементом на ведущий элемент.

Симплекс таблица примет следующий вид:

Текущий опорный план является оптимальным, так как в строках 4 под переменными нет отрицательных элементов.

Решение можно записать так: .

Значение целевой функции в данной точке: F (X )=.

Пример 2. Найти максимум функции

Р е ш е н и е.

Базисные векторы x 4 , x 3 , следовательно, все элементы в столбцах x 4 , x 3 , ниже горизонтальной линии должны быть нулевыми.

Обнулим все элементы столбца x 4 , кроме ведущего элемента. Для этого сложим строку 3 со строкой 1, умноженной на 4. Обнулим все элементы столбца x 3 , кроме ведущего элемента. Для этого сложим строку 3 со строкой 2, умноженной на 1.

Симплекс таблица примет вид:

Данный опорный план не является оптимальным, так как в последней строке есть отрицательный элемент (-11), следовательно в базис входит вектор x 2 . Определяем, какой вектор выходит из базиса. Для этого вычисляем при . Все следовательно целевая функция неограничена сверху. Т.е. задача линейного программирования неразрешима.

Примеры решения ЗЛП методом искусственного базиса

Пример 1. Найти максимум функции

Р е ш е н и е. Так как количество базисных векторов должен быть 3, то добавляем искусственное переменное, а в целевую функцию добавляем это переменное, умноженное на −M, где M, очень большое число:

Матрица коэффициентов системы уравнений имеет вид:

Базисные векторы следовательно, все элементы в столбцах ниже горизонтальной линии должны быть нулевыми.

Обнулим все элементы столбца кроме ведущего элемента. Для этого сложим строку 5 со строкой 3, умноженной на -1.

Симплекс таблица примет вид:

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

Симплекс таблица примет следующий вид:

Данный опорный план не является оптимальным, так как в последней строке есть отрицательные элементы. Самый большой по модулю отрицательный элемент (-3), следовательно в базис входит вектор Определяем, какой вектор выходит из базиса. Для этого вычисляем при соответствует строке 1. Из базиса выходит вектор x 2 . Сделаем исключение Гаусса для столбца x 1 , учитывая, что ведущий элемент соответствует строке 1. Обнулим все элементы этого столбца, кроме ведущего элемента. Для этого сложим строки строки 2, 3, 4 со строкой 1, умноженной на 3/2, -1/10, 3/2, соответственно. Далее делим строку с ведущим элементом на ведущий элемент.

Симплекс таблица примет следующий вид:

Данный опорный план не является оптимальным, так как в последней строке есть отрицательные элементы. Самый большой по модулю отрицательный элемент (-13/2), следовательно в базис входит вектор x 3 . Определяем, какой вектор выходит из базиса. Для этого вычисляем при соответствует строке 3. Из базиса выходит вектор x 5 . Сделаем исключение Гаусса для столбца x 3 , учитывая, что ведущий элемент соответствует строке 3. Обнулим все элементы этого столбца, кроме ведущего элемента. Для этого сложим строки строки 1, 2, 4 со строкой 3, умноженной на 5/3, 25/9, 65/9, соответственно. Далее делим строку с ведущим элементом на ведущий элемент.

Симплекс таблица примет следующий вид:

Текущий опорный план является оптимальным, так как в строках 4−5 под переменными нет отрицательных элементов.

Решение исходной задачи можно записать так:

Пример 2. Найти оптимальный план задачи линейного программирования:

Матрица коэффициентов системы уравнений имеет вид:

Базисные векторы x 4 , x 5 , x 6 , следовательно, все элементы в столбцах x 4 , x 5 , x 6 , ниже горизонтальной линии должны быть нулевыми.

Обнулим все элементы столбца x 4 , кроме ведущего элемента. Для этого сложим строку 4 со строкой 1, умноженной на -1. Обнулим все элементы столбца x 5 , кроме ведущего элемента. Для этого сложим строку 5 со строкой 2, умноженной на -1. Обнулим все элементы столбца x 6 , кроме ведущего элемента. Для этого сложим строку 5 со строкой 3, умноженной на -1.

Симплекс таблица примет вид:

В строке 5 элементы, соответствующие переменным x 1 , x 2 , x 3 , x 4 , x 5 , x 6 неотрицательны, а число находящийся в пересечении данной строки и столбца x 0 отрицательнo. Тогда исходная задача не имеет опорного плана. Следовательно она неразрешима.

В Excel 2007 для включения пакета анализа надо нажать перейти в блок Параметры Excel , нажав кнопку в левом верхнем углу, а затем кнопку «Параметры Excel » внизу окна:

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

Заполните данные

Значение переменных X i может различаться, но целевая функция F(x) должна иметь такое же значение.

Иногда задание звучит следующим образом: расчеты осуществить на ЭВМ, привести распечатку полученных результатов.

MS Excel позволяет представить результаты поиска решения в форме отчета. Существует три типа таких отчетов:

1. Результаты (Answer). В отчет включаются исходные и конечные значения целевой и влияющих ячеек, дополнительные сведения об ограничениях.
2. Устойчивость (Sensitivity). Отчет, содержащий сведения о чувствительности решения к малым изменениям в изменяемых ячейках или в формулах ограничений.
3. Пределы (Limits). Помимо исходных и конечных значений изменяемых и целевой ячеек в отчет включаются верхние и нижние границы значений, которые могут принимать влияющие ячейки при соблюдении ограничений.

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

	ПРОИЗВОДИТЕЛЬНОСТЬ БАБУШЕК м 2 . /мин
	Баба Аня	Белла Петровна	Баба Варя	Баба Галя	Домна Ивановна	Евгения Карловна	Площадь работ
Мытье окон	2	0	0	1	0	0	46
Мытье полов	0	1	0	0	0	0	300
Протирка столов	0	0	2	0	0.2	1	50
Чистка дорожек	0	0	0	2	0	4	100

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

Задача 1 (распределительная)

На предприятии 4 вида продукции могут вырабатываться на 3 отдельных взаимозаменяемых машинах.

Известны:

· Производственное задание по выпуску продукции разных видов в планируемом периоде

• · Фонд эффективного рабочего времени оборудования в планируемом периоде - ;
• · Нормы затрат машинного времени на изготовление единицы продукции - ;
• · Прибыль в руб. от реализации единицы продукции, выработанной на том или ином оборудовании - .

Исходная информация отображается в таблице следующей формы.

Таблица 1. Исходные данные

Фонд эф. раб. врем. -	Нормы затрат врем. на ед. продукции - прибыль на ед. продукции -

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

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

РЕШЕНИЕ

Разработка экономико - математической модели.

Искомые переменные - характеризуют объём выпуска й продукции м исполнителем.

Тогда матрица искомых переменных

характеризует план распределения производственного задания по выпуску продукции между исполнителями.

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

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

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

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

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

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

Приведём задачу к каноническому виду, для этого в неравенства (2) добавим переменные, а в равенства (3) добавим 4 искусственных базиса. В результате запишем математическую модель задачи в каноническом виде:

Симплекс-метод

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

Таблица 1

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

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

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

Покажем это.

Таблица 2

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

Таблица 3

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

Таблица 4

Выделим столбец с переменной. Наименьшее оценочное отношение 28,57, находится в первой строке. Из базиса выводим переменную, при этом в базис вводим переменную.

Таблица 5

Выделим столбец с переменной. Наименьшее оценочное отношение 407,7, находится в третьей строке. Из базиса выводим переменную, при этом в базис вводим переменную.

Таблица 6

Выделим столбец с переменной. Наименьшее оценочное отношение 344,3, находится в седьмой строке. Из базиса выводим искусственный базис, при этом в базис вводим переменную.

Таблица 7

Выделим столбец с переменной. Наименьшее оценочное отношение 3,273, находится во второй строке. Из базиса выводим переменную, при этом в базис вводим переменную.

Таблица 8

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

Таблица 9

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

Таблица 10

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

Таблица 11

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

Таблица 12

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

Таблица 13

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

Таблица 14

Так как в индексной строке нет отрицательных оценок, получен оптимальный план, при котором объём выпуска продукции представлен матрицей

при этом прибыль максимальная и составляет 17275,31 руб.

Решение задачи с помощью Excel

Математическую модель задачи необходимо перенести в ЭТ EXCEL. Для этого:

• · Продумать организацию исходных данных модели (коэффициенты целевой функции и ограничения), снабдив понятными названиями.
• · Зарезервировать в отдельных ячейках независимые переменные математической модели.
• · В одной из ячеек создать формулу, определяющую целевую функцию.
• · Выбрать ячейки и поместить в них формулы, соответствующие левым частям ограничений.
• · Войти в пункт меню "Поиск решения", ввести необходимые данные и получить оптимальное решение задачи.
• · Проанализировать полученное решение и отчёты.

Рассмотрим последовательность действий по реализации этих этапов решения задачи с помощью EXCEL.

Создадим таблицу для ввода исходных данных.

В созданную форму введём исходные данные.

Коэффициенты целевой функции, выражающие прибыль, от производства единицы продукции каждого вида (единичная прибыль), записаны в ячейки В6:M6.

Коэффициенты ресурсных ограничений, определяющие потребность в каждом из видов ресурсов для производства единицы продукции, размещены в ячейках В9:M15. В ячейках P9:P15 записаны правые части ограничений на ресурсы. Для независимых переменных задачи - искомых объёмов производства продукции зарезервированы ячейки В3:M3.

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

А также заполняем ограничения правой части.

После этого можно приступать к поиску решения. Для решения оптимизационных задач в EXCEL используется команда ПОИСК РЕШЕНИЯ меню СЕРВИС.

Эта команда оперирует с тремя основными компонентами построенной в ЭТ оптимизируемой модели:

• · Ячейкой, содержащей целевую функцию задачи.
• · Изменяемыми ячейками, содержащими независимые переменные.
• · Ячейками, содержащими левые части ограничений на имеющиеся ресурсы, а также простые ограничения на независимые переменные.

Рассмотрим последовательность ввода этих компонентов.

Курсор в ячейку N7 и команда СЕРВИС - Поиск решения. На экране появится диалоговое окно.

В окне заполняем поле Установить целевую ячейку, в котором должен стоять адрес $N$7. Далее устанавливаем кнопку на поиск максимального значения. В поле Изменяя ячейки введём адреса искомых переменных $B3:$M3. Затем следует ввести ограничения, путём кнопки Добавить.

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

После этого получим решение задачи.

Если вычисления оказались успешными, после завершения поиска решения значения будут вставлены в таблицу, а также можно указать Тип отчёта - Результаты, в результате которого можем получить следующий отчёт. рабочий время оборудование прибыль

Следовательно, решение в EXCEL такое же, как и при СИМПЛЕКС методе, а это значит, что рассматриваемая задача, решена, верно.