Как заполнить матрицу эксель симплекс методом. Основные методы решения ЗЛП_Методичка

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

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

прибавление к обеим частям уравнения системы другого уравнения той же системы, умноженного на число, отличное от нуля;
перестановка местами уравнений в системе;
удаление из системы уравнений вида 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).

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

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

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

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

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

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

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

, при i = r . (*)

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

, при i ≠ r (**)

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Решение задачи о раскрое материалов Поиском решений Excel, часть 2

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

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

В нашей подборке вы также можете найти больше видеоуроков по решению прикладных задач в Excel
Больше других обучающих видеоуроков вы сможете найти на нашем сайте

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

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

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

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

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

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

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

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

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

Поиск решения в Excel

Быстрая пояснялка по надстройке Поиск решения в Excel. Статья по адресу

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

х 1 +2*х 2 <=16;

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

х 1 + х 2 <=10;

3*х 1 + х 2 <=24;

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

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

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

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

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

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

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

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

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