مجموعه های محدب و خواص آنهابرای بررسی خصوصیات یک مجموعه محدب، لازم است تعریف دقیقی از مجموعه محدب ارائه شود. پیش از این، مجموعه محدب به عنوان مجموعه‌ای تعریف می‌شد که همراه با هر دو نقطه آن، شامل یک قطعه است که آنها را به هم متصل می‌کند.

تعمیم مفهوم یک قطعه برای چندین نقطه ترکیب خطی محدب آنها است.

نقطه X نامیده می شود ترکیب خطی محدبنکته ها, در صورت تحقق شرایط

مجموعه نقاط است محدب،اگر همراه با هر دو نقطه از آن، ترکیب خطی و محدب دلخواه خود را داشته باشد.

می توانیم قضیه زیر را در مورد نمایش یک چندوجهی محدب اثبات کنیم.

قضیه 1.1. یک چندوجهی n بعدی محدب، ترکیب خطی محدب از نقاط گوشه آن است.

از قضیه 1.1 چنین بر می آید که یک چندوجهی محدب توسط نقاط گوشه یا رئوس آن ایجاد می شود: یک پاره با دو نقطه، یک مثلث با سه، یک چهار وجهی با چهار نقطه و غیره. در عین حال، یک منطقه چند وجهی محدب، که مجموعه ای نامحدود است، به طور منحصر به فردی با نقاط گوشه آن تعریف نمی شود: هیچ یک از نقاط آن را نمی توان به عنوان یک ترکیب خطی محدب از نقاط گوشه نشان داد.

ویژگی های مسئله برنامه ریزی خطیقبلا اشکال مختلفی از یک مسئله برنامه ریزی خطی در نظر گرفته شد و نشان داده شد که هر مسئله برنامه ریزی خطی را می توان به عنوان یک مسئله کلی یا متعارف نشان داد.

برای اثبات ویژگی‌های مسئله برنامه‌ریزی خطی و روش‌های حل آن، توصیه می‌شود دو نوع دیگر از نمادگذاری مسئله متعارف را در نظر بگیرید.

فرم ضبط ماتریس:

اینجا با- ماتریس ردیف، آ- ماتریس سیستم، ایکس- ماتریس-ستون متغیرها، که در- ماتریس-ستون اعضای آزاد:

فرم برداری ضبط:

که در آن بردارها با ستون های ضرایب مجهولات مطابقت دارند.

قضیه زیر در بالا فرمول بندی شد، اما به صورت کلی ثابت نشد.

قضیه 1.2. مجموعه تمام راه حل های امکان پذیر برای سیستم محدودیت های یک مسئله برنامه ریزی خطی محدب است.

اثبات:اجازه دهید - دو راه حل امکان پذیر PLP، که به شکل ماتریس ارائه شده است. سپس . اجازه دهید یک ترکیب خطی محدب از راه حل ها را در نظر بگیریم، به عنوان مثال.

و نشان می دهد که آن نیز یک راه حل قابل قبول سیستم (1.3) است. در واقع

یعنی راه حل ایکسسیستم (1.3) را برآورده می کند. اما از آن زمان ایکس> 0، یعنی راه حل شرایط غیر منفی را برآورده می کند.

بنابراین، ثابت شده است که مجموعه تمام راه حل های امکان پذیر برای یک مسئله برنامه ریزی خطی محدب است، یا به طور دقیق تر، نشان دهنده یک چند وجهی محدب یا یک ناحیه چند وجهی محدب است، که در ادامه آن را با یک جمله می نامیم - چند وجهی محلول ها

پاسخ به این سوال که در کدام نقطه از حل چندوجهی راه حل بهینه برای یک مسئله برنامه ریزی خطی ممکن است در قضیه اساسی زیر آورده شده است.

قضیه 1.3. اگر یک مسئله برنامه ریزی خطی راه حل بهینه داشته باشد، تابع خطی حداکثر مقدار خود را در یکی از نقاط گوشه چندوجهی حل می گیرد. اگر یک تابع خطی در بیش از یک نقطه گوشه حداکثر مقدار را بگیرد، آنگاه آن را در هر نقطه ای که ترکیب خطی محدب این نقاط است می گیرد.

اثبات:فرض می کنیم که چند وجهی محلول محدود است. اجازه دهید نقاط گوشه آن را با علامت گذاری کنیم , و راه حل بهینه از طریق است ایکس*. سپس F(X*)³ F(X)برای تمام نقاط ایکسچند وجهی محلول ها اگر ایکس*یک نقطه گوشه است، سپس قسمت اول قضیه ثابت می شود.

بیایید وانمود کنیم که ایکس*بنابراین، بر اساس قضیه 1.1 یک نقطه گوشه نیست ایکس*را می توان به عنوان یک ترکیب خطی محدب از نقاط گوشه چند وجهی محلول نشان داد، یعنی.

زیرا F(X)یک تابع خطی است، دریافت می کنیم

در این تجزیه، ماکزیمم را از بین مقادیر انتخاب می کنیم. بگذارید با نقطه گوشه مطابقت داشته باشد X k(1 پوند ک£ ر); بیایید آن را با علامت گذاری کنیم م،آن ها . اجازه دهید هر مقدار در عبارت (1.5) را با این مقدار حداکثر جایگزین کنیم م.سپس

با فرض ایکس* راه حل بهینه است، بنابراین، از یک طرف، اما، از طرف دیگر، ثابت شده است که
F(X*)£ م،بنابراین، کجا X k- نقطه گوشه بنابراین یک نقطه گوشه وجود دارد X k، که در آن تابع خطی حداکثر مقدار خود را می گیرد.

برای اثبات قسمت دوم قضیه، فرض می کنیم که تابع هدف در بیش از یک نقطه گوشه، مثلاً در نقاط، حداکثر مقدار را می گیرد. ، جایی که , سپس

اجازه دهید ایکس- یک ترکیب خطی محدب از این نقاط گوشه، یعنی.

در این حالت با توجه به اینکه تابع F(X)- خطی، می گیریم

آن ها تابع خطی افحداکثر مقدار را در یک نقطه دلخواه می گیرد ایکس، که یک ترکیب خطی محدب از نقاط گوشه است.

اظهار نظر.شرط محدود بودن چندوجهی محلول در قضیه ضروری است، زیرا در مورد یک ناحیه چندوجهی نامحدود، همانطور که در قضیه 1.1 ذکر شد، هر نقطه از چنین ناحیه ای را نمی توان با ترکیب خطی محدب نقاط گوشه آن نشان داد.

قضیه اثبات شده بنیادی است، زیرا نشان دهنده یک راه اساسی برای حل مسائل برنامه ریزی خطی است. در واقع، با توجه به این قضیه، به جای مطالعه مجموعه ای نامتناهی از راه حل های امکان پذیر برای یافتن راه حل بهینه مورد نظر از بین آنها، لازم است فقط تعداد محدودی از نقاط گوشه چند وجهی حل مورد مطالعه قرار گیرد.

قضیه بعدی به روش تحلیلی یافتن نقاط گوشه اختصاص دارد.

قضیه 1.4. هر راه حل اساسی قابل قبول یک مسئله برنامه ریزی خطی مربوط به یک نقطه گوشه از چند وجهی راه حل است، و بالعکس، به هر نقطه گوشه ای از چند وجهی راه حل، یک راه حل پایه قابل قبول مطابقت دارد.

اثبات:اجازه دهید یک راه حل اساسی قابل قبول از سیستم محدودیت های LLP (1.4) باشد، که در آن اولین تیجزء متغیرهای اصلی و بقیه هستند p - tجزء - متغیرهای غیر اصلی برابر با صفر در راه حل اصلی (اگر اینطور نیست، می توان متغیرهای مربوطه را مجددا شماره گذاری کرد). بیایید آن را نشان دهیم ایکس

بیایید برعکس را فرض کنیم، یعنی. چی ایکسیک نقطه گوشه نیست سپس اشاره کنید ایکسرا می توان با نقطه داخلی یک قطعه نشان داد که دو قطعه مختلف را که با هم منطبق نیستند به هم وصل می کند ایکس،نکته ها

به عبارت دیگر، یک ترکیب خطی محدب از نقاط چند وجهی محلول ها، یعنی

کجا (فرض می کنیم که، زیرا در غیر این صورت نقطه ایکسمنطبق با نقطه ایکس 1 یا ایکس 2).

اجازه دهید برابری برداری (1.6) را به صورت مختصات بنویسیم:

زیرا همه متغیرها و ضرایب غیر منفی هستند، سپس از آخرین p-tبرابری ها نتیجه می شود که , i.e. در تصمیم گیری ها ایکس 1 , ایکس 2 و ایکسسیستم معادلات (1.4) مقادیر p - tمولفه ها در این حالت برابر با صفر هستند. این مولفه ها را می توان مقادیر متغیرهای غیر اولیه در نظر گرفت. اما مقادیر متغیرهای غیر پایه به طور منحصر به فرد مقادیر اصلی را تعیین می کند، بنابراین،

پس همه چیز پجزء در محلول ها ایکس 1 , ایکس 2 و ایکسمنطبق هستند، و بنابراین نقاط ایکس 1 و ایکس 2 ادغام، که با این فرض در تضاد است. از این رو، ایکس- نقطه گوشه چندوجهی محلول.

اجازه دهید بیان مخالف را ثابت کنیم. اجازه دهید نقطه گوشه چند وجهی محلول و اولین آن باشد تیمختصات مثبت است بیایید آن را نشان دهیم ایکس- راه حل اساسی قابل قبول یک نقطه گوشه نیست، که با شرایط در تضاد است. بنابراین، فرض ما نادرست است، یعنی. بردارها به صورت خطی مستقل هستند و ایکسیک راه حل اساسی قابل قبول برای مسئله (1.4) است.

یک نتیجه مهم مستقیماً از قضایای 1.3 و 1.4 به دست می آید: اگر یک مسئله برنامه ریزی خطی یک راه حل بهینه داشته باشد، حداقل با یکی از راه حل های اساسی امکان پذیر آن منطبق است.

بنابراین، بهینه یک تابع خطی یک مسئله برنامه ریزی خطی را باید در میان تعداد محدودی از راه حل های اساسی امکان پذیر آن جستجو کرد.

اجزای مدل ریاضی

مبنای حل مسائل اقتصادی مدل های ریاضی هستند.

مدل ریاضیمسئله مجموعه ای از روابط ریاضی است که ماهیت مسئله را توصیف می کند.

ترسیم یک مدل ریاضی شامل موارد زیر است:

• انتخاب متغیرهای مسئله
• تدوین یک سیستم محدودیت
• انتخاب تابع هدف

متغیرهای وظیفهمقادیر X1، X2، Xn نامیده می شوند که به طور کامل فرآیند اقتصادی را مشخص می کنند. آنها معمولاً به صورت بردار نوشته می شوند: X=(X1, X2,...,Xn).

سیستم محدودیت هامسائل مجموعه ای از معادلات و نابرابری ها هستند که منابع محدود در مسئله مورد بررسی را توصیف می کنند.

تابع هدفوظایف تابعی از متغیرهای وظیفه نامیده می‌شوند که کیفیت کار را مشخص می‌کند و حداکثر آن را باید پیدا کرد.

به طور کلی یک مسئله برنامه ریزی خطی را می توان به صورت زیر نوشت:

این ورودی به معنای زیر است: حداکثر تابع هدف (1) و متغیرهای متناظر X=(X1, X2,...,Xn) را بیابید به شرطی که این متغیرها سیستم محدودیت ها (2) و غیر منفی بودن را برآورده کنند. شرایط (3).

راه حل معتبر(طرح) یک مسئله برنامه ریزی خطی هر بردار n بعدی X=(X1, X2,...,Xn) است که سیستم محدودیت ها و شرایط غیر منفی را برآورده می کند.

مجموعه راه‌حل‌های عملی (طرح‌ها) مسئله شکل می‌گیرد منطقه راه حل های امکان پذیر(ODR).

راه حل بهینه(طرح) یک مسئله برنامه ریزی خطی، چنین راه حل (طرح) قابل قبولی از مسئله است که در آن تابع هدف به یک حد نهایی می رسد.

نمونه ای از ترسیم یک مدل ریاضی مسئله استفاده از منابع (مواد اولیه)

وضعیت:برای تولید n نوع محصول از m نوع منابع استفاده می شود. یک مدل ریاضی بسازید.

شناخته شده:

• bi (i = 1،2،3،...،m) - ذخایر هر iمین نوع منبع؛
• aij (i = 1,2,3,...,m؛ j=1,2,3,...,n) - هزینه های هر iمین نوع منبع برای تولید یک واحد حجم j-امین نوع محصول؛
• cj (j = 1،2،3،...،n) - سود حاصل از فروش یک واحد حجم از نوع jام محصول.

لازم است یک برنامه تولید تهیه شود که حداکثر سود را تحت محدودیت های داده شده در منابع (مواد اولیه) تضمین کند.

راه حل:

اجازه دهید یک بردار از متغیرهای X=(X1, X2,...,Xn) را معرفی کنیم که در آن xj (j = 1,2,...,n) حجم تولید نوع j-ام محصول است.

هزینه های منبع نوع i برای تولید حجم معین xj از محصولات برابر با aijxj است، بنابراین محدودیت استفاده از منابع برای تولید انواع محصولات به شکل زیر است:
سود حاصل از فروش نوع j ام محصول برابر با cjxj است، بنابراین تابع هدف برابر است با:

پاسخ- مدل ریاضی به صورت زیر است:

شکل متعارف یک مسئله برنامه ریزی خطی

در حالت کلی، یک مسئله برنامه ریزی خطی به گونه ای نوشته می شود که محدودیت ها هم معادله و هم نابرابری هستند و متغیرها می توانند غیر منفی یا به طور دلخواه متغیر باشند.

در صورتی که همه قیودها معادله باشند و همه متغیرها شرط عدم منفی بودن را برآورده کنند، مسئله برنامه ریزی خطی نامیده می شود. ابتدایی.

می توان آن را به صورت مختصات، بردار و نماد ماتریسی نشان داد.

مسئله برنامه ریزی خطی متعارف در نماد مختصات به شکل زیر است:

مسئله برنامه نویسی خطی متعارف در نمادگذاری ماتریس به شکل زیر است:

• الف - ماتریس ضرایب سیستم معادلات
• X - ماتریس-ستون متغیرهای وظیفه
• Ао - ماتریس-ستون قسمت های سمت راست سیستم محدودیت ها

مسائل برنامه نویسی خطی، به نام متقارن، اغلب مورد استفاده قرار می گیرند که در نمادگذاری ماتریسی به شکل زیر است:

کاهش یک مسئله برنامه ریزی خطی عمومی به شکل متعارف

در اکثر روش های حل مسائل برنامه ریزی خطی، فرض بر این است که سیستم محدودیت ها از معادلات و شرایط طبیعی برای منفی نبودن متغیرها تشکیل شده است. با این حال، هنگام تدوین مدل‌های مسائل اقتصادی، محدودیت‌ها عمدتاً در قالب سیستم نابرابری‌ها شکل می‌گیرند، بنابراین لازم است بتوان از سیستم نابرابری‌ها به سیستم معادلات حرکت کرد.

این را می توان به صورت زیر انجام داد:

بیایید نابرابری خطی a1x1+a2x2+...+anxn≤b را در نظر بگیریم و مقدار مشخصی xn+1 را به سمت چپ آن اضافه کنیم، به طوری که نابرابری به برابری a1x1+a2x2+...+anxn+xn+1=b تبدیل شود. . علاوه بر این، این مقدار xn+1 غیر منفی است.

بیایید با استفاده از یک مثال به همه چیز نگاه کنیم.

مثال 26.1

مسئله برنامه ریزی خطی را به شکل متعارف بیاورید:

راه حل:
بیایید به مسئله یافتن حداکثر تابع هدف برویم.
برای این کار، علائم ضرایب تابع هدف را تغییر می دهیم.
برای تبدیل نابرابری های دوم و سوم سیستم محدودیت ها به معادله، متغیرهای اضافی غیر منفی x4 x5 را معرفی می کنیم (در مدل ریاضی این عمل با حرف D مشخص شده است).
متغیر x4 در سمت چپ نابرابری دوم با علامت "+" وارد می شود، زیرا نابرابری به شکل "≤" است.
متغیر x5 در سمت چپ نابرابری سوم با علامت "-" وارد می شود، زیرا نابرابری به شکل "≥" است.
متغیرهای x4 x5 با یک ضریب وارد تابع هدف می شوند. برابر با صفر
مسئله را به صورت متعارف می نویسیم:

برنامه ریزی خطیشاخه‌ای از ریاضیات است که روش‌هایی را برای یافتن حداقل یا حداکثر یک تابع خطی از تعداد محدودی از متغیرها مطالعه می‌کند، مشروط بر اینکه متغیرها تعداد محدودی از محدودیت‌ها را به شکل معادلات خطی یا نابرابری‌های خطی برآورده کنند.

بنابراین، مسئله برنامه ریزی خطی عمومی (GLP) را می توان به صورت زیر فرموله کرد.

مقادیر متغیرهای واقعی را پیدا کنید که برای آنها تابع هدف

برای مجموعه نقاطی که مختصات آنها برآورده می شود یک مقدار حداقل می گیرد سیستم محدودیت ها

همانطور که مشخص است، مجموعه ای منظم از مقادیر nمتغیرها , … با یک نقطه در فضای n بعدی نشان داده می شود. در ادامه به این نکته اشاره خواهیم کرد ایکس=( , , … ).

به صورت ماتریسی، مسئله برنامه ریزی خطی را می توان به صورت زیر فرموله کرد:

, آ- ماتریس اندازه،

نقطه ایکس=( , , … ) که تمام شرایط را برآورده می کند، فراخوانی می شود نکته معتبر . مجموعه تمام نقاط قابل قبول نامیده می شود منطقه معتبر .

راه حل بهینه (طرح بهینه)یک مسئله برنامه ریزی خطی راه حل نامیده می شود ایکس=( , , …)، متعلق به ناحیه مجاز و تابع خطی برای آن است سمقدار بهینه (حداکثر یا حداقل) را می گیرد.

قضیه. مجموعه تمام راه حل های امکان پذیر برای سیستم محدودیت های یک مسئله برنامه ریزی خطی محدب است.

مجموعه نقاط نامیده می شود محدب ، اگر همراه با هر دو نقطه از آن ترکیب خطی محدب دلخواه خود را داشته باشد.

نقطه ایکستماس گرفت ترکیب خطی محدب در صورت احراز شرایط امتیاز می گیرد

مجموعه تمام راه حل های امکان پذیر برای یک مسئله برنامه ریزی خطی یک ناحیه چند وجهی محدب است که از این پس آن را می نامیم. چند وجهی محلول ها .

قضیه. اگر ZLP راه حل بهینه داشته باشد، تابع هدف حداکثر (حداقل) مقدار را در یکی از رئوس چند وجهی حل می گیرد. اگر تابع هدف در بیش از یک نقطه حداکثر (حداقل) مقدار را بگیرد، در هر نقطه ای که ترکیب خطی محدب این نقاط است این مقدار را می گیرد.

در میان بسیاری از راه حل های سیستم مترمعادلات خطی که چند وجهی راه حل ها را توصیف می کنند، به اصطلاح راه حل های اساسی متمایز می شوند.

راه حل اساسی سیستم مترمعادلات خطی با n متغیر راه حلی است که در آن همه n-mمتغیرهای غیر هسته ای صفر هستند. در مسائل برنامه نویسی خطی به چنین راه حل هایی گفته می شود راه حل های اساسی قابل قبول (طرح های مرجع).

قضیه. هر راه حل پایه قابل قبول برای یک مسئله برنامه ریزی خطی مربوط به یک راس از چند وجهی راه حل است، و بالعکس، برای هر راس چند وجهی راه حل، یک راه حل اساسی قابل قبول مطابقت دارد.

یک نتیجه مهم از قضایای فوق بدست می آید:

اگر یک مسئله برنامه ریزی خطی یک راه حل بهینه داشته باشد، حداقل با یکی از راه حل های اساسی امکان پذیر آن منطبق است.

در نتیجه، بهینه تابع خطی هدف یک مسئله برنامه‌ریزی خطی را باید در میان تعداد متناهی راه‌حل‌های اساسی امکان‌پذیر آن جستجو کرد.

تعریف. هر راه حلی برای سیستم محدودیت ها راه حل قابل قبول برای PLP نامیده می شود.
تعریف. راه حل عملی که در آن تابع هدف به مقدار حداکثر یا حداقل می رسد، راه حل بهینه نامیده می شود.

با توجه به این تعاریف، مسئله LP را می توان به صورت زیر فرموله کرد: از بین تمام نقاط یک منطقه محدب، که راه حلی برای یک سیستم از محدودیت ها است، یکی را انتخاب کنید که مختصات آن تابع خطی را به حداقل برساند (بیشینه کند). اف = با 1 ایکس + با 2 y.
توجه داشته باشید که متغیرها ایکس, yدر ZLP، به عنوان یک قاعده، آنها مقادیر غیر منفی می گیرند ( ایکس≥ 0, y≥ 0)، بنابراین منطقه در ربع اول صفحه مختصات قرار دارد.

تابع خطی را در نظر بگیرید اف = با 1 ایکس + با 2 yو مقداری از ارزش آن را اصلاح کنید اف. اجازه دهید، برای مثال، اف= 0، یعنی با 1 ایکس + با 2 y= 0. نمودار این معادله یک خط مستقیم خواهد بود که از مبدا مختصات (0;0) می گذرد (شکل).
طراحی
هنگام تغییر این مقدار ثابت اف = د، سر راست با 1 ایکس+ با 2 y = dموازی جابجا می شود و کل صفحه را "طرح کلی" می کند. اجازه دهید D- چند ضلعی - دامنه حل سیستم محدودیت ها. وقتی تغییر می کند دسر راست با 1 ایکس + با 2 y = د، به مقداری د = د 1 به چند ضلعی می رسد D، بیایید این نقطه را بنامیم آ"نقطه ورود"، و سپس، پس از عبور از چند ضلعی، در مقداری د = د 2 آخرین نقطه مشترک را با آن خواهیم داشت که در، بیا تماس بگیریم که در"نقطه خروج".
واضح است که تابع هدف کوچکترین و بزرگترین مقادیر خود را دارد اف=با 1 ایکس + با 2 yبه نقاط ورودی خواهد رسید آو "خروج" که در.
با توجه به اینکه مقدار بهینه در مجموعه راه حل های امکان پذیر، تابع هدف رئوس ناحیه را می گیرد. D، می توانیم طرح زیر را برای حل مشکل پیشنهاد کنیم:

1. ساخت دامنه حل سیستم محدودیت؛
2. یک خط مستقیم مطابق با تابع هدف بسازید و با ترجمه موازی این خط مستقیم نقطه "ورود" یا "خروج" را بیابید (بسته به نیاز به حداقل یا حداکثر کردن تابع هدف).
3. مختصات این نقطه را تعیین کنید و مقدار تابع هدف را در آنها محاسبه کنید.

توجه داشته باشید که بردار ( با 1 , با 2)، عمود بر خط مستقیم، جهت رشد تابع هدف را نشان می دهد.

هنگام حل گرافیکی ZLP، دو مورد ممکن است که نیاز به بحث خاصی دارد.

مورد 1
شکل 6
هنگام حرکت یک خط مستقیم با 1 ایکس + با 2 y= د"ورود" یا "خروج" (مانند شکل) در امتداد ضلع چند ضلعی رخ خواهد داد. اگر چند ضلعی اضلاع موازی با خط داشته باشد این اتفاق می افتد با 1 ایکس+ با 2 در = د .
در این مورد، تعداد نامتناهی نقطه "خروج" ("ورودی") وجود دارد، یعنی هر نقطه ای در بخش AB. این بدان معنی است که تابع هدف حداکثر (حداقل) مقدار را نه در یک نقطه، بلکه در تمام نقاط واقع در سمت مربوطه چند ضلعی می گیرد. D.

مورد 2
بیایید موردی را در نظر بگیریم که محدوده مقادیر مجاز نامحدود است.
در مورد یک دامنه نامحدود، تابع هدف را می توان به گونه ای مشخص کرد که خط مستقیم مربوطه نقطه "خروج" (یا "ورود") نداشته باشد. سپس به حداکثر مقدار تابع (حداقل) هرگز نمی رسد - آنها می گویند که تابع نامحدود است.
طراحی
یافتن حداکثر مقدار تابع هدف ضروری است اف = 4ایکس + 6y→ حداکثر، با سیستمی از محدودیت ها
اجازه دهید منطقه ای از راه حل های امکان پذیر بسازیم، به عنوان مثال. بیایید سیستم نابرابری ها را به صورت گرافیکی حل کنیم. برای انجام این کار، هر خط مستقیم را می سازیم و نیم صفحه های تعریف شده توسط نابرابری ها را تعیین می کنیم.
ایکس + y = 18

ایکس	12	9
y	6	9

0,5ایکس + y = 12

ایکس	12	18
y	6	3

ایکس= 12 - موازی با محور OY ;
y= 9 - موازی با محور گاو نر ;
ایکس= 0 – محور OY ;
y = 0 – محور گاو نر;
ایکس OY;
y≥ 0 - نیم صفحه بالای محور گاو نر;
y≤ 9 - نیم صفحه زیر y = 9;
ایکس ≤ 12 - نیم صفحه به سمت چپ ایکس = 12;
0,5ایکس + yایکس + y = 12;
ایکس + y ایکس + y = 18.
طراحی
محل تقاطع تمام این نیم صفحه ها آشکارا یک پنج ضلعی است OAVSD، با رئوس در نقاط در باره(0; 0), آ(0; 9), که در(6; 9), با(12; 6), D(12; 0). این پنج ضلعی منطقه راه حل های امکان پذیر برای مشکل را تشکیل می دهد.

اف = 4ایکس + 6y→ حداکثر

ایکس	3	0
y	–2	0

اف = 0: 4ایکس + 6y ایکس+ 6y با(12؛ 6). در آن است اف = 4ایکس + 6y
بنابراین، هنگامی که ایکس = 12, y= 6 تابع اف اف= 4 ∙ 12 + 6 ∙ 6 = 84، برابر با 84. نقطه با مختصات (12؛ 6) تمام نابرابری های سیستم محدودیت را برآورده می کند و در آن مقدار تابع هدف بهینه است. اف* = 84 (مقدار بهینه را با "*" نشان خواهیم داد).
مشکل حل شده است. بنابراین، تولید 12 محصول از نوع I و 6 محصول از نوع II، با سود 84 هزار روبل ضروری است.

از روش گرافیکی برای حل مسائلی استفاده می شود که تنها دو متغیر در سیستم محدودیت داشتند. این روش برای سیستم های نابرابری با سه متغیر نیز قابل استفاده است. از نظر هندسی، وضعیت متفاوت خواهد بود، نقش خطوط مستقیم را صفحات در فضای سه بعدی ایفا می کنند و راه حل نابرابری در سه متغیر، نیم فضایی خواهد بود که در یک طرف صفحه قرار دارد. نقش مناطق را چند وجهی ایفا می کنند که محل تلاقی نیم فضاها هستند.

مثال شماره 2. معدن دو درز ایجاد می کند. بازده اوج برای لایه اول a1% است. برای دوم - a2٪. حداکثر بهره وری سطح کار برای لایه اول B1 هزار تن در سال، برای لایه دوم - B2 هزار تن در سال است. با توجه به تکنولوژی کار، تولید از لایه دوم نمی تواند بیشتر از تولید از لایه اول باشد. خروجی معدن از طریق معدن نباید بیش از C1 هزار تن در سال باشد. مجموع بار روی دو لایه در سال نباید کمتر از C2 هزار تن در سال باشد. یک مدل ریاضی ایجاد کنید و مجموعه ای از مقادیر بار مجاز را برای لایه های اول و دوم در سال بسازید.

مثال شماره 3. این فروشگاه 2 نوع نوشابه می فروشد: کولا و لیموناد. درآمد یک قوطی کولا 5 سنت و درآمد یک قوطی لیموناد 7 سنت است. به طور متوسط، یک فروشگاه بیش از 500 قوطی از هر دو نوشیدنی در روز نمی فروشد. با وجود این واقعیت که کولا توسط یک برند معروف تولید می شود، مشتریان لیموناد را ترجیح می دهند زیرا بسیار ارزان تر است. تخمین زده می شود که حجم فروش کولا و لیموناد باید حداقل 2:1 باشد؛ علاوه بر این، مشخص است که فروشگاه حداقل 100 قوطی کولا در روز به فروش می رساند. فروشگاه چند قوطی از هر نوشیدنی باید در ابتدای روز داشته باشد تا درآمد را به حداکثر برساند؟

مثال شماره 4. یک مسئله برنامه ریزی خطی را تقریباً به صورت گرافیکی حل کنید و سپس مقدار دقیق و حداکثر (min) مقدار تابع هدف را محاسبه کنید.

مثال شماره 5. یک شرکت مسافرتی به اتوبوس های سه تنی و اتوبوس های پنج تنی بیشتر نیاز ندارد. قیمت فروش اتوبوس های برند اول 20000 تومان، برند دوم 40000 تومان می باشد. یک شرکت مسافرتی نمی تواند بیش از 1 دلار برای خرید اتوبوس اختصاص دهد. چند اتوبوس از هر برند باید جداگانه خریداری شود تا ظرفیت حمل کل (کل) آنها حداکثر باشد. مشکل را گرافیکی حل کنید.

مثال شماره 6. با استفاده از روش گرافیکی، طرح تولید بهینه را در مسئله ارائه شده در جدول پیدا کنید.

مثال شماره 7. یک مسئله برنامه ریزی خطی را به صورت گرافیکی حل کنید، سیستم محدودیت های مسئله را در معرض تبدیل های جردن-گاوس قرار دهید. سیستم محدودیت مسئله به شکل زیر است:
a 11 x 1 + a 12 x 2 + a 13 x 3 + a 14 x 4 + a 15 x 5 = b 1
a 21 x 1 + a 22 x 2 + a 23 x 3 + a 24 x 4 + a 25 x 5 = b 2
a 31 x 1 + a 32 x 2 + a 33 x 3 + a 34 x 4 + a 35 x 5 = b 3
رهنمودها. با استفاده از این سرویس یا از طریق مطالعه SLAE می‌توان تبدیل‌های جردنو-گاوسی را انجام داد.

مثال شماره 8. این شرکت دو نوع محصول A و B تولید می کند که برای تولید آنها از سه نوع مواد اولیه استفاده می شود. برای تولید یک واحد محصول A باید مواد اولیه از هر نوع a1، a2، a3 کیلوگرم و برای یک واحد محصول B - b1، b2، b3 کیلوگرم مصرف شود. تولید با مواد اولیه هر نوع به ترتیب به میزان P1، P2، P3 کیلوگرم تامین می شود. هزینه یک واحد محصول A rub C1 است و هزینه یک واحد محصول B rub ​​C2 است. لازم است یک برنامه تولید برای محصولات A و B تهیه شود که حداکثر هزینه محصول نهایی را تضمین کند.

مثال شماره 2. یافتن حداکثر مقدار تابع هدف ضروری است اف = 4ایکس + 6y→ حداکثر، با یک سیستم محدودیت:

اجازه دهید منطقه ای از راه حل های امکان پذیر بسازیم، به عنوان مثال. بیایید سیستم نابرابری ها را به صورت گرافیکی حل کنیم. برای این کار تعداد محدودیت ها را برابر با 4 انتخاب می کنیم (شکل 1).
تصویر 1

سپس ضرایب متغیرها و خود محدودیت ها را پر می کنیم (شکل 2).
شکل 2

شکل 3
ایکس= 12 - موازی با محور OY;
y= 9 - موازی با محور گاو نر;
ایکس> = 0 – محور OY
y= 0 – محور گاو نر;
ایکس≥ 0 - نیم صفحه سمت راست محور OY;
y≥0 - نیم صفحه بالای محور گاو نر;
y≤ 9 - نیم صفحه زیر y = 9;
ایکس≤ 12 - نیم صفحه به سمت چپ ایکس = 12;
0,5ایکس + y≤ 12 - نیم صفحه زیر خط مستقیم 0.5 ایکس + y = 12;
ایکس + y≤ 18 - نیم صفحه زیر خط مستقیم ایکس + y = 18.

محل تلاقی همه این نیم صفحه ها یک پنج ضلعی است ABCDE، با رئوس در نقاط آ(0; 0), ب(0;9), سی(6; 9), D(12;6), E(12; 0). این پنج ضلعی منطقه راه حل های امکان پذیر برای مشکل را تشکیل می دهد.

تابع هدف مسئله را در نظر بگیرید اف = 4ایکس + 6y→ حداکثر

ایکس	3	0
y	–2	0

بیایید یک خط مستقیم مطابق با مقدار تابع بسازیم اف = 0: 4ایکس + 6y= 0. این خط را به صورت موازی حرکت می دهیم. از کل خانواده خطوط 4 ایکس + 6y= تعیین آخرین راس که خط از آن عبور می کند هنگام خروج از مرز چند ضلعی، راس خواهد بود. با(12؛ 6). در آن است اف = 4ایکس + 6yبه حداکثر مقدار خود خواهد رسید.

بنابراین، هنگامی که ایکس = 12, y= 6 تابع افبه حداکثر مقدار خود می رسد اف= 4 ∙ 12 + 6 ∙ 6 = 84، برابر با 84. نقطه با مختصات (12;6) تمام نابرابری های سیستم محدودیت را برآورده می کند و در آن مقدار تابع هدف بهینه است. اف* = 84.

آزمون در رشته "تحقیق در عملیات"

(پاسخ های صحیح اول هستند)

1. اصطلاح "تحقیق در عملیات" ظاهر شد ...

در طول جنگ جهانی دوم

در دهه 50 قرن XX

در دهه 60 قرن XX

در دهه 70 قرن XX

در دهه 90 قرن XX

در آغاز قرن بیست و یکم

2. تحقیق در عملیات اشاره به (انتخاب مناسب ترین گزینه) ...

مجموعه ای از روش های علمی برای حل مشکلات مدیریت موثر سیستم های سازمانی

مجموعه ای از اقدامات انجام شده برای اجرای عملیات خاص

مجموعه ای از روش ها برای اجرای طرح

روش های علمی تخصیص منابع هنگام سازماندهی تولید

3. مراحلی را که معمولاً هر تحقیق عملیاتی طی می‌کند ترتیب دهید:

فرمول بندی مسئله

ساخت یک مدل معنادار (کلامی) از شی (فرآیند) مورد بررسی

ساخت یک مدل ریاضی

حل مسائل فرموله شده بر اساس مدل ریاضی ساخته شده

بررسی نتایج به دست آمده برای کفایت ماهیت سیستم مورد مطالعه

پیاده سازی راه حل به دست آمده در عمل

4. در تحقیق در عملیات، عملیات به معنای ...

هر رویداد (سیستم اقدامات) که با یک برنامه واحد متحد شده و هدف آن دستیابی به یک هدف است

هر رویداد غیر قابل کنترل

مجموعه ای از اقدامات فنی برای اطمینان از تولید محصولات مصرفی

5. راه حل بهینه نامیده می شود ...

اگر به یک دلیل یا آن دلیل بر دیگران ارجح باشد

اگر عقلانی باشد

در صورت توافق با مسئولین

در صورتی که به تصویب مجمع عمومی برسد

6. برنامه نویسی ریاضی ...

به مطالعه مشکلات شدید و توسعه روش هایی برای حل آنها مشغول است

فرآیند ایجاد برنامه های کامپیوتری تحت هدایت ریاضیدانان است

حل مسائل ریاضی روی کامپیوتر

7-مسئله برنامه ریزی خطی ...

یافتن بزرگترین (کوچکترین) مقدار یک تابع خطی در حضور قیود خطی

ایجاد یک برنامه خطی در یک زبان برنامه نویسی انتخاب شده که برای حل یک مسئله معین طراحی شده است

توصیف یک الگوریتم خطی برای حل یک مسئله داده شده

8. در یک مسئله برنامه نویسی درجه دوم ...

تابع هدف درجه دوم است

مساحت راه حل امکان پذیر یک مربع است

محدودیت ها شامل توابع درجه دوم هستند

9. در مسائل برنامه نویسی عدد صحیح ...

مجهولات فقط می توانند مقادیر صحیح را بگیرند

تابع هدف لزوما باید یک مقدار صحیح بگیرد و مجهولات می توانند هر کدام باشند

تابع هدف یک ثابت عددی است

10. در مسائل برنامه نویسی پارامتری ...

تابع هدف و/یا سیستم محدودیت ها حاوی پارامتر(های) است.

ناحیه راه حل های امکان پذیر متوازی الاضلاع یا متوازی الاضلاع است

تعداد متغیرها فقط می تواند زوج باشد

11. در مسائل برنامه نویسی پویا ...

فرآیند یافتن راه حل چند مرحله ای است

تولید دینامیت باید منطقی شود

نیاز به استفاده بهینه از بلندگوها

12. مسئله برنامه ریزی خطی زیر مطرح شده است:

اف(ایکس 1, ایکس 2) = 5ایکس 1 + 6ایکس 2→ حداکثر

0.2ایکس 1 + 0.3ایکس 2 ≤ 1.8,

0.2ایکس 1 + 0.1ایکس 2 ≤ 1.2,

0.3ایکس 1 + 0.3ایکس 2 ≤ 2.4,

ایکس 1 ≥ 0, ایکس 2 ≥ 0.

وظیفه ای را انتخاب کنید که معادل این کار باشد.

اف(ایکس 1, ایکس 2)= 5ایکس 1 + 6ایکس 2 → حداکثر,

2ایکس 1 + 3ایکس 2 ≤ 18,

2ایکس 1 + ایکس 2 ≤ 12,

ایکس 1 + ایکس 2 ≤ 8,

ایکس 1 ≥ 0,

ایکس 2 ≥ 0.

اف(ایکس 1, ایکس 2)= 6ایکس 1 + 5ایکس 2 → دقیقه،

2ایکس 1 + 3ایکس 2 ≤ 18,

2ایکس 1 + ایکس 2 ≤ 12,

ایکس 1 + ایکس 2 ≤ 8,

ایکس 1 ≥ 0,

ایکس 2 ≥ 0.

اف(ایکس 1, ایکس 2)= 50ایکس 1 + 60ایکس 2 → حداکثر,

2ایکس 1 + 3ایکس 2 ≤ 18,

2ایکس 1 + ایکس 2 ≤ 12,

ایکس 1 + ایکس 2 ≤ 8,

ایکس 1 ≥ 0,

ایکس 2 ≥ 0.

اف(ایکس 1, ایکس 2)= 5ایکس 12 + 6ایکس 22 → حداکثر,

2ایکس 1 + 3ایکس 2 ≤ 18,

2ایکس 1 + ایکس 2 ≤ 12,

3ایکس 1 + ایکس 2 ≤ 2.4,

ایکس 1 ≥ 0,

ایکس 2 ≥ 0.

13. تابع هدف یک مسئله برنامه ریزی خطی می تواند تابع:

اف=12x1+20x2-3 0x3→دقیقه

اف= →دقیقه

اف=→حداکثر

اف=→حداکثر

14. سیستم قیود برای مسئله برنامه ریزی خطی می تواند سیستم زیر باشد:

15. روش سیمپلکس:

روش تحلیلی برای حل مسئله برنامه ریزی خطی پایه

روشی برای یافتن منطقه راه حل های امکان پذیر برای یک مسئله برنامه ریزی خطی.

روش گرافیکی برای حل مسئله اصلی برنامه ریزی خطی.

روشی برای کاهش یک مسئله برنامه ریزی خطی عمومی به شکل متعارف.

16. مسئله برنامه ریزی خطی این است:

یافتن بزرگترین یا کوچکترین مقدار یک تابع خطی در حضور قیود خطی

توسعه یک الگوریتم خطی و پیاده سازی آن بر روی کامپیوتر

تدوین و حل یک سیستم معادلات خطی

جست‌وجوی یک مسیر خطی توسعه فرآیندی که توسط یک سیستم محدود از محدودیت‌ها توصیف شده است.

17. منطقه راه حل های امکان پذیر برای مسئله برنامه ریزی خطی نمی تواندبه این شکل نگاه کنید:

18. تابع هدف یک مسئله برنامه ریزی خطی می تواند تابع:

اف=12x1+20x2-3 0x3→دقیقه

اف= →دقیقه

اف=→حداکثر

اف=→حداکثر

19. سیستم قیود برای مسئله برنامه ریزی خطی می تواند سیستم:

20. منطقه راه حل های امکان پذیر برای مسئله برنامه ریزی خطی به شکل زیر است:

اف(ایکس 1, ایکس 2)= 3ایکس 1 + 5ایکس 2 برابر ...

21. ناحیه راه حل های امکان پذیر برای یک مسئله برنامه ریزی خطی به شکل زیر است:

سپس حداکثر مقدار تابع اف(ایکس 1, ایکس 2)= 5ایکس 1 + 3ایکس 2 برابر ...

22. ناحیه راه حل های امکان پذیر برای مسئله برنامه ریزی خطی به شکل زیر است:

سپس حداکثر مقدار تابع اف(ایکس 1, ایکس 2)= 2ایکس 1 - 2ایکس 2 برابر ...

23. ناحیه راه حل های امکان پذیر برای مسئله برنامه ریزی خطی به شکل زیر است:

اف(ایکس 1, ایکس 2)= 2ایکس 1 - 2ایکس 2 برابر ...

24. منطقه راه حل های امکان پذیر برای مسئله برنامه ریزی غیرخطی به شکل زیر است:

سپس حداکثر مقدار تابع اف(ایکس 1, ایکس 2)= ایکس 2 – ایکس 12 برابر ...

25. حداکثر مقدار تابع هدف اف(ایکس 1, ایکس 2)= 5ایکس 1 + 2ایکس 2 با محدودیت
ایکس 1 + ایکس 2 ≤ 6,

ایکس 1 ≤ 4,

ایکس 1 ≥ 0, ایکس 2 ≥ 0 برابر است...

26. یک شرکت کوچک دو نوع محصول تولید می کند. تولید یک محصول از نوع A به 2 کیلوگرم مواد اولیه و برای تولید یک محصول از نوع B به 1 کیلوگرم نیاز دارد. در مجموع 60 کیلوگرم مواد اولیه وجود دارد. در صورتی که قیمت فروش یک محصول از نوع A 3 c.u باشد، نوع B - 1 c.u، باید یک برنامه تولید تهیه شود که دریافت بیشترین درآمد را تضمین کند. یعنی بیش از 25 محصول از نوع A مورد نیاز نیست و بیش از 30 محصول از نوع B لازم نیست.

این وظیفه ...

مشکل برنامه ریزی خطی

حل مشکل با روش برنامه نویسی پویا

مشکل برنامه ریزی شبکه

27. یک شرکت کوچک دو نوع محصول تولید می کند. تولید یک محصول از نوع A به 2 کیلوگرم مواد اولیه و برای تولید یک محصول از نوع B به 1 کیلوگرم نیاز دارد. در مجموع 60 کیلوگرم مواد اولیه وجود دارد. در صورتی که قیمت فروش یک محصول از نوع A 3 c.u باشد، نوع B - 1 c.u، باید یک برنامه تولید تهیه شود که دریافت بیشترین درآمد را تضمین کند. یعنی بیش از 25 محصول از نوع A مورد نیاز نیست و بیش از 30 محصول از نوع B لازم نیست.

تابع هدف این مسئله تابع ...

اف(x1، x2)=3x1+x2→حداکثر

اف(x1، x2)=25x1+30x2→حداکثر

اف(x1، x2)=2x1+x2→حداکثر

اف(x1، x2)=60 -2x1 - x2→دقیقه

28. یک شرکت کوچک دو نوع محصول تولید می کند. تولید یک محصول از نوع A به 2 کیلوگرم مواد اولیه و برای تولید یک محصول از نوع B به 1 کیلوگرم نیاز دارد. در مجموع 60 کیلوگرم مواد اولیه وجود دارد. در صورتی که قیمت فروش یک محصول از نوع A 3 c.u باشد، نوع B - 1 c.u، باید یک برنامه تولید تهیه شود که دریافت بیشترین درآمد را تضمین کند. e.، و محصولات نوع A نباید بیش از 25 تولید شوند، و نوع B - بیش از 30 عدد

یک برنامه معتبر برای این کار، طرح است:

X=(20, 20)

X=(25, 15)

X=(20, 25)

X=(30, 10)

29. در دو نقطه A1 و A2 به ترتیب 60 و 160 واحد کالا وجود دارد. کلیه کالاها باید به ترتیب به تعداد 80، 70 و 70 عدد به نقاط B1، B2، B3 حمل شوند. ماتریس تعرفه به شرح زیر است: . حمل و نقل خود را طوری برنامه ریزی کنید که هزینه آن حداقل باشد.

این وظیفه ...

وظیفه حمل و نقل

مسئله برنامه نویسی غیرخطی

مشکل فروشنده دوره گرد

مشکل تکلیف

30. در دو نقطه A1 و A2 به ترتیب 60 و 160 واحد کالا وجود دارد. کلیه کالاها باید به ترتیب به تعداد 80، 70 و 70 عدد به نقاط B1، B2، B3 حمل شوند. ماتریس تعرفه به شرح زیر است: . حمل و نقل خود را طوری برنامه ریزی کنید که هزینه آن حداقل باشد

طرح اساسی برای این کار، طرح است:

;

31. در دو نقطه A1 و A2 به ترتیب 60 و 160 واحد کالا وجود دارد. کلیه کالاها باید به ترتیب به تعداد 80، 70 و 70 عدد به نقاط B1، B2، B3 حمل شوند. ماتریس تعرفه به شرح زیر است: . حمل و نقل خود را طوری برنامه ریزی کنید که هزینه آن حداقل باشد.

تابع هدف این مسئله تابع:

اف=4x11+6x12+ 8x13+5x21+8x22+7x23→دقیقه

اف= →دقیقه

اف=60x1+160x2+ 80x3+70x4+705 →حداکثر

اف=60x1+160x2- 80x3– 70x4- 705 →دقیقه

32. در دو نقطه A1 و A2 به ترتیب 60 و 160 واحد کالا وجود دارد. کلیه کالاها باید به ترتیب به تعداد 80، 70 و 70 عدد به نقاط B1، B2، B3 حمل شوند. ماتریس تعرفه به شرح زیر است: . حمل و نقل خود را طوری برنامه ریزی کنید که هزینه آن حداقل باشد.

برنامه بهینه برای این مشکل طرح زیر است:

;

.

;

;

33. مشکل حمل و نقل

بسته می شود اگر ...

34. مشکل حمل و نقل

است…

باز کن

بسته

غیر قابل حل

35. مشکل حمل و نقل

است…

بسته

باز کن

غیر قابل حل

36. برای حل مشکل حمل و نقل زیر

نیاز به ورود ...

مصرف کننده ساختگی

تامین کننده ساختگی؛

تعرفه موثر

37. برای حل مشکل حمل و نقل زیر

نیاز به ورود ...

تامین کننده ساختگی؛

مصرف کننده ساختگی

تعرفه موثر

نرخ بهره موثر

38. از جمله این وظایف حمل و نقل

بسته اند...

39. طرح مرجع اولیه برای مشکل حمل و نقل را می توان ...

تمام روش های فوق

روش گوشه شمال غربی

روش حداقل تعرفه

روش ترجیح مضاعف

روش تقریب وگل

40. اگر تابع هدف یک مسئله برنامه ریزی خطی روی حداکثر تنظیم شود، آنگاه ... تابع هدف یک مسئله دوگانه روی حداقل تنظیم می شود.

هیچ تابع هدف در مشکل دوگانه وجود ندارد

مشکل دوگانه راه حلی ندارد

مشکل دوگانه راه حل های بی نهایت زیادی دارد

41. با توجه به یک مسئله برنامه ریزی خطی:

اف(ایکس 1, ایکس 2)= 2ایکس 1 + 7ایکس 2 → حداکثر,

2ایکس 1 + 3ایکس 2 ≤ 14,

ایکس 1 + ایکس 2 ≤ 8,

ایکس 1 ≥ 0, ایکس 2 ≥ 0.

دوگانه برای این مشکل به شرح زیر است ...

اف*(y1, y2)= 14y1 + 8y2 → دقیقه,

3 سال 1 + y2 ³ 7،

y 1 ≥ 0، y2 ≥ 0.

اف*(y1, y2)= 2y1 + 7y2 → دقیقه,

2y1 + 3y2 ³ 14،

y 1 + y2 ³ 8،

y 1 £ 0، y2 £ 0.

اف*(y1, y2)= 2y1 + 7y2 → دقیقه,

3 y 1 + y2 ³ 7،

y 1 £ 0، y2 £ 0.

اف*(y1, y2)= 14y1 + 8y2 → دقیقه,

y 1 + y2 ³ 7،

y 1 ≥ 0، y2 ≥ 0.

42. اگر یکی از یک جفت مسئله دوگانه طرح بهینه داشته باشد، پس...

و دیگری برنامه بهینه دارد

دیگری برنامه بهینه ای ندارد

دیگری هیچ راه حل عملی ندارد

43. اگر یکی از یک جفت مسئله دوگانه طرح بهینه داشته باشد، پس...

و دیگری دارای پلان بهینه است و مقادیر توابع هدف با نقشه های بهینه آنها با یکدیگر برابر است

و دیگری طرح بهینه دارد، اما مقادیر توابع هدف برای طرح های بهینه آنها با یکدیگر برابر نیست.

مشکل دیگر ممکن است برنامه بهینه نداشته باشد، اما راه حل های قابل اجرا داشته باشد

44. اگر تابع هدف یکی از یک جفت مسئله دوگانه محدود نباشد (برای مسئله حداکثر - از بالا، برای حداقل مسئله - از پایین)، سپس

کار دیگر هیچ برنامه معتبری ندارد

مشکل دیگر برنامه های قابل اجرا دارد اما برنامه بهینه ندارد

تابع هدف وظیفه دیگر نیز نامحدود است

45. هنگام حل برخی از مسائل برنامه ریزی غیرخطی، ...

روش ضریب لاگرانژ

روش گاوسی

روش تقریب وگل

روش گوموری

46. ​​یک مسئله برنامه ریزی غیرخطی داده شده است

اف(ایکس 1, ایکس 2)= ایکس 12 + ایکس 22 → حداکثر,

ایکس 1 + ایکس 2 =6,

ایکس 1 ≥ 0, ایکس 2 ≥ 0.

اف(ایکس 1, ایکس 2) …

غیر قابل دسترس (+ ¥)

47. یک مسئله برنامه ریزی غیرخطی داده شده است

اف(ایکس 1, ایکس 2)= ایکس 12 + ایکس 22 → مترکه در,

ایکس 1 + ایکس 2 =6,

ایکس 1 ≥ 0, ایکس 2 ≥ 0.

اف(ایکس 1, ایکس 2) …

48. یک مسئله برنامه ریزی غیرخطی داده شده است

اف(ایکس 1, ایکس 2)= ایکس 12 + ایکس 22 → حداکثر,

ایکس 1 + ایکس 2 =6,

ایکس 1, ایکس 2 - هر.

بزرگترین مقدار تابع هدف اف(ایکس 1, ایکس 2) …

غیر قابل دسترس (+ ¥)

49. یک مسئله برنامه ریزی غیرخطی داده شده است

اف(ایکس 1, ایکس 2)= ایکس 12 + ایکس 22 → مترکه در,

ایکس 1 + ایکس 2 =6,

ایکس 1, ایکس 2 - هر.

حداقل مقدار تابع هدف اف(ایکس 1, ایکس 2) …

غیر قابل دسترس (- ¥)

50. منطقه راه حل های امکان پذیر برای یک مسئله برنامه ریزی غیرخطی به شکل زیر است:

سپس حداکثر مقدار تابع اف(ایکس 1, ایکس 2)= ایکس 12 +ایکس 22 برابر ...

51. ناحیه راه حل های امکان پذیر برای یک مسئله برنامه ریزی غیرخطی به شکل زیر است:

سپس مقدار حداقل تابع اف(ایکس 1, ایکس 2)= ایکس 12 +ایکس 22 برابر ...

52. برای حل مشکل حمل و نقل می توان از ...

روش بالقوه

روش ضریب لاگرانژ

روش گاوسی

روش سرگردانی

53. در سیستم قیود یک مسئله برنامه ریزی خطی عمومی ...

54. در سیستم قیود یک مسئله برنامه ریزی خطی استاندارد (متقارن) ...

فقط نابرابری ها می توانند وجود داشته باشند

هر دو معادله و نابرابری ممکن است وجود داشته باشد

فقط معادلات می توانند وجود داشته باشند

55. در سیستم قیود مسئله برنامه ریزی خطی متعارف (اصلی) ...

فقط معادلات می توانند وجود داشته باشند (به شرطی که متغیرها غیر منفی باشند)

فقط نابرابری ها می توانند وجود داشته باشند (به شرطی که متغیرها غیرمنفی باشند)

هم معادلات و هم نابرابری ممکن است وجود داشته باشد (به شرطی که متغیرها غیر منفی باشند)

56. مسئله برنامه ریزی خطی

اف(ایکس 1, ایکس 2)= 2ایکس 1 + 7ایکس 2 → حداکثر,

2ایکس 1 + 3ایکس 2 ≤ 14,

ایکس 1 + ایکس 2 ≤ 8,

ایکس 1 ≥ 0, ایکس 2 ≥ 0.

ثبت شده در ...

فرم استاندارد (متقارن).

شکل متعارف (اساسی).

فرم کلامی

57. برای ثبت یک کار

اف(ایکس 1, ایکس 2)= 2ایکس 1 + 7ایکس 2 → حداکثر,

2ایکس 1 + 3ایکس 2 ≤ 14,

ایکس 1 + ایکس 2 ≤ 8,

ایکس 1 ≥ 0, ایکس 2 ≥ 0.

به شکل متعارف...

58. برای ثبت یک کار

اف(ایکس 1, ایکس 2)= 2ایکس 1 + 7ایکس 2 → حداکثر,

2ایکس 1 + 3ایکس 2 ≤ 14,

ایکس 1 + ایکس 2 ≤ 8,

ایکس 1 + 4ایکس 2 ≥ 10,

ایکس 1 ≥ 0, ایکس 2 ≥ 0.

به شکل متعارف...

سه متغیر غیر منفی اضافی باید معرفی شود

لازم است دو متغیر غیرمنفی اضافه شود

چهار متغیر غیر منفی اضافی باید معرفی شود

59. برای ثبت یک کار

اف(ایکس 1, ایکس 2)= 2ایکس 1 + 7ایکس 2 → حداکثر,

2ایکس 1 + 3ایکس 2 = 14,

ایکس 1 + ایکس 2 ≤ 8,

ایکس 1 + 4ایکس 2 ≥ 10,

ایکس 1 ≥ 0, ایکس 2 ≥ 0.

به شکل متعارف...

لازم است دو متغیر غیرمنفی اضافه شود

سه متغیر غیر منفی اضافی باید معرفی شود

چهار متغیر غیر منفی اضافی باید معرفی شود

پنج متغیر غیر منفی اضافی باید معرفی شود

60. هنگام حل مسائل برنامه نویسی اعداد صحیح می توان از ...

روش گوموری

روش ضریب لاگرانژ

روش گاوسی

روش تقریب وگل

61. مبنای حل مسائل با استفاده از روش برنامه نویسی پویا...

اصل تیغ اوکام

اصل "دندان در برابر دندان، چشم در برابر چشم"

اصل هایزنبرگ

62. وضعیتی که در آن احزابی که منافع آنها به طور کامل یا جزئی مخالف است را می گویند...

(تعارض، درگیری، درگیری، درگیری)

63. درگیری واقعی یا رسمی که در آن حداقل دو شرکت کننده (بازیکن) وجود داشته باشد که هر یک برای رسیدن به اهداف خود تلاش می کنند ...

(بازی، بازی)

64. به اعمال مجاز هر بازیکن با هدف رسیدن به هدف معینی می گویند...

(قوانین بازی، قوانین بازی)

65. ارزیابی کمی از نتایج یک بازی به نام ...

(پرداخت، پرداخت، پرداخت)

66. اگر فقط دو طرف (دو نفر) در بازی شرکت کنند، بازی به نام ...

(دو نفره، دونفره، بازی دو نفره، بازی دو نفره)

67. اگر در بازی دونفره مجموع پرداخت ها صفر باشد یعنی باخت یک بازیکن برابر با سود بازیکن دیگر باشد، بازی را بازی...

(مجموع صفر)

68. توصیف بدون ابهام از انتخاب بازیکن در هر یک از موقعیت های ممکن که در آن او باید یک حرکت شخصی انجام دهد نامیده می شود.

(استراتژی بازیکن، استراتژی بازیکن، استراتژی، استراتژی)

69. اگر زمانی که بازی چندین بار تکرار می شود، یک استراتژی حداکثر میانگین برد ممکن (حداقل میانگین باخت ممکن) را برای بازیکن فراهم کند، به چنین استراتژی ...

(بهینه، بهینه، استراتژی بهینه، استراتژی بهینه)

70. بگذارید a قیمت پایین تر و b قیمت بالای یک بازی زوج صفر باشد. پس این جمله درست است ...

71. فرض کنید a قیمت کمتر و b قیمت بالای یک بازی زوج صفر باشد. اگر a = b = v، عدد v نامیده می شود...

به قیمت بازی

نقطه تعادل

استراتژی بهینه

استراتژی مختلط

72. فرض کنید a قیمت کمتر و b قیمت بالای یک بازی زوج صفر باشد. اگر a = b، بازی نامیده می شود ...

بازی نقطه زینی

درگیری غیر قابل حل

یک بازی بدون قوانین

73. برداری که هر یک از اجزای آن بسامد نسبی استفاده بازیکن از استراتژی خالص مربوطه را نشان می دهد، نامیده می شود ...

استراتژی مختلط

بردار راهنما

بردار معمولی

شیب

74. قیمت پایین تر یک بازی ماتریسی که توسط ماتریس پرداخت می شود ...

قیمت کمتر بیشتر

برابر با قیمت پایین تر

وجود ندارد

81. بازی ماتریسی ارائه شده توسط ماتریس پرداخت، ...

نقطه زین دارد

نقطه زین ندارد

نه یک جفت

82. قیمت یک بازی ارائه شده توسط ماتریس پرداخت …

83. بازی ماتریسی ارائه شده توسط ماتریس پرداخت، ...

یک اتاق بخار است

نقطه زین دارد

نه یک جفت

84. یک بازی جفت با مجموع صفر، که توسط ماتریس پرداخت آن ارائه شده است، می تواند به ... کاهش یابد.

مشکل برنامه ریزی خطی

مسئله برنامه نویسی غیرخطی

مسئله برنامه ریزی خطی عدد صحیح

مسئله بهینه سازی کلاسیک

85. قیمت پایین تر یک بازی ماتریسی که توسط ماتریس پرداخت می شود ...

قیمت کمتر بیشتر

برابر با قیمت پایین تر

وجود ندارد

92. بازی ماتریسی داده شده توسط ماتریس پرداخت، ...

نقطه زین ندارد

نقطه زین دارد

نه یک جفت

93. قیمت بازی داده شده توسط ماتریس پرداخت در محدوده ...

94. اگر در جریانی از رویدادها وقایع در فواصل زمانی از پیش تعیین شده و کاملاً تعریف شده به دنبال یکدیگر بیایند، چنین جریانی نامیده می شود ...

منظم

سازماندهی شده است

95. اگر احتمال افتادن هر تعداد رویداد در یک بازه زمانی فقط به طول این بازه بستگی داشته باشد و به فاصله زمانی این فاصله از ابتدای زمان بستگی نداشته باشد، جریان مربوط به رویدادها نامیده می شود:

ثابت

جریان بدون عواقب

ساده ترین

پواسون

96. اگر تعداد رویدادهایی که در یکی از بازه‌های زمانی انتخاب شده به‌طور دلخواه اتفاق می‌افتد، به تعداد رویدادهایی که در بازه زمانی دیگری که به‌طور دلخواه انتخاب شده است، بستگی نداشته باشد، مشروط بر اینکه این فواصل با هم تلاقی نداشته باشند، جریان متناظر رویدادها نامیده می‌شود. ...

جریان بدون عواقب

منظم

نشان دهنده

طبیعی

97. اگر احتمال وقوع دو یا چند رویداد همزمان در مدت زمان بسیار کوتاه در مقایسه با احتمال وقوع تنها یک رویداد ناچیز باشد، جریان متناظر رویدادها را ...

معمولی

خارق العاده

طبیعی

پواسون

98. اگر جریانی از رویدادها به طور همزمان دارای خاصیت ایستایی، عادی بودن و عدم عواقب باشد، به آن می گویند:

ساده ترین (پواسون)

طبیعی

99. QS تک کاناله با خرابی ایستگاه تعمیر و نگهداری روزانه برای شستشوی خودرو می باشد. درخواست - ماشینی که در زمانی که پست اشغال شده می رسد - از خدمات خودداری می شود. شدت جریان خودرو λ=1.0 (ماشین در ساعت). میانگین مدت خدمات 1.8 ساعت است. جریان ماشین و جریان سرویس ساده ترین هستند. سپس در حالت ثابت توان نسبی qبرابر...

100. QS تک کاناله با خرابی یک ایستگاه تعمیر و نگهداری روزانه برای شستشوی خودرو است. درخواست - ماشینی که در زمانی که پست اشغال شده می رسد - از خدمات خودداری می شود. شدت جریان خودرو λ=1.0 (ماشین در ساعت). میانگین مدت خدمات 1.8 ساعت است. جریان ماشین و جریان سرویس ساده ترین هستند. سپس در حالت ثابت، درصد امتناع خودروهای دریافت کننده خدمات برابر است با ...