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

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

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

Размер: px

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

Транскрипт

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Урок 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

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

В 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

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

Для реализации трех групп товаров коммерческое предприятие располагает тремя видами ограниченных материально-денежных ресурсов в количестве b 1 = 240, b 2 = 200, b 3 = 160 единиц. При этом для продажи 1 группы товаров на 1 тыс. руб. товарооборота расходуется ресурса первого вида в количестве a 11 = 2 единицы, ресурса второго вида в количестве a 21 = 4 единицы, ресурса третьего вида в количестве a 31 = 4 единицы. Для продажи 2 и 3 групп товаров на 1 тыс. руб. товарооборота расходуется соответственно ресурса первого вида в количестве a 12 = 3, a 13 = 6 единицы, ресурса второго вида в количестве a 22 = 2, a 23 = 4 единицы, ресурса третьего вида в количестве a 32 = 6, a 33 = 8 единиц. Прибыль от продажи трех групп товаров на 1 тыс. руб. товарооборота составляет соответственно c 1 = 4, c 2 = 5, c 3 = 4 (тыс. руб.). Определить плановый объем и структуру товарооборота так, чтобы прибыль торгового предприятия была максимальной.

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

Решение задачи симплекс методом

Пусть x 1 , x 2 , x 3 - количество реализованных товаров, в тыс. руб., 1, 2, 3 - ей групп, соответственно. Тогда математическая модель задачи имеет вид:

F = 4·x 1 + 5·x 2 + 4·x 3 ->max

0}}}{~}" title="delim{lbrace}{matrix{4}{1}{{2x_1 + 3x_2 + 6x_3= 0}}}{~}">

Решаем симплекс методом.

Вводим дополнительные переменные x 4 ≥ 0, x 5 ≥ 0, x 6 ≥ 0, чтобы неравенства преобразовать в равенства.

В качестве базиса возьмем x 4 = 240; x 5 = 200; x 6 = 160.

Данные заносим в симплекс таблицу

Симплекс таблица № 1

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

0 · 240 + 0 · 200 + 0 · 160 = 0

Вычисляем оценки по формуле:

Δ 1 = 0 · 2 + 0 · 4 + 0 · 4 - 4 = - 4
Δ 2 = 0 · 3 + 0 · 2 + 0 · 6 - 5 = - 5
Δ 3 = 0 · 6 + 0 · 4 + 0 · 8 - 4 = - 4
Δ 4 = 0 · 1 + 0 · 0 + 0 · 0 - 0 = 0
Δ 5 = 0 · 0 + 0 · 1 + 0 · 0 - 0 = 0
Δ 6 = 0 · 0 + 0 · 0 + 0 · 1 - 0 = 0

Поскольку есть отрицательные оценки, то план не оптимален. Наименьшая оценка:

Вводим переменную x 2 в базис.

Определяем переменную, выходящую из базиса. Для этого находим наименьшее неотрицательное отношение для столбца x 2 .

= 26.667

Наименьшее неотрицательное: Q 3 = 26.667. Выводим переменную x 6 из базиса

3-ю строку делим на 6.
Из 1-й строки вычитаем 3-ю строку, умноженную на 3
Из 2-й строки вычитаем 3-ю строку, умноженную на 2

Вычисляем:

Получаем новую таблицу:

Симплекс таблица № 2

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

0 · 160 + 0 · 440/3 + 5 · 80/3 = 400/3

Вычисляем оценки по формуле:

Δ 1 = 0 · 0 + 0 · 8/3 + 5 · 2/3 - 4 = - 2/3
Δ 2 = 0 · 0 + 0 · 0 + 5 · 1 - 5 = 0
Δ 3 = 0 · 2 + 0 · 4/3 + 5 · 4/3 - 4 = 8/3
Δ 4 = 0 · 1 + 0 · 0 + 5 · 0 - 0 = 0
Δ 5 = 0 · 0 + 0 · 1 + 5 · 0 - 0 = 0
Δ 6 = 0 · (-1)/2 + 0 · (-1)/3 + 5 · 1/6 - 0 = 5/6

Поскольку есть отрицательная оценка Δ 1 = - 2/3, то план не оптимален.

Вводим переменную x 1 в базис.

Определяем переменную, выходящую из базиса. Для этого находим наименьшее неотрицательное отношение для столбца x 1 .

Наименьшее неотрицательное: Q 3 = 40. Выводим переменную x 2 из базиса

3-ю строку делим на 2/3.
Из 2-й строки вычитаем 3-ю строку, умноженную на 8/3

Вычисляем:

Получаем новую таблицу:

Симплекс таблица № 3

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

0 · 160 + 0 · 40 + 4 · 40 = 160

Вычисляем оценки по формуле:

Δ 1 = 0 · 0 + 0 · 0 + 4 · 1 - 4 = 0
Δ 2 = 0 · 0 + 0 · (-4) + 4 · 3/2 - 5 = 1
Δ 3 = 0 · 2 + 0 · (-4) + 4 · 2 - 4 = 4
Δ 4 = 0 · 1 + 0 · 0 + 4 · 0 - 0 = 0
Δ 5 = 0 · 0 + 0 · 1 + 4 · 0 - 0 = 0
Δ 6 = 0 · (-1)/2 + 0 · (-1) + 4 · 1/4 - 0 = 1

Поскольку отрицательных оценок нет, то план оптимален.

Решение задачи:

Ответ

x 1 = 40; x 2 = 0; x 3 = 0; x 4 = 160; x 5 = 40; x 6 = 0; F max = 160

То есть необходимо реализовать товар первого вида в объеме 40 тыс. руб. Товар 2-го и 3-го видов реализовывать не надо. При этом максимальная прибыль составит F max = 160 тыс. руб.

Решение двойственной задачи

Двойственная задача имеет вид:

Z = 240·y 1 + 200·y 2 + 160·y 3 ->min

Title="delim{lbrace}{matrix{4}{1}{{2y_1 + 4y_2 + 4y_3>=4} {3y_1 + 2y_2 + 6y_3>=5} {6y_1 + 4y_2 + 8y_3>=4} {y_1, y_2, y_3>= 0}}}{~}">

Вводим дополнительные переменные y 4 ≥ 0, y 5 ≥ 0, y 6 ≥ 0, чтобы неравенства преобразовать в равенства.

Сопряженные пары переменных прямой и двойственной задач имеют вид:

Из последней симплекс таблицы № 3 прямой задачи, находим решение двойственной задачи:

Z min = F max = 160;
y 1 = Δ 4 = 0; y 2 = Δ 5 = 0; y 3 = Δ 6 = 1; y 4 = Δ 1 = 0; y 5 = Δ 2 = 1; y 6 = Δ 3 = 4;