Методы оптимальных решений

СОДЕРЖАНИЕ

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

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

Таблица 1.График самостоятельной работы по дисциплине «Методы оптимальных решений»

1. ВВЕДЕНИЕ. ОБЩАЯ ПОСТАНОВКА ЗАДАЧИ

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

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

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

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

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

Под принятием решений в курсе «Методы оптимальных решений» понимают сложный процесс, в котором можно выделить следующие основные этапы:

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

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

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

3-й этап. Исследование влияния переменных на значение целевой функции. Этот этап предусматривает владение математическим аппаратом для решения математических, задач, возникающих на втором этапе процесса принятия решения.

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

4-й этап. Сопоставление результатов вычислений, полученных на 3-м этапе, с моделируемым объектом, т. е. экспертная проверка результатов (критерий практики). Таким образом, на этом этапе устанавливается степень адекватности модели и моделируемого объекта в пределах точности исходной информации. Здесь возможны два случая:

1-й случай. Если результаты сопоставления неудовлетворительны (обычная ситуация на начальной стадии процесса моделирования), то переходят ко второму циклу процесса. При этом уточняется входная информация о моделируемом объекте и, в случае необходимости, уточняется постановка задачи (1-й этап); уточняется или строится заново математическая модель (2-й этап); решается соответствующая математическая задача (3-й этап) и, наконец, снова проводится сопоставление (4-й этап).

2-й случай. Если результаты сопоставления удовлетворительны, то модель принимается. Когда речь идет о неоднократном использовании на практике результатов вычислений, возникает задача подготовки модели к эксплуатации. Предположим, например, что целью моделирования является создание календарных планов производственной деятельности предприятия. Тогда эксплуатация модели включает в себя сбор и обработку информации, ввод обработанной информации в ЭВМ, расчеты на основе разработанных программ календарных планов и, наконец, выдачу результатов вычислений (в удобном для пользователей виде) для их использования в сфере производственной деятельности.

В математическом программировании можно выделить два направления.

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

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

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

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

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

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

Квадратичное программирование – целевая функция квадратична, а ограничениями являются линейные равенства и неравенства.

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

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

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

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

2. ГЕОМЕТРИЧЕСКОЕ ИСТОЛКОВАНИЕ ЗАДАЧИ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ

Задача линейного программирования (ЗЛП):

найти вектор X = (x 1 ,x 2 ,...,x n) максимизирующий линейную форму

F = Σ c j x j → max (2.1)

J=1

и удовлетворяющий условиям:

Σa ij x j ≤ b i (2.2)

J=1

x j ≥0 , j = 1,…,n (2.3)

Линейная функция F называется целевой функцией задачи.

Перепишем эту задачу в векторной форме:

Найдем тах функции:

F = c 1 x 1 + c 2 x 2 + … + c n x n (2.4)

x 1 P 1 + x 2 P 2 + … + x n P n = P 0 , (2.5)

x j ≥0 , j = 1,…,n (2.6)

где P 1 , …, P n и P 0 - m-мерные вектор столбцы, из коэффициентов при неизвестных и свободных членов системы уравнений задачи:

B 1 a 11 a 12 a 1n

P 0 = (b 2) ; P 1 = (a 21) ; P 2 = (a 22) ;……. P n = (a 2n) ; (2.7)

… … … …

B n a m1 a m2 a mn

План X = (x 1 ,x 2 ,...,x n) называется опорным планом основной ЗЛП, если положительные коэффициенты х j стоят при линейно независимых векторах Р j .

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

Теорема

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

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

Выводы:

Непустое множество планов основной ЗЛП образует выпуклый многогранник;

Каждая вершина этого многогранника определяет опорный план;

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

Двумерный случай ЗЛП

Найдем решение задачи, состоящее в определении максимального значения функции

F = c 1 x 1 + c 2 x 2 (2.8)

при условиях

a i1 x 1 + a i2 x 2 ≤ b i , (i=1,…,k) (2.9)

x j ≥0 (j=1,2) (2.10)

Задача линейного программирования состоит в нахождении такой точ-ки многоугольника решений, в которой целевая функция F принимает максимальное значение. Эта точка существует тогда, когда многоугольник ре-шений не пуст и на нем целевая функция ограничена сверху.

Для определения данной вершины построим линию уровня c 1 x 1 +c 2 x 2 =h, (где h – некоторая постоянная), проходящую через многоугольник решений, и будем передвигать ее в направлении вектора С=(с 1 ,с 2) до тех пор, пока она не пройдет через последнюю ее общую точку с многоугольником решений. Координаты указанной точки и определяют оптимальный план данной задачи.

Этапы решения ЗЛП геометрическим методом:

1. Построить прямые по уравнениям (2.9), (2.10).

2. Найти полуплоскости, определяемые каждым из ограничений задачи.

3. Найти многоугольник решений.

4. Построить вектор С.

5. Построить прямую c 1 x 1 +c 2 x 2 =h, проходящую через многоугольник решений.

6. Передвинуть прямую c 1 x 1 +c 2 x 2 =h в направлении вектора С.

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

Пример 1.

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

Таблица 2.1

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

Решение:

х1 – выпуск изделий вида А

х2 – выпуск изделий вида В

Тогда ограничения задачи:

Общая прибыль от реализации изделий вида А и В составит: F = 30х 1 + 40x 2

Найдем решение задачи, используя ее геометрическую интерпретацию.

Для этого в неравенствах системы ограничений перейдем к равенствам и построим соответствующие прямые:

Найдем координаты точки В – пересечения прямых:

Решив эту систему уравнений, получим: x 1 = 12 ; x 2 = 18

Следовательно, если предприятие изготовит 12 изделий вида А и 18 изделий вида В, то оно получит максимальную прибыль, равную

F max = 30·12+40·18 = 1080 руб.

Пример 2.

Решить ЗЛП

max(min)F = 2x 1 +3x 2 ;

Решение. Для построения области допустимых решений строим в системе x 1 Ox 2 соответствующие данным ограничениям-неравенствам граничные прямые:

x 1 +x 2 ≤ 6, x 1 +4x 2 ≥ 4, 2x 1 -x 2­ ≥ 0.

Находим полуплоскости, в которых выполняются данные неравенства. Для этого вследствие выпуклости любой полуплоскости достаточно взять произвольную точку, через которую не проходит соответствующая граничная прямая, и проверить, удовлетворяет ли эта пробная точка ограничению-неравенству. Если удовлетворяет, то данное неравенство выполняется в по-луплоскости, содержащей пробную точку. В противном случае берется полуплоскость, не содержащая пробной точки. В качестве пробной точки часто удобно брать начало координат О(0; 0). Для нашего примера область допус-тимых решений - множество точек четырехугольника АВСD (рис. 6).

Строим вектор с = (с 1 ; с 2) = (2; 3). Так как он необходим лишь для вы-яснения направления возрастания целевой функции, иногда для большей на-глядности удобно строить λс(λ > 0). Перпендикулярно к вектору с проводим линию уровня F=0. Параллельным перемещением прямой F=0 находим край-нюю точку В. в которой целевая функция принимает максимальное значение и точку А, в которой достигается минимальное значение.

Координаты точки В определяются системой

Откуда Fmax = F (A) = 32/9

ЗАДАНИЯ ДЛЯ САМОСТОЯТЕЛЬНОГО РЕШЕНИЯ

Задачи 1.1-1.10 решить графически.

Задача со многими переменными

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

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

Сделать это можно, последовательно, исключая переменные или мето-дом Жордана-Гаусса. Рассмотрим метод Жордана-Гаусса.

Таблица 1

(-3) 1 , (-1) 3,4

Таблица 2

(2) 1 , (-1) 2 ,(1) 3

Таблица 3

(-1) 2 , (1) 3 ,(2) 4

Таблица 4

(-1) 2 , (1) 3 ,(2) 4

Отбросим в уравнениях-ограничениях неотрицательные разрешенные неизвестные

x 2 , x 4 , x 5 и заменим знак равенства знаками неравенства, по-лучим вспомогательную задачу линейного программирования с двумя переменными:

F (x) = 2 x 3 +2 → max

F (x) = 0: 2 x 3 +2 -0 (0;-1) ;(5;-1)

F max = 2 при x 1 = 0; x 3 = 0

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

3.1. Геометрическая интерпретация симплексного метода

Если задача линейного программирования оптимизируется, то оптимум соответствует угловой точке (хотя бы одной) О.Д.Р. и совпадает с хотя бы одним из неотрицательных базисных решений. Таким образом, перебирая конечное число неотрицательных базисных решений системы, выбираем из них то, которое соответствует экстремальному значению целевой функции. Графически это означает, что мы перебираем угловые точки многогранника решений, улучшая значение целевой функции.

Симплексный метод состоит в:

1) определении первоначального допустимого базисного решения задачи;

2) переходе к лучшему решению;

3) проверке оптимального допустимого решения.

3.2. Табличная интерпретация симплексного метода

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

Найти оптимальное решение

X = (x 1 ,x 2 ,...,x n) (3.1)

удовлетворяющее системе ограничений (уравнений)

Σa ij x j = b i (i=1,m) (3.2)

j=1

и условиям x j ≥ 0 (j=1,n)

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

Z(x) = Σ c j x j (3.3)

j=1

Пусть найдено первоначальное неотрицательное базисное решение системы (3.2), где х 1, х 2 , х 3 … х m - базисные неизвестные, а х m+1 , x m+2 , …, x n – свободные неизвестные.

Тогда система (3.2) превращается в разрешенную систему

(3.4)

Данной системе соответствует неотрицательное базисное решение вида

X 0 = (b 1 ,b 2 ,...,b m ,0,0...0)

Подставим полученное решение в целевую функцию

Δ 0 = L(X 0) = Σ C j B j (3.5)

J=1

и преобразуем ее таким образом, чтобы она зависела только от свобод-ных неизвестных х m+1, х m+2 , … х n

Все базисные неизвестные х 1, х 2 , х 3 … х m выразим через свободные х m+1, х m+2 , … х n и подставим в целевую функцию.

Тогда целевая функция примет вид (3.6)

Введем понятие оценки Δ j свободных неизвестных

(3.7)

Тогда целевая функция примет вид

(3.8)

Введем в рассмотрение векторы C = (c 1 , c 2 , …, c m) и B = (a 1j , a 2j , …, a mj) (j=m+1,n), тогда равенство (3.7) можно записать в векторной форме

Δ j =CB j -c j (3.9)

Равенство (3.8) по характеру записи не отличается от уравнений систе-мы, поэтому добавим его к этой системе и получим расширенную систему:

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

первом столбце записаны базисные неизвестные x 1 ,x 2 , …, x m ; в столбце C записаны коэффициенты из целевой функции, соответствующие этим базисным неизвестным; в столбце B - свободные члены уравнений системы, совпадающие с положительными компонентами первоначального неотрицательного базисного решения X 0 . Под неизвестными x 1 ,x 2 , …, x n в столбцах записаны коэффициенты из системы.

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

В оценочной строке неравенство Δ j ≥0 и означает критерий оптимальности опорного плана.

Алгоритм решения ЗЛП симплекс-методом.

1. Найти опорный план.

2. Составить симплекс-таблицу.

3. Выяснить, имеется ли хотя бы одно отрицательное число Δ j

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

4. Найти направляющий столбец и строку. Наибольший столбец определяется наибольшим по абсолютной величине отрицательным числом Δ j , а направляющая строка – минимальным из отношений компонент столбца вектора Р 0 к положительным компонентам направляющего столбца.

5. По формулам (3.7) – (3.9) определить положительные компоненты нового опорного плана, коэффициенты разложения векторов Р j по векторам нового базиса и числа. Все эти числа записываются в новой симплекс- таблице.

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

Пример 3.1.

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

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

Решение:

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

х 1 – выпуск изделий вида А;

х 2 – выпуск изделий вида В;

х3 – выпуск изделий вида С.

Запишем систему ограничений:

Общая стоимость произведенных товаров составляет:

F = 9x 1 +10x 2 +16x 3

По экономическому содержанию переменные х 1 , х 2 , х 3 могут принимать только неотрицательные значения:

x 1 ,x 2 ,x 3 ≥0

Запишем эту задачу в виде основной ЗЛП, для этого перейдем от системы неравенств к равенствам, для этого введем три дополнительные переменные:

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

Запишем преобразованную систему уравнений в векторной форме:

x 1 P 1 +x 2 P 2 +x 3 P 3 +x 4 P 4 +x 5 P 5 +x 6 P 6 =P 0

где

Поскольку среди векторов Рj имеется три единичных вектора, то дляданной задачи можно записать опорный план Х=(0, 0, 0, 360, 192, 180) определяемый системой единичных векторов Р 4 , Р 5 , Р 6 , которые образуют базис трехмерного пространства.

Составляем симплексную таблицу I итерации и подсчитываем значения F 0 , z j -c j .

Проверяем исходный план на оптимальность:

F 0 = (С,P 0)=0; z 1 =(С,P 1)=0; z 2 =(С,P 2)=0; z 3 =(С,P 3)=0;

z 1 -c 1 = 0-9 = -9; z 2 -c 2 = 0-10 = -10; z 3 -c 3 = 0-16 = -16;

Для векторов базиса z j -c j = 0 (j=4,5,6).

Максимальное отрицательное число Δ j стоит в 4-ой строке столбца Р 3 . Следовательно, в базис введем вектор Р 3 . Определим вектор, подлежащий исключению из базиса, для этого находим Θ 0 = min(b i /a ij) для a i3 >0 т.е. Θ = min (360/12 ; 192/8; 180/3) =192/8 =24.

Т.е. ограничивающим фактором для производства изделий С является имеющийся объем сырья II вида. С учетом его наличия предприятие может изготовить 24 изделия С, при этом сырье II вида будет полностью израсходо вано.

Следовательно, вектор Р 5 подлежит исключению из базиса. Столбец вектора Р 3 и 2-я строка являются направляющими.

Составим таблицу II итерации. Сначала заполняем строку вектора, вновь введенного в базис, т.е. направляющую строку 2. Элементы этой строки получаются путем деления соответствующих элементов таблицы 1 наразрешающий элемент (т.е. 8). При этом в столбец С б записываем коэффи циент С 3 =16, стоящий в столбце вводимого в базис вектора Р 3

Для определения остальных элементов таблицы II применим правило треугольника.

Вычислим элементы таблицы II, стоящие в столбце Р 0 .

Первый элемент - находим три числа

1) число, стоящее в т. 1 на пересечении столбца Р0 и 1-ой строки (360);

2) число, стоящее в т. 1 на пересечении столбца Р3 и 1-ой строки (12);

3) число, стоящее в т. 2 на пересечении столбца Р0 и 2-ой строки (24).

360-12·24 = 72

Второй элемент был вычислен ранее (Θ 0 = 192/8 =24)

Третий элемент -

1) число, стоящее в т. 1 на пересечении столбца Р0 и 3-ой строки (180);

2) число, стоящее в т. 1 на пересечении столбца Р3 и 3-ой строки (3);

3) число, стоящее в т. 2 на пересечении столбца Р0 и 2-ой строки (24).

180-3·24 =108

Значение F 0 в 4-ой строке этого же столбца можно найти двумя спосо бами:

1) по формуле F 0 =(C,P 0) = 0·72+16·24+0·108 = 384;

2) по правилу треугольника:

Вычислим элементы вектора Р 1 т.2. Первые два числа берем из столб цов Р 1 и Р 3 т.1,

а третье число – из т.2 на пересечении 2-ой строки и столбца Р1.

18-12 (3/ 4) = 9; 5-3 (3/ 4)=11/ 4.

Число z 1 -c 1 в 4-й строке столбца вектора P 1 таблице 2

можно найти двумя способами:

1) по формуле z 1 -с 1 =(C,P 1)-c 1 имеем:

0·9+16·3/ 4+0·11/ 4-9 =3

2) по правилу треугольника получим:

-9-(-16) 3/ 4 = 3

Аналогично находим элементы столбца вектора P 2 .

Элементы столбца вектора Р 5 вычисляем по правилу треугольника.

выглядят иначе.Однако построенные для определения этих элементов треугольники

При вычислении элемента 1-й строки указанного столбца получается треугольник, образованный числами 0;12 и 1/8. Следовательно, искомый элемент равен

0 – 12 (1/8) = -3/2.

Элемент, стоящий в 3-й строке данного столбца, равен

0 - 3 (1 /8) = -3/8.

По окончании расчета всех элементов таблица II в ней получены но вый опорный план и коэффициенты разложения векторов Р j через базисные векторы P 4 , P 3 , P 6 и значения F 0 " Δ j ".

Как видно из этой таблицы, новым опорным планом задачи является план X=(0; 0; 24; 72; 0; 108).

Найденный на II итерации план задачи не является оптимальным.

этой строки стоит отрицательное число – 2. Это видно и из 4-й строки таблицы 2, поскольку в столбце вектора P 2 .

Значит, в базис следует ввести вектор P 2 , т. е. в новом плане следует предусмотреть выпуск изделий В.

При определении возможного числа изготовления изделий В следует учитывать имеющееся количество сырья каждого вида, а именно: возможный выпуск изделий В определяется min (b i "/a i 2") для a i2 ">0 т.е. находим Θ 0 = min(72/9; 24·2/1; 108·2/3) = 72/9=8.

Следовательно, исключению из базиса подлежит вектор Р4 иными словами, выпуск изделий В ограничен имеющимся в распоряжении предприятия сырьем I вида. С учетом имеющихся объемов этого сырья предприятию следует изготовить 8 изделий В. Число 9 является разрешающим элементом, а столбец вектора P2 и 1-я строка таблицы 2 являются направляющими.

Составим таблицу для III итерации.

В таблице III сначала заполняем элементы 1-й строки, которая представляет собой строку вновь вводимого в базис вектора Р2. Элементы этой строки получаем из элементов 1-й строки таблицы 2 делением последних на разрешающий элемент (т.е. на 9).

При этом в столбце С б данной строки записываем с 2 =10.

Затем заполняем элементы столбцов векторов базиса и по правилу треугольника вычисляем элементы остальных столбцов.

В результате в таблице III получаем новый опорный план X=(0; 8; 20; 0; 0; 96) и коэффициенты разложения векторов Р j через базисные векторы P 1 , P 2 и P 3 соответствующие значения F 0 "" и Δ j .

Проверяем, является ли данный опорный план оптимальным или нет. Для этого рассмотрим 4-ю строку, таблицы 3 . В этой строке среди чисел нет отрицательных. Это означает, что найденный опорный план является оптимальным и F max =400.

Следовательно, план выпуска продукции, включающий изготовление 8 изделий В и 20 изделий С, является оптимальным. При данном плане выпуска изделий полностью используется сырье I и II видов и остается неиспользованным 96 кг сырья III вида, а стоимость производимой продукции равна 400 €.

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

Пример 3.2

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

Решение:

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

-во вторую строку запишем неизвестные x 1 ,x 2 , …, x 5 ;

-в первой строке над ними – соответствующие коэффициенты 3, -2, 1,4,-1 из целевой функции;

-под неизвестными x 1 ,x 2 , …, x 5 , заполним столбцы, составленные из соответствующих коэффициентов левых частей уравнений исходной системы;

-в столбец запишем свободные члены уравнений 3,1,5;

-в первый столбец Б.п. поместим неизвестные x 2 ,x 3 , x 5 , так как под ними стоят единичные столбцы, и поэтому их будем считать базисными; базисные неизвестные располагаются в таком порядке, чтобы единицы в столбцах находились на пересечении одинаковых неизвестных;

-в столбец запишем коэффициенты -2,1,-1, из целевой функции при выбранных базисных неизвестных x 2 ,x 3 , x 5 ;

-заполним оценочную строку следующим образом: под столбцом B поместим число Δ 0 , вычисленное по формуле (3.5); под базисными неизвестными x 2 ,x 3 , x 5 - нули, которые можно получить и из равенства (3.9); под свободными переменными x 1 , x 4 - запишем значения, полученные из равенства (3.9).

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

Выберем в качестве разрешающего столбец х 4 , как самый «плохой» (ему соответствует наибольшая по модулю отрицательная оценка). Далее введем разрешающую строку следующим образом: для положительных коэффициентов столбца х 4 вычислим отношения b i /a i4 запишем их в графу θ.

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

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

Таким образом, уже в таблице второго шага критерий оптимальности выполнен. Мы получили оптимальный план Х(0;0;11/2;3/2;13/2), max L(X) =5.